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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;


public class B {
	
	static int mod =1000000007; 
	
	public static void main(String[] args) throws Exception {
		PrintWriter out=new PrintWriter(System.out);
	    FastScanner fs=new FastScanner();
	    int te=fs.nextInt();
	   outer: while(te-->0) {
		   int n=fs.nextInt(), k=fs.nextInt();
		   int arr[]=fs.readArray(n);
		   Map<Integer,List<Integer>> map=new HashMap<>();
		   for(int i=0;i<n;i++) {
			   if(!map.containsKey(arr[i])) map.put(arr[i], new ArrayList<>());
			   map.get(arr[i]).add(i);
		   }
		   int res[]=new int[n];
		   int curclr=1;
		   for(Map.Entry<Integer, List<Integer>> e:map.entrySet()) {
			   List<Integer> temp=e.getValue();
			   for(int i=0;i<Math.min(k,temp.size());i++) {
				   res[temp.get(i)]=curclr;
				   curclr++;
				   if(curclr==k+1) curclr=1;
			   }
		   }
		   Set<Integer> set=new HashSet<>();
		   for(int i=1;i<curclr;i++) set.add(i);
		   for(int i=0;i<n;i++) {
			   if(set.contains(res[i])) {
				   set.remove(res[i]);
				   res[i]=0;  
			   }
			   out.print(res[i]+" ");
		   }
		   out.println();
		   
	   }
	    out.close();
	}
	static void rev(char arr[]) {
		int i=0,j=arr.length-1;
		while(i<j) {
			char temp=arr[i];
			arr[i]=arr[j];
			arr[j]=temp;
			i++; j--;
		}
	}
	
	static long gcd(long  a,long  b) {
		if(b==0) return a;
		return gcd(b,a%b);
	}
	static long nck(int n,int k) {
		if(k>n) return 0;
		long res=1;
		res*=fact(n);
		res%=mod;
		res*=modInv(fact(k));
		res%=mod;
		res*=modInv(fact(n-k)); 
		res%=mod;
		return res;
	}
	static long fact(long n) {
		long res=1;
		for(int i=2;i<=n;i++) {
			res*=i;
			res%=mod;
		}
		return res;
	}
	static long pow(long a,long b) {
		long res=1;
		while(b!=0) {
			if((b&1)!=0) {
				res*=a;
				res%=mod;
			}
			a*=a;
			a%=mod;
			b=b>>1;
		}
		return res;
	}
	static long modInv(long n) {
		return pow(n,mod-2);
	}
	
	static void sort(int[] a) {
		//suffle
		int n=a.length;
		Random r=new Random();
		for (int i=0; i<a.length; i++) {
			int oi=r.nextInt(n);
			int temp=a[i];
			a[i]=a[oi];
			a[oi]=temp;
		}
		
		//then sort
		Arrays.sort(a);
	}
	
	// Use this to input code since it is faster than a Scanner
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
 
}