## Wonderful Coloring – 2 solution codeforces

Table of Contents

**Solution **

**Coming Soon**

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 a1,a2,…,ana1,a2,…,an. They want to paint it using pieces of chalk of kk colors. The coloring of a sequence is called wonderful if the following conditions are met:

- each element of the sequence is either painted in one of kk colors or isn’t painted;
- 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);
- let’s calculate for each of kk colors the number of elements painted in the color — all calculated numbers must be equal;
- 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]a=[3,1,1,1,1,10,3,10,10,2] and k=3k=3. One of the wonderful colorings of the sequence is shown in the figure.

The first line contains one integer tt (1≤t≤100001≤t≤10000) — the number of test cases. Then tt test cases follow.

Each test case consists of two lines. The first one contains two integers nn and kk (1≤n≤2⋅1051≤n≤2⋅105, 1≤k≤n1≤k≤n) — the length of a given sequence and the number of colors, respectively. The second one contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤n1≤ai≤n).

It is guaranteed that the sum of nn over all test cases doesn’t exceed 2⋅1052⋅105.

Output tt 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 nn integers c1,c2,…,cnc1,c2,…,cn (0≤ci≤k0≤ci≤k) separated by spaces where

- ci=0ci=0, if ii-th element isn’t painted;
- ci>0ci>0, if ii-th element is painted in the cici-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.

input

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

output

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

In the first test case, the answer is shown in the figure in the statement. The red color has number 11, the blue color — 22, the green — 33.