Wonderful Coloring – 2 solution codeforces

Wonderful Coloring – 2 solution codeforces


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:

  1. each element of the sequence is either painted in one of kk 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 kk 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]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 example of a wonderful coloring of the 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. Note that one of the elements isn’t painted.
Help Paul and Mary to find a wonderful coloring of a given sequence aa.

Input

The first line contains one integer tt (1t100001≤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 (1n21051≤n≤2⋅1051kn1≤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 (1ain1≤ai≤n).

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

Output

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 (0cik0≤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.

Example

input

Copy
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

Copy
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
Note

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.


Solution

Coming Soon


Wonderful Coloring - 2 solution codeforcesXOR and Distance solution codeforces

Leave a Comment