Эта задача является продолжением задачи «Чудесная раскраска - 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\) строк, каждая строка содержит описание возможной чудесной раскраски для соответствующего набора входных данных.
Каждая чудесная раскраска должна быть выведена в виде \(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\), синий имеет номер \(2\), зелёный — номер \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
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 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
|