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 

//package com.company;

import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;
import java.math.BigDecimal;
import java.math.MathContext;
import java.math.RoundingMode;
import java.util.*;
import java.io.*;
//import javafx.util.Pair;

public class Main
{

    @Retention(RetentionPolicy.RUNTIME)
    @Target({ElementType.PARAMETER})
    public @interface NamedArg {
        String value();

        String defaultValue() default "";
    }
    public static class Pair<K, V> implements Serializable {

        private K key;
        private V value;

        public K getKey() {
            return this.key;
        }

        public V getValue() {
            return this.value;
        }

        public Pair(@NamedArg("key") K var1, @NamedArg("value") V var2) {
            this.key = var1;
            this.value = var2;
        }

        public String toString() {
            return this.key + "=" + this.value;
        }

        public int hashCode() {
            byte var1 = 7;
            int var2 = 31 * var1 + (this.key != null ? this.key.hashCode() : 0);
            var2 = 31 * var2 + (this.value != null ? this.value.hashCode() : 0);
            return var2;
        }

        public boolean equals(Object var1) {
            if (this == var1) {
                return true;
            } else if (!(var1 instanceof Pair)) {
                return false;
            } else {
                Pair var2 = (Pair)var1;
                if (this.key != null) {
                    if (!this.key.equals(var2.key)) {
                        return false;
                    }
                } else if (var2.key != null) {
                    return false;
                }

                if (this.value != null) {
                    if (!this.value.equals(var2.value)) {
                        return false;
                    }
                } else if (var2.value != null) {
                    return false;
                }

                return true;
            }
        }
    }

    private static class FastReader implements Closeable {
        private static final byte B_SP = ' ';
        private static final byte B_CR = '\r';
        private static final byte B_LF = '\n';
        private static final byte B_0 = '0';
        private static final byte B_9 = '9';
        private static final byte B_DASH = '-';

        private final InputStream in;
        private byte prev;


        public FastReader(InputStream in) {
            this.in = in;

        }


        public byte read() throws IOException {
            return (prev = (byte) in.read());
        }

        public byte readNonWs() throws IOException {
            byte b;
            do {
                b = read();
            } while (b <= B_SP);
            return b;
        }

        public int readInt() throws IOException {
            byte b = readNonWs();
            final boolean neg = (b == B_DASH);
            if (neg) {
                b = read();
            }
            int i = (b - B_0);
            b = read();
            while (b >= B_0 && b <= B_9) {
                i = i * 10 + (b - B_0);
                b = read();
            }
            return neg ? -i : i;
        }

        public long readLong() throws IOException {
            byte b = readNonWs();
            final boolean neg = (b == B_DASH);
            if (neg) {
                b = read();
            }
            long i = (b - B_0);
            b = read();
            while (b >= B_0 && b <= B_9) {
                i = i * 10 + (b - B_0);
                b = read();
            }
            return neg ? -i : i;
        }

        public int readToken(byte[] tbuf) throws IOException {
            byte b = readNonWs();
            int i = 0;
            do {
                tbuf[i++] = b;
                b = read();
            } while (b >= B_SP);
            return i;
        }

        public int readLine(byte[] lbuf) throws IOException {
            byte b;
            if (prev == B_CR) {
                b = read();
                if (b == B_LF) {
                    b = read();
                }
            } else {
                b = read();
            }
            int i = 0;
            while (b >= B_SP) {
                lbuf[i++] = b;
                b = read();
            }
            return i;
        }

        @Override
        public void close() throws IOException {
            in.close();
        }
    }
    private static final Random rng = new Random();

    private static void shuffle(long[] arr, int lo, int hi) {
        int k = hi - lo;
        for (int i = hi-1; i > lo; i--) {
            int j = lo + rng.nextInt(k--);
            long tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
    public static int[][][] dp;
    public static class myPair{
        int k;
        int v;
        myPair(int mk,int mv)
        {
            k=mk;
            v=mv;

        }

        public int getK() {
            return k;
        }

        public int getV() {
            return v;
        }
    }
   // public static long max;
    public static void main(String args[])throws IOException
    {
        //max = 0;
        PrintWriter out=new PrintWriter(System.out);
        FastReader scanner = new FastReader(System.in);

       int t = scanner.readInt();

        while (t-->0)
        {
           int n=scanner.readInt();
           int k=scanner.readInt();
           int[] arr = new int[n];
           for(int i =0; i < n; i ++)
               arr[i]=scanner.readInt();

           Map<Integer,List<Integer>> map = new HashMap<>();
           for(int i =0; i < arr.length;i++)
           {
               map.putIfAbsent(arr[i],new ArrayList<>());
               map.get(arr[i]).add(i);
           }

           List<Integer> r = new ArrayList<>();


           for(Map.Entry<Integer,List<Integer>> entry : map.entrySet())
            {
                r.add(entry.getValue().size());
            }
           Collections.sort(r);
           int[] presum = new int[r.size()];

           presum[0] = r.get(0);
           for(int i =1; i < presum.length;i++)
               presum[i]= presum[i-1]+r.get(i);


           int max = Integer.MIN_VALUE;
           int maxc = -1;
           for(int i = 1; i <= k; i++)
           {
               int start = -1;
               int end = r.size();
               int sol = -1;
               while(start+1<end)
               {
                   int mid = start + (end-start)/2;
                   if(r.get(mid)>=i)
                   {
                       sol = mid;
                       end = mid;

                   }else start = mid;
               }

               int total = sol == -1 ? (presum[presum.length-1]-presum[presum.length-1]%i) : (r.size()-sol)*i+(sol>0?(presum[sol-1]-presum[sol-1]%i):0);
               if(sol !=-1 && total >= max)
               {
                   max = total;
                   maxc = i;
               }
           }

           int c = 1;
           int colored =0;
           for(Map.Entry<Integer,List<Integer>> entry : map.entrySet())
           {
               int j =0;
               for(; j <Math.min(maxc,entry.getValue().size())&&colored<max; j++)
               {
                   arr[entry.getValue().get(j)] = c%maxc==0?maxc:c%maxc;
                   c++;
                   colored++;
               }
               for(; j < entry.getValue().size();j++)
                   arr[entry.getValue().get(j)]=0;
           }

           for(int i =0; i<arr.length;i++)
           out.print(arr[i]+" ");
           out.println();



        }



        out.close();

    }


    private static final BigDecimal SQRT_DIG = new BigDecimal(15);
    private static final BigDecimal SQRT_PRE = new BigDecimal(10).pow(SQRT_DIG.intValue());

    /**
     * Private utility method used to compute the square root of a BigDecimal.
     *
     * @author Luciano Culacciatti
     * @url http://www.codeproject.com/Tips/257031/Implementing-SqrtRoot-in-BigDecimal
     */
    private static BigDecimal sqrtNewtonRaphson  (BigDecimal c, BigDecimal xn, BigDecimal precision){
        BigDecimal fx = xn.pow(2).add(c.negate());
        BigDecimal fpx = xn.multiply(new BigDecimal(2));
        BigDecimal xn1 = fx.divide(fpx,2*SQRT_DIG.intValue(), RoundingMode.HALF_DOWN);
        xn1 = xn.add(xn1.negate());
        BigDecimal currentSquare = xn1.pow(2);
        BigDecimal currentPrecision = currentSquare.subtract(c);
        currentPrecision = currentPrecision.abs();
        if (currentPrecision.compareTo(precision) <= -1){
            return xn1;
        }
        return sqrtNewtonRaphson(c, xn1, precision);
    }

    /**
     * Uses Newton Raphson to compute the square root of a BigDecimal.
     *
     * @author Luciano Culacciatti
     * @url http://www.codeproject.com/Tips/257031/Implementing-SqrtRoot-in-BigDecimal
     */
    public static BigDecimal bigSqrt(BigDecimal c){
        return sqrtNewtonRaphson(c,new BigDecimal(1),new BigDecimal(1).divide(SQRT_PRE));
    }

    public static long bt(long x, long y, long a, long b, long exp)
    {
        if(x>=y) return exp-1;
        if(x*a<x+b)
            return bt(x*a,y,a,b,exp+1);
        else
            return (y-x)/b +exp - ((y-x)%b==0?1:0);

    }


}


