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 a_1, a_2, ..., a_n. They want to paint it using pieces of chalk of k 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 k 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 k 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] and k=3. One of the wonderful colorings of the sequence is shown in the figure.

<image> The example of a wonderful coloring of the sequence a=[3, 1, 1, 1, 1, 10, 3, 10, 10, 2] and k=3. Note that one of the elements isn't painted.

Help Paul and Mary to find a wonderful coloring of a given sequence a.

Input

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

Each test case consists of two lines. The first one contains two integers n and k (1 ≤ n ≤ 2⋅10^5, 1 ≤ k ≤ n) — the length of a given sequence and the number of colors, respectively. The second one contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ n).

It is guaranteed that the sum of n over all test cases doesn't exceed 2 ⋅ 10^5.

Output

Output t 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 n integers c_1, c_2, ..., c_n (0 ≤ c_i ≤ k) separated by spaces where

  * c_i=0, if i-th element isn't painted; 
  * c_i>0, if i-th element is painted in the c_i-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


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

Note

In the first test case, the answer is shown in the figure in the statement. The red color has number 1, the blue color — 2, the green — 3.
12
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
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
 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

2 1 2 3 0 1 3 2 3 1 
1 2 3 4 
1 
1 1 1 0 1 1 1 1 0 0 0 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 
2 1 2 3 0 1 3 2 3 1 
1 2 3 4 
1 
1 1 1 0 1 1 1 1 0 0 0 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 
 2 1 2 3 0 1 3 2 3 1 
1 2 3 4 
1 
1 1 1 0 1 1 1 1 0 0 0 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 

import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class codeforce {

    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(
                    new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') {
                    if (cnt != 0) {
                        break;
                    }
                    else {
                        continue;
                    }
                }
                buf[cnt++] = (byte)c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0,
                    BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }
    static int mod = (int) (1e9 + 7);

    public static class pair implements Comparator<pair> {
        int x;
        int y;

        public pair() {

        }

        public pair(int x, int y) {
            this.x = x;
            this.y = y;

        }

        @Override
        public int compare(pair o1, pair o2) {
            return o1.y - o2.y;
        }
    }
    public static long modularpow(long a,long b){
        long res=1;
        if(b==0)
            return res;
        else
        {
            while(b>0){
                if(b%2==1){
                    res*=a;
                    res%=mod;

                }
                a=a*a;
                a%=mod;
                b/=2;
            }
            return res%mod;
        }
    }
    public static int gcd(int a,int b){
        if(b==0)
            return a;
        else
            return gcd(b,a%b);
    }
    public static String binary(int a){
        String s1="";
        while(a>0){
            s1=a%2+s1;
            a/=2;
        }
        return s1;
    }
    public static int Lower_Bound(long a[],int l,int r,long k){


        while(r-l>1){
            int mid=l+(r-l)/2;
            if(a[mid]<=k) l=mid;
            else
                r=mid;

        }
        return l;
    }
    public static int Upper_Bound(int a[],int l,int r,int k){

        while(r-l>1){
            int mid=(l+r)/2;
            if(a[mid]<=k)
                l=mid;
            else
                r=mid;
        }
        return l+1;
    }
    public static void main(String arg[]) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter sb = new BufferedWriter(
                new OutputStreamWriter(System.out));
        int t=Integer.parseInt(br.readLine());
        while(t-->0){
            String s[]=br.readLine().split(" ");
            int n=Integer.parseInt(s[0]);
            int k=Integer.parseInt(s[1]);
            s=br.readLine().split(" ");
            int a[]=new int[n];
            for(int i=0;i<n;i++)
                a[i]=Integer.parseInt(s[i]);
            int b[]=new int[k+1];
            int c[]=new int[n];
            Map<Integer,ArrayList<Integer>>mp=new HashMap<Integer,ArrayList<Integer>>();
            for(int i=0;i<n;i++){
                ArrayList<Integer>ar;
                if(mp.containsKey(a[i])){
                    ar=mp.get(a[i]);
                    ar.add(i);
                    mp.put(a[i],ar);
                }
                else {
                    ar=new ArrayList<>();
                    ar.add(i);
                    mp.put(a[i], ar);
                }
            }
            Set<Integer>st=new HashSet<Integer>();
            Set<Integer>st1=new HashSet<Integer>();
            int k2=0;
            for(Map.Entry<Integer,ArrayList<Integer>>e:mp.entrySet()){
                int key=e.getKey();
                int val=e.getValue().size();
                if(val>=k){
                    st.add(key);
                }
                else{
                    k2+=val;
                    st1.add(key);
                }
            }
            int re=k2/k;
            Arrays.fill(b,re);
            for(int e:st){
                ArrayList<Integer>ar=mp.get(e);
                for(int i=0;i<k;i++){
                    c[ar.get(i)]=i+1;
                }
                mp.remove(e);
            }

            int j=1;
            for(int e:st1){


                ArrayList<Integer>ar=mp.get(e);
                for(int i:ar){

                    if(j%k==0&&b[k]>0){

                        c[i]=k;
                        b[k]--;
                    }
                    else if(b[j%k]>0){
                        c[i]=j%k;
                        b[j%k]--;
                    }
                    j++;
                }
            }
            for(int i=0;i<n;i++)
                sb.write(c[i]+" ");
            sb.write("\n");
        }


        sb.flush();
    }
}
