CF1551B2.Wonderful Coloring - 2

This problem is an extension of the problem "Wonderful Coloring - 1". It has quite many differences, so you should read this statement completely.

Recently, Paul and Mary have found a new favorite sequence of integers $a_1, a_2, \dots, a_n$. They want to paint it using pieces of chalk of $k$ colors. The coloring of a sequence is called wonderful if the following conditions are met:

1. each element of the sequence is either painted in one of $k$ colors or isn't painted;
2. each two elements which are painted in the same color are different (i. e. there's no two equal values painted in the same color);
3. let's calculate for each of $k$ colors the number of elements painted in the color — all calculated numbers must be equal;
4. the total number of painted elements of the sequence is the maximum among all colorings of the sequence which meet the first three conditions.

E. g. consider a sequence $a=[3, 1, 1, 1, 1, 10, 3, 10, 10, 2]$ and $k=3$. One of the wonderful colorings of the sequence is shown in the figure.

The example of a wonderful coloring of the sequence $a=[3, 1, 1, 1, 1, 10, 3, 10, 10, 2]$ and $k=3$. Note that one of the elements isn't painted.

Help Paul and Mary to find a wonderful coloring of a given sequence $a$.

本题是“奇妙染色 - 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$ 下的一种奇妙染色示例。注意：其中一个元素未被染色。

请帮助 Paul 和 Mary 为给定序列 $a$ 找出一种奇妙染色方案。

The first line contains one integer $t$ ($1 \le t \le 10000$) — the number of test cases. Then $t$ test cases follow.

Each test case consists of two lines. The first one contains two integers $n$ and $k$ ($1 \le n \le 2\cdot10^5$, $1 \le k \le n$) — the length of a given sequence and the number of colors, respectively. The second one contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

Output $t$ lines, each of them must contain a description of a wonderful coloring for the corresponding test case.

Each wonderful coloring must be printed as a sequence of $n$ integers $c_1, c_2, \dots, c_n$ ($0 \le c_i \le k$) separated by spaces where

• $c_i=0$, if $i$-th element isn't painted;
• $c_i \gt 0$, if $i$-th element is painted in the $c_i$-th color.

Remember that you need to maximize the total count of painted elements for the wonderful coloring. If there are multiple solutions, print any one.

输出 $t$ 行，每行必须包含对应测试用例的一个“精彩染色”方案的描述。

每个“精彩染色”方案需以一个由 $n$ 个整数 $c_1, c_2, \dots, c_n$（其中 $0 \le c_i \le k$）组成的序列形式输出，各整数之间用空格分隔，满足：

• 若第 $i$ 个元素未被染色，则 $c_i = 0$；
• 若第 $i$ 个元素被染成第 $c_i$ 种颜色，则 $c_i > 0$。

注意：你需要使“精彩染色”方案中被染色元素的总数最大化。若存在多种可行方案，输出任意一种即可。

In the first test case, the answer is shown in the figure in the statement. The red color has number $1$, the blue color — $2$, the green — $3$.

在第一个测试用例中，答案如题目陈述中的图所示。红色对应数字 $1$，蓝色对应数字 $2$，绿色对应数字 $3$。