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: from sys import stdin, stdout
  from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
  from collections import defaultdict as df, deque
  from heapq import merge, heapify, heappop, heappush, nsmallest
  from bisect import bisect_left as bl, bisect_right as br, bisect
  mod = pow(10, 9) + 7
  mod2 = 998244353
  S1 = 'abcdefghijklmnopqrstuvwxyz'
  S2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
  def SieveOfEratosthenes(n):
      l=[]
      prime = [True for i in range(n+1)]
      p = 2
      while (p * p <= n):
          if (prime[p] == True):
              for i in range(p * p, n+1, p):
                  prime[i] = False
          p += 1
      for p in range(2, n+1):
          if prime[p]:
              l.append(p)
      return l
  def isprime(x):
      if x<=1: return False
      if x in (2, 3): return True
      if x%2 == 0: return False
      for i in range(3, int(sqrt(x))+1, 2):
          if x%i == 0: return False
      return True
  def f(s):
      first,second=0,0
      ans,res=10,10
      for i in range(10):
          if i%2==0:
              first+=int(s[i])
          else:
              second+=int(s[i])
          if first>second+(10-i)//2:
              ans=i+1
              break
      for i in range(10):
          if i%2==0:
              first+=int(s[i])
          else:
              second+=int(s[i])
          if first+(9-i)//2<second:
              res=i+1
              break
      return min(ans,res)
  for _ in range(int(input())):
      n,k=map(int,input().split())
      s=list(map(str,input().split()))
      d=df(list)
      for i in range(n):
          d[s[i]].append(i)
      # print(d)
      res=[0]*n
      cnt,ans=0,0
      ss=set(s)
      coll=1
      for i in ss:
          if len(d[i])<k:
              cnt+=len(d[i])
      cnt=(cnt//k)*k
      # print(d,cnt)
      for i in ss:
          if len(d[i])>=k:
              j=0
              col=1
              while(j<k and col<=k):
                  res[d[i][j]]=col
                  col+=1
                  j+=1
          else:
              j=0
              while(j<len(d[i]) and cnt>0):
                  res[d[i][j]]=coll
                  # print(coll)
                  coll+=1
                  if coll==k+1:
                      coll=1
                  j+=1
                  cnt-=1
                  # if cnt<k:
      print(*res,sep=' ')
              
  
              
  
  
  
      # for i in list(d.values()):
      #     if i>=k:
      #         ans+=1
      #     else:
      #         cnt+=1
      # print(ans+cnt//k)
  
      # n=int(input())
      # c1,c2=0,0
      # if n%3==0:
      #     print(n//3,n//3)
      # else:
      #     if (n-1)%3==0:
      #         x=(n-1)//3
      #         print(x+1,x)
      #     else:
      #         x=(n-2)//3
      #         print(x,x+1)
          
      