#P17983. Redundancy Refrain

Redundancy Refrain

Redundancy Refrain

题目描述

给定长度为 nn 的数组 aa,每个元素属于 {0,1,…,k}\{0,1,\ldots,k\}。你需要把每个 00 替换成 11 到 kk 中的一个整数,非零元素必须保持不变,得到数组 bb。

如果存在两个不同的起点 x≠yx\ne y,使长度均为 ℓ\ell 的子数组

$$b_x,\ldots,b_{x+\ell-1}\quad\text{与}\quad b_y,\ldots,b_{y+\ell-1}$$

包含完全相同的多重集合,即每个数在两段中的出现次数均相同,则称这两段形成一个长度为 ℓ\ell 的重复。两段允许重叠,且其中元素的排列顺序可以不同。

定义数组得分为所有这类重复的最大长度;没有重复时得分为 00。请构造一个得分最小的补全数组。

输入格式

第一行一个整数 TT。每个用例占两行:

第一行两个整数 n,kn,k。

第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。

输出格式

每个用例输出一行 nn 个整数 b1,…,bnb_1,\ldots,b_n,满足 1≤bi≤k1\le b_i\le k;若 ai≠0a_i\ne0,必须有 bi=aib_i=a_i。

输出任意一个达到最小得分的数组即可,无需输出得分。

数据范围

1≤T≤1041\le T\le10^4,2≤n≤2×1052\le n\le2\times10^5,1≤k≤n1\le k\le n,0≤ai≤k0\le a_i\le k。

所有用例的 nn 之和不超过 2×1052\times10^5。

样例

4
8 3
0 1 0 2 1 3 0 2
3 3
1 0 2
9 7
0 1 1 0 5 0 4 0 7
6 6
0 0 0 0 0 0
1 1 3 2 1 3 2 2
1 3 2
2 1 1 3 5 6 4 4 7
1 2 3 4 5 6