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.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;
    }
  }

}