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: import java.util.*;
  
  import java.io.*;
  
  public class cf2 {
    static Reader sc = new Reader();
    static PrintWriter out = new PrintWriter(System.out);
    static long mod = (long) 1e9 + 7;
  
    public static void main(String[] args) {
      int tc = sc.ni();
      while (tc-- > 0) {
        int n = sc.ni(), k = sc.ni();
        int[] arr = sc.nai(n);
        int[] freq = new int[n + 1];
        for (int e : arr) {
          freq[e]++;
        }
        HashSet<Integer> all = new HashSet<>();
        int rem = n;
        for (int key = 1; key <= n; key++) {
          if (freq[key] >= k) {
            all.add(key);
            rem -= freq[key];
          }
        }
  
        int count = rem / k, curr = 1;
  
        int[] val = new int[n + 1];
  
        for (int e : all) {
          val[e] = 1;
        }
        ArrayList<Integer>[] hm1 = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++)
          hm1[i] = new ArrayList<>();
        for (int i = 0; i < n; i++) {
          if (freq[arr[i]] == 0 || all.contains(arr[i]))
            continue;
          hm1[arr[i]].add(i);
        }
        Arrays.sort(hm1, (x, y) -> y.size() - x.size());
  
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
          if (all.contains(arr[i])) {
            if (val[arr[i]] <= k) {
              res[i] = val[arr[i]];
              val[arr[i]]++;
            }
          }
        }
  
        for (int i = 0; i <= n; i++) {
          if (hm1[i].size() > 0) {
            for (int idx : hm1[i]) {
              if (count > 0) {
                res[idx] = curr;
                curr++;
                if (curr > k) {
                  curr = 1;
                  count--;
                }
              }
            }
          }
        }
  
        for (int e : res)
          out.print(e + " ");
        out.println();
      }
      out.close();
  
    }
  
    public static long pow(long a, long b, long m) {
      if (b == 0) {
        return 1;
      }
      if (b % 2 == 0) {
        return pow((a * a) % m, b / 2, m) % m;
      } else {
        return (a * pow((a * a) % m, b / 2, m)) % m;
      }
    }
  
    // snippets
  
    static class Pair implements Comparable<Pair> {
      int x;
      int y;
  
      Pair(int x, int y) {
        this.x = x;
        this.y = y;
  
      }
  
      @Override
      public int compareTo(Pair o) {
        if (this.x > o.x)
          return 1;
        else if (this.x < o.x)
          return -1;
        else {
          if (this.y > o.y)
            return 1;
          else if (this.y < o.y)
            return -1;
          else
            return 0;
        }
      }
  
      public int hashCode() {
        int ans = 1;
        ans = x * 31 + y * 13;
        return ans;
      }
  
      @Override
      public boolean equals(Object o) {
        if (this == o) {
          return true;
        }
        if (o == null) {
          return false;
        }
        if (this.getClass() != o.getClass()) {
          return false;
        }
        Pair other = (Pair) o;
        if (this.x == other.x && this.y == other.y) {
          return true;
        }
        return false;
      }
  
    }
  
    static void add_map(HashMap<Integer, Integer> map, int v) {
      if (!map.containsKey(v)) {
        map.put(v, 1);
      } else {
        map.put(v, map.get(v) + 1);
      }
    }
  
    static void remove_map(HashMap<Integer, Integer> map, int v) {
      if (map.containsKey(v)) {
        map.put(v, map.get(v) - 1);
        if (map.get(v) == 0)
          map.remove(v);
      }
    }
  
    static int gcd(int a, int b) {
      if (b == 0)
        return a;
      return gcd(b, a % b);
    }
  
    static long gcd(long a, long b) {
      if (b == 0)
        return a;
      return gcd(b, a % b);
    }
  
    static void sort(int[] arr) {
      // shuffle
      Random rand = new Random();
      for (int i = 0; i < arr.length; i++) {
        int j = rand.nextInt(i + 1);
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
      }
      Arrays.sort(arr);
    }
  
    static void sort(long[] arr) {
      // shuffle
      Random rand = new Random();
      for (int i = 0; i < arr.length; i++) {
        int j = rand.nextInt(i + 1);
        long tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
      }
      Arrays.sort(arr);
    }
  
    static boolean isPrime(int n) {
      if (n <= 1)
        return false;
      if (n <= 3)
        return true;
      if (n % 2 == 0 || n % 3 == 0)
        return false;
      double sq = Math.sqrt(n);
  
      for (int i = 5; i <= sq; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
          return false;
      return true;
    }
  
    static boolean isPrime(long n) {
      if (n <= 1)
        return false;
      if (n <= 3)
        return true;
      if (n % 2 == 0 || n % 3 == 0)
        return false;
      double sq = Math.sqrt(n);
  
      for (int i = 5; i <= sq; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
          return false;
      return true;
    }
  
    static void print_arr(int A[]) {
      for (int i : A) {
        System.out.print(i + " ");
      }
      System.out.println();
    }
  
    static void print_arr(long A[]) {
      for (long i : A) {
        System.out.print(i + " ");
      }
      System.out.println();
    }
  
    static void print_arr(char A[]) {
      for (char i : A) {
        System.out.print(i + " ");
      }
      System.out.println();
    }
  
    static int min(int a, int b) {
      return Math.min(a, b);
    }
  
    static int min(int a, int b, int c) {
      return Math.min(a, Math.min(b, c));
    }
  
    static int min(int a, int b, int c, int d) {
      return Math.min(a, Math.min(b, Math.min(c, d)));
    }
  
    static int max(int a, int b) {
      return Math.max(a, b);
    }
  
    static int max(int a, int b, int c) {
      return Math.max(a, Math.max(b, c));
    }
  
    static int max(int a, int b, int c, int d) {
      return Math.max(a, Math.max(b, Math.max(c, d)));
    }
  
    static long min(long a, long b) {
      return Math.min(a, b);
    }
  
    static long min(long a, long b, long c) {
      return Math.min(a, Math.min(b, c));
    }
  
    static long min(long a, long b, long c, long d) {
      return Math.min(a, Math.min(b, Math.min(c, d)));
    }
  
    static long max(long a, long b) {
      return Math.max(a, b);
    }
  
    static long max(long a, long b, long c) {
      return Math.max(a, Math.max(b, c));
    }
  
    static long max(long a, long b, long c, long d) {
      return Math.max(a, Math.max(b, Math.max(c, d)));
    }
  
    static int max(int A[]) {
      int max = Integer.MIN_VALUE;
      for (int i = 0; i < A.length; i++) {
        max = Math.max(max, A[i]);
      }
      return max;
    }
  
    static int min(int A[]) {
      int min = Integer.MAX_VALUE;
      for (int i = 0; i < A.length; i++) {
        min = Math.min(min, A[i]);
      }
      return min;
    }
  
    static long max(long A[]) {
      long max = Long.MIN_VALUE;
      for (int i = 0; i < A.length; i++) {
        max = Math.max(max, A[i]);
      }
      return max;
    }
  
    static long min(long A[]) {
      long min = Long.MAX_VALUE;
      for (int i = 0; i < A.length; i++) {
        min = Math.min(min, A[i]);
      }
      return min;
    }
  
    static long sum(int A[]) {
      long sum = 0;
      for (int i : A) {
        sum += i;
      }
      return sum;
    }
  
    static long sum(long A[]) {
      long sum = 0;
      for (long i : A) {
        sum += i;
      }
      return sum;
    }
  
    static ArrayList<Integer> sieve(int n) {
      ArrayList<Integer> primes = new ArrayList<>();
      boolean[] isPrime = new boolean[n];
      Arrays.fill(isPrime, true);
      isPrime[0] = isPrime[1] = false;
      for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
          for (int j = i * i; j < n; j += i) {
            isPrime[j] = false;
          }
        }
      }
      for (int i = 2; i < n; i++) {
        if (isPrime[i])
          primes.add(i);
      }
      return primes;
    }
  
    static class Reader {
      BufferedReader br;
      StringTokenizer st;
  
      Reader() {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer("");
      }
  
      Reader(File f) throws FileNotFoundException {
        br = new BufferedReader(new FileReader(f));
        st = new StringTokenizer("");
      }
  
      String next() {
        while (!st.hasMoreTokens())
          try {
            st = new StringTokenizer(br.readLine());
          } catch (IOException e) {
          }
        return st.nextToken();
      }
  
      int ni() {
        return Integer.parseInt(next());
      }
  
      long nl() {
        return Long.parseLong(next());
      }
  
      double nextDouble() {
        return Double.parseDouble(next());
      }
  
      int[] nai(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
          a[i] = ni();
        return a;
      }
  
      long[] nal(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
          a[i] = nl();
        return a;
      }
    }
  
  }