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: // package com.company
  
  /*
   * @author :: Yuvraj Singh
   * CS UNDERGRAD AT IT GGV BILASPUR
   */
  
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.*;
  
  import static java.lang.Math.*;
  import static java.lang.System.out;
  import static java.lang.Long.MAX_VALUE;
  
  public final class Main {
  
      FastReader in;
      StringBuffer sb;
      public static void main(String[] args) {
          new Main().run();
      }
  
      void run(){
          in= new FastReader();
          start();
      }
  
      void start(){
          sb= new StringBuffer();
          for(int t=in.nextInt();t>0;t--)
              solve();
          out.print(sb);
      }
  
      void solve(){
          int n= in.nextInt();
          int k= in.nextInt();
          int[] arr = new int[n];
          for(int i=0;i<n;i++)
              arr[i]= in.nextInt();
          HashMap<Integer,Integer> mp = new HashMap<>();
          for(int i : arr) {
              mp.put(i,mp.getOrDefault(i,0)+1);
          }
          Set<Integer> x = mp.keySet();
          HashMap<Integer,Integer> xk = new HashMap<>();
          HashMap<Integer,Integer> pk = new HashMap<>();
          int cnt = 0;
          for(int i : x) {
              int y = mp.get(i);
              if(y>=k) {
                  xk.put(i,k);
              }
              else {
                  pk.put(i,y);
                  cnt+=y;
              }
          }
          int h = cnt%k;
          cnt-=h;
          HashMap<Integer,Stack<Integer> > hk = new HashMap<>();
          for(int i : pk.keySet()) {
              hk.put(i,new Stack<Integer>());
              hk.get(i).add(0);
          }
          for(int i : pk.keySet()) {
              if(cnt>0) {
                  int y = pk.get(i);
                  while( cnt > 0&&y>0) {
                      hk.get(i).add((cnt%k)+1);
                      y--;
                      cnt--;
                  }
              }
              else
                  break;
          }
          StringBuffer ans = new StringBuffer();
          for(int i : arr) {
              if(xk.containsKey(i)) {
                  int j = xk.get(i);
                  if(j>0) {
                      ans.append(j+" ");
                      xk.put(i,j-1);
                  }
                  else
                      ans.append(0+" ");
              }
              else {
                  if(hk.get(i).peek() != 0) {
                      int ha =hk.get(i).pop();
                      ans.append(ha+" ");
                  }
                  else
                      ans.append(0+" ");
              }
          }
          sb.append(ans).append("\n");
      }
  
      long power(long x, long y, long p) {
          long res = 1;
          x = x % p;
          while (y > 0) {
              if (y % 2 == 1)
                  res = (res * x) % p;
  
              y = y >> 1;
              x = (x * x) % p;
          }
          return res;
      }
  
      int upper_bound(long[] arr, int key) {
          int i=0, j=arr.length-1;
          if (arr[j]<=key) return j+1;
          if(arr[i]>key) return i;
          while (i<j){
              int mid= (i+j)/2;
              if(arr[mid]<=key){
                  i= mid+1;
              }else{
                  j=mid;
              }
          }
          return i;
      }
  
      void sort(long[] A){
          int n = A.length;
          Random rnd = new Random();
          for(int i=0; i<n; ++i){
              long tmp = A[i];
              int randomPos = i + rnd.nextInt(n-i);
              A[i] = A[randomPos];
              A[randomPos] = tmp;
          }
          Arrays.sort(A);
      }
  
      long[] longArr(int n){
          long[] res= new long[n];
          for(int i=0;i<n;i++){
              res[i]= in.nextLong();
          }
          return res;
      }
  
      // sieve of eratosthenes code for precomputing whether numbers are prime or not up to MAX_VALUE
      long MAX= MAX_VALUE;
      int[] precomp= new int[(int) (MAX+1)];
      void sieve(){
          long n= MAX;
          boolean[] prime = new boolean[(int) (n+1)];
          for(int i=0;i<=n;i++)
              prime[i] = true;
  
          for(long p = 2; p*p <=n; p++)
          {
              // If prime[p] is not changed, then it is a prime
              if(prime[(int) p])
              {
                  // Update all multiples of p
                  for(long i = p*p; i <= n; i += p)
                      prime[(int) i] = false;
              }
          }
  
          // Print all prime numbers
          for(long i = 2; i <= n; i++)
          {
              if(prime[(int) i])
                  precomp[(int) i]= 1;
          }
      }
  
      boolean isDigitSumPalindrome(long N) {
          // code here
          long sum= sumOfDigits(String.valueOf(N));
          long rev=0;
          long org= sum;
          while (sum!=0){
              long d= sum%10;
              rev = rev*10 +d;
              sum /= 10;
          }
          return org == rev;
      }
  
      long sumOfDigits(String n){
          long sum= 0;
          for (char c: n.toCharArray()){
              sum += Integer.parseInt(String.valueOf(c));
          }
          return sum;
      }
  
      long[] revArray(long[] arr) {
          int n= arr.length;
          int i=0, j=n-1;
          while (i<j){
              long temp= arr[i];
              arr[i]= arr[j];
              arr[j]= temp;
              i++;
              j--;
          }
          return arr;
      }
  
      long gcd(long a, long b){
          if (b==0)
              return a;
          return gcd(b, a%b);
      }
      long lcm(long a,long b){
          return (a*b)/gcd(a,b);
      }
  
      static class Pair{
          long first;
          long second;
          Pair(long x,long y){
              this.first=x;
              this.second=y;
          }
      }
  
      static class Compare {
          static void compare(ArrayList<Pair> arr, long n) {
              arr.sort(new Comparator<Pair>() {
                  @Override
                  public int compare(Pair p1, Pair p2) {
                      return (int) (p2.first - p1.first);
                  }
              });
          }
      }
  
      public static class FastReader{
          BufferedReader br;
          StringTokenizer st;
          public FastReader(){
              br=new BufferedReader(new InputStreamReader(System.in));
          }
          String next(){
              while (st==null || !st.hasMoreElements()){
                  try{
                      st=new StringTokenizer(br.readLine());
                  }catch (Exception e){
                      e.printStackTrace();
                  }
              }
              return st.nextToken();
          }
          int nextInt(){
              return Integer.parseInt(next());
          }
          long nextLong(){
              return Long.parseLong(next());
          }
          double nextDouble(){
              return Double.parseDouble(next());
          }
          float nextFloat(){
              return Float.parseFloat(next());
          }
          String nextLine(){
              String str="";
              try{
                  str=br.readLine();
              }catch (Exception e){
                  e.printStackTrace();
              }
              return str;
          }
      }
  }