这个问题是问题“Wonderful Coloring - 1”的延伸。它有很多差异,因此您应该完整阅读此声明。
最近,Paul 和 Mary 发现了一个新的最喜欢的整数序列 $$$a_1, a_2, \dots, a_n$$$。他们想用 $$$k$$$ 颜色的粉笔来绘制它。如果满足以下条件,则序列的着色被称为精彩:
1. 序列中的每个元素要么用 $$$k$$$ 颜色之一绘制,要么不绘制;
2.每两个涂成相同颜色的元素都不相同(即没有两个相同的值涂成相同的颜色);
3. 让我们计算每种 $$$k$$$ 颜色所绘制的元素的数量 — 所有计算出的数字必须相等;
4.序列的着色元素总数是满足前三个条件的序列的所有着色中的最大值。
例如考虑序列 $$$a=[3, 1, 1, 1, 1, 10, 3, 10, 10, 2]$$$ 和 $$$k=3$$$。图中显示了该序列的美妙色彩之一。
序列 $$$a=[3, 1, 1, 1, 1, 10, 3, 10, 10, 2]$$$ 和 $$$k=3$$$ 的精彩着色示例。请注意,其中一个元素未绘制。
帮助保罗和玛丽找到给定序列 $$$a$$$ 的美妙着色。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10000$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。
每个测试用例由两行组成。第一个包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2\cdot10^5$$$, $$$1 \le k \le n$$$) — 分别是给定序列的长度和颜色的数量。第二个包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
输出 $$$t$$$ 行,每一行都必须包含相应测试用例的精彩着色描述。
每个美妙的颜色必须打印为 $$$n$$$ 整数 $$$c_1, c_2, \dots, c_n$$$ ($$$0 \le c_i \le k$$$) 的序列,并用空格分隔,其中
- $$$c_i=0$$$,如果第 $$$i$$$ 个元素未绘制;
- $$$c_i>0$$$,如果第 $$$i$$$ 个元素以第 $$$c_i$$$ 颜色绘制。
请记住,您需要最大化绘制元素的总数才能获得美妙的着色。如果有多种解决方案,请打印其中之一。
示例
输入 #1
6 10 3 3 1 1 1 1 10 3 10 10 2 4 4 1 1 1 1 1 1 1 13 1 3 1 4 1 5 9 2 6 5 3 5 8 9 13 2 3 1 4 1 5 9 2 6 5 3 5 8 9 13 3 3 1 4 1 5 9 2 6 5 3 5 8 9
输出 #1
1 1 0 2 3 2 2 1 3 3 4 2 1 3 1 0 0 1 1 0 1 1 1 0 1 1 1 0 2 1 2 2 1 1 1 1 2 1 0 2 2 1 1 3 2 1 3 3 1 2 2 3 2 0
注意
在第一个测试用例中,答案如图语句中所示。红色的数字为 $$$1$$$,蓝色的数字为 $$$2$$$,绿色的数字为 $$$3$$$。