description: 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.
solution: 
   //   * * * the goal is to be worlds best * * *   //
   import java.io.BufferedReader;
   import java.io.IOException;
   import java.io.InputStreamReader;
   import java.util.*;
  
  
    
   
   public class C {
       static class Pair implements Comparable<Pair>{
           int a;
           int b;
   
           Pair(int a , int b){
               this.a = a;
               this.b = b;
           }
   
           public int compareTo(Pair o){
               return this.a - o.a;
           }
       }
   
   //==================================================================================================
       static class CC implements Comparator<Pair>{
           public int compare(Pair one , Pair two){
               return two.a - one.a;
           }
       }
       public static void main(String[] args) {
          FastScanner sc = new FastScanner();
          int t = sc.nextInt();
          while(t-->0){
              int n = sc.nextInt();
              int k = sc.nextInt();
  
              int a[] = sc.readArray(n);
  
              // Pair pa[] = new Pair[n];
  
              // for(int i = 0; i < n; i++){
              //     pa[i] = new Pair(a[i] , i);
              // }
              // Map<Integer , Integer> map = new HashMap<>();
              // PriorityQueue<Pair> pq = new PriorityQueue<>(new CC());
              
              // for(int i = 1; i <= k; i++){
              //     pq.add(new Pair(k , i));
              // }
  
              HashMap<Integer , Integer> map = new HashMap<>();
              HashSet<Integer> set = new HashSet<>();
  
              ArrayList<Integer> b[] = new ArrayList[2 * 1000_00 + 1];
              for(int i = 0; i < n + 1; i++){
                  b[i] = new ArrayList<>();
              }
             
              for(int i = 0; i < n; i++){
                  set.add(a[i]);
                  b[a[i]].add(i);
                  map.put(a[i] , map.getOrDefault(a[i], 0) + 1);
              }
  
              int c[] = new int[n];
  
              ArrayList<Integer> al = new ArrayList<>();
  
              for(int e : set){
                  if(map.get(e) >= k){
                      for(int i = 0; i < k; i++){
                          c[b[e].get(i)] = i + 1;
                      }
                  }
                  else{
                      for(int f : b[e]){
                          al.add(f);
                      }
                  }
              }
  
              // for(int i = 0; i < n; i++)[
              //     set.put(a[i] , new HashSet<>());
              // ]
              // for(Pair p : pa){
              //     map.put(p.a , map.getOrDefault(p.a , 0) + 1);
              //     if(map.get(p.a) <= k){
              //         while(set[p.a].contains)
              //         Pair ppp = pq.poll();
              //         pq.add(new Pair(ppp.a - 1, ppp.b));
              //         a[p.b] = ppp.b;
              //     }
              //     else{
              //         a[p.b] = 0;
              //     }
              // }
              
              int sz = (al.size() / k) * k;
              int temp = 1;
              // // System.out.println("RESULT");
              // for(int e : a){
              //     System.out.print(e + " ");
              // }
              // System.out.println();
  
              for(int i = 1; i < sz + 1; i++){
                  if((i - 1) % k == 0){
                      temp = 1;
                  }
  
                  c[al.get(i - 1)] = temp;
                  temp++;
              }
  
              // System.out.println("RESULT");
              print(c);
          }
       }
   
   //==================================================================================================
   
   
       // Use this instead of Arrays.sort() on an array of ints. Arrays.sort() is n^2
       // worst case since it uses a version of quicksort. Although this would never
       // actually show up in the real world, in codeforces, people can hack, so
       // this is needed. 
  	 static void sort(int[] arr) {
  		 int n = arr.length;
  		 ArrayList<Integer> res = new ArrayList<>();
  		 for (int a : arr) {
  		 	 res.add(a);
  		 }
  		 Collections.sort(res);
  		 for (int i = 0; i < n; i++) {
  			 arr[i] = res.get(i);
  		 }
  	 }
   
  	 static void sort(long[] arr) {
  		 int n = arr.length;
  		 ArrayList<Long> res = new ArrayList<>();
  		 for (long a : arr) {
  			 res.add(a);
  		 }
  		 Collections.sort(res);
  		 for (int i = 0; i < n; i++) {
  			 arr[i] = res.get(i);
  		} 
  	 }
   
  	 static void revSort(int[] arr) {
  		 int n = arr.length;
  		 ArrayList<Integer> res = new ArrayList<>();
  		 for (int a : arr) {
  			 res.add(a);
  		 }
  		 Collections.sort(res, Collections.reverseOrder());
  		 for (int i = 0; i < n; i++) {
  			 arr[i] = res.get(i);
  		 }
  	 } 
       
       // 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());
           }
   
           double nextDouble() {
               return Double.parseDouble(next());
           }
    
           String str = "";
    
           String nextLine() {
               try {
                   str = br.readLine();
               } catch (IOException e) {
                   e.printStackTrace();
               }
               return str;
           }
    
           int[] readArray(int n) {
               int[] a = new int[n];
               for (int i = 0; i < n; i++)
                   a[i] = nextInt();
               return a;
           }
    
           long[] readLongArray(int n) {
               long[] a = new long[n];
               for (int i = 0; i < n; i++)
                   a[i] = nextLong();
               return a;
           }
           long nextLong() {
               return Long.parseLong(next());
           }
       }
       
       // print integers in array
       static void print(int a[]){
           for(int e : a){
               System.out.print(e + " ");
           }
           System.out.println();
       }
  
       static void print(long a[]){
           for(long e : a){
               System.out.print(e + " ");
           }
           System.out.println();
       }
  
       // generates all the prime numbers upto n
       static void sieveOfEratosthenes(int n , ArrayList<Integer> al)
       {
           boolean prime[] = new boolean[n + 1];
           for (int i = 0; i <= n; i++)
               prime[i] = true;
    
           for (int p = 2; p * p <= n; p++) 
           {
               if (prime[p] == true) 
               {
                   for (int i = p * p; i <= n; i += p)
                       prime[i] = false;
               }
           }
           for (int i = 2; i <= n; i++)
           {
               if (prime[i] == true)
                   al.add(i);
           }
       }
       static final int mod = 1000_000_000 + 7;
       static final int imx = Integer.MAX_VALUE;
       static final int imi = Integer.MIN_VALUE;
       
  	 static ArrayList<Integer> divisors(int n) {
  		 ArrayList<Integer> al = new ArrayList<>();
  		 for (int i = 1; i * i <= n; i++) {
  			 if (n % i == 0) {
  				 if (n == i * i) {
  					 al.add(i);
  				 } else {
  					 al.add(i);
  					 al.add(n / i);
  				 }
  		 	 }
  		 }
  		 Collections.sort(al);
  		 return al;
  	 }
   
  	 static int countDigits(int n) {
  		 int c = 0;
  		 while (n != 0) {
  			 c++;
  			 n /= 10;
  		 }
  		 return c;
  	 }
   
  	 static boolean palindrome(String str) {
  		 int s = 0;
  		 int e = str.length() - 1;
  		 while (s < e) {
  			 if (str.charAt(s) != str.charAt(e)) {
  				 return false;
  			 }
  			 s++;
  			 e--;
  		 }
  		 return true;
  	 }
   
  	 static void reverse(int[] arr, int s, int e) {
  		 while (s < e) {
  			 int temp = arr[s];
  			 arr[s++] = arr[e];
  			 arr[e--] = temp;
  		 }
  	 }
       // starting exclusive ending inclusive
  	 static int getMax(int[] arr, int s, int e) {
  		 int maxi = s;
  		 for (int i = s + 1; i <= e; i++) {
  			 if (arr[i] > arr[maxi]) {
  				 maxi = i;
  			 }
  		 }
  		 return maxi;
  	 }
  
       // starting exclusive ending inclusive
       static int getMin(int[] arr, int s, int e) {
  	     int mini = s;
  		 for (int i = s + 1; i <= e; i++) {
  			 if (arr[i] < arr[mini]) {
  				 mini = i;
  			 }
  		 }
  		 return mini;
  	 }
   
  	 static long lcm(long n1, long n2) {
  		 return (n1 * n2) / gcd(n1, n2);
   	 }
   
  	 static int lcm(int n1, int n2) {
  		 return (n1 * n2) / gcd(n1, n2);
  	 }
   
  	 static long gcd(long num1, long num2) {
  		 if (num2 == 0) {
  			 return num1;
  		 }
  		 return gcd(num2, num1 % num2);
  	 }
   
  	 static int gcd(int num1, int num2) {
  		 if (num2 == 0) {
  			 return num1;
  		 }
  		 return gcd(num2, num1 % num2);
  	 }
  
       //fastPow
       static long fastPow(long base, long exp) {
           if (exp==0) return 1;
           long half=fastPow(base, exp/2);
           if (exp%2==0) return mul(half, half);
           return mul(half, mul(half, base));
       }
   
       // multiply two long numbers % mod
       static long mul(long a, long b) {
           return a*b%mod;
       }
   
       static int nCr(int n, int r)
       {
          return factorial(n) / (factorial(r) *
              factorial(n - r));
       }
       
       // Returns factorial of n
       static int factorial(int n)
       {
           int res = 1;
           for (int i = 2; i <= n; i++)
               res = res * i;
           return res;
       }
        
       // to generate the lps array
       // lps means longest preffix that is also a suffix
       static void generateLPS(int lps[] , String p){
           int l = 0;
           int r = 1;
      
           while(l < p.length() && l < r && r < p.length()){
               if(p.charAt(l) == p.charAt(r)){
                   lps[r] = l + 1;
                   l++;
                   r++;
               }
               else{
                   if(l > 0)
                       l = lps[l - 1];
                   else
                       r++;    
               }
           }
       }
        
       // returns the index of the element which is just smaller than or
       // equal to the tar in the given arraylist 
       static int lowBound(ArrayList<Integer> ll,long tar ,int l,int r){
           if(l>r) return l;
   
           int mid=l+(r-l)/2;
   
           if(ll.get(mid)>=tar){
               return lowBound(ll,tar,l,mid-1);
           }
   
           return lowBound(ll,tar,mid+1,r);
       }
   
       // returns the index of the element which is just greater than or
       // equal to the tar in the given arraylist 
       static int upBound(ArrayList<Integer> ll,long tar,int l ,int r){
           if(l>r) return l;
   
           int mid=l+(r-l)/2;
   
           if(ll.get(mid)<=tar){
               return upBound(ll,tar,mid+1 ,r);
           }
   
           return upBound(ll,tar,l,mid-1);
       }
   
       static void swap(int a[] , int i , int j){
           int x = a[i];
           int y = a[j];
           a[j] = x;
           a[i] = y;
       }
       static void swap(long a[] , int i , int j){
           long x = a[i];
           long y = a[j];
           a[j] = x;
           a[i] = y;
      }
       // a -> z == 97 -> 122
   
       // String.format("%.9f", ans) ,--> to get upto 9 decimal places , (ans is double)
       
       // write 
   }
   