CF1551B2 Wonderful Coloring - 2

本题是题目“Wonderful Coloring - 1”的扩展版，与原题有较多不同，请务必完整阅读题面。 最近，Paul 和 Mary 找到了一个新的最喜欢的整数序列 $a_1, a_2, \dots, a_n$。他们想用 $k$ 种颜色的粉笔来给这个序列涂色。一个序列的涂色被称为“美妙涂色”，当且仅当满足以下条件： 1. 序列中的每个元素要么被涂上 $k$ 种颜色中的某一种，要么不被涂色； 2. 被涂成同一种颜色的任意两个元素必须不同（即不存在两个相等的数被涂成同一种颜色）； 3. 对于每一种颜色，统计被涂成该颜色的元素个数——所有颜色的这个数必须相等； 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$ 的一种美妙涂色方案。

第一行包含一个整数 $t$（$1 \le t \le 10000$），表示测试用例的数量。接下来有 $t$ 组测试用例。 每组测试用例包含两行。第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^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$，用空格分隔，其中： - 如果第 $i$ 个元素未被涂色，则 $c_i=0$； - 如果第 $i$ 个元素被涂成第 $c_i$ 种颜色，则 $c_i>0$。 请注意，你需要最大化被涂色的元素总数。如果有多种方案，输出任意一种均可。

在第一个测试用例中，答案如题面中的图片所示。红色为颜色 $1$，蓝色为颜色 $2$，绿色为颜色 $3$。 由 ChatGPT 4.1 翻译