| Codeforces Round 734 (Div. 3) |
|---|
| Закончено |
Эта задача является продолжением задачи «Чудесная раскраска - 1». Она имеет довольно много отличий, поэтому прочтите это условие полностью.
Совсем недавно у Паши и Маши появилась любимая последовательность чисел $$$a_1, a_2, \dots, a_n$$$. Они захотели и её раскрасить с помощью мелков $$$k$$$ цветов. Раскраска последовательности называется чудесной, если выполняются следующие условия:
- каждый элемент последовательности раскрашивается ровно в один из $$$k$$$ цветов, либо не раскрашивается вовсе;
- любые два элемента, раскрашенные в один цвет, различны (то есть нет двух одинаковых значений, которые раскрашены в один цвет);
- посчитаем для каждого из $$$k$$$ цветов количество элементов, раскрашенных этот цвет — все полученные количества должны быть равны;
- суммарное количество раскрашенных элементов при соблюдении первых трёх условий максимально возможно.
Например, пусть последовательность имеет вид $$$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$$$.
Помните, что в чудесной раскраске максимизируется суммарное количество раскрашенных элементов. Если существует несколько решений, выведите любое из них.
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 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$$$.
