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 

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
 
namespace custom{
    typedef long long ll;
    typedef long double ld;
    typedef pair<int,int> pii;
    typedef pair<ll,ll> pll;
    typedef pair<ld,ld> pld;
    typedef vector<int> vi;
    typedef vector<vi> vvi;
    typedef vector<ll> vll;
    typedef vector<vll> vvll;
    typedef vector<pii>vpii;
    typedef vector<pll> vpll;
    
    #define pub push_back
    #define puf push_front
    #define pob pop_back
    #define fi first 
    #define se second
    #define precision(a) fixed<<setprecision(a)
    #define init(var,val) memset(var,val,sizeof(var))
    #define range(i, init, n) for(int i=init;i<n;i+=1)
    #define all(arr) arr.begin(),arr.end()
    #define INF INT_MAX
    #define LINF LONG_LONG_MAX
    #define IO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
    #define MOD 998244353
    const int dx[4]={-1,0,1,0};
    const int dy[4]={0,1,0,-1};
 
    template<class T>
    istream& operator>>(istream& in, vector<T>& v){
        for(auto&el:v)in>>el;
        return in;
    }
    template<class T>
        void print(T a,string end="\n"){cout<<a<<end;}
    template<class T1, class T2> 
        void print(pair<T1,T2>& a,string end="\n"){
            cout<<"{"<<a.fi<<","<<a.se<<"}"<<end;
        }
    template<class T> 
        void parr(T& arr, string end="\n"){
            int i=0;
            for(auto&el:arr){
                print(el," ");}
            print("",end);
        }
    template<class T> 
        void print(vector<T>& a,string end="\n"){parr(a,end);}
    template<class T> 
        void print(set<T>& a,string end="\n"){parr(a,end);}
    template<class T> 
        void print(deque<T>& a,string end="\n"){parr(a,end);}
    template<class T1, class T2> 
        void print(map<T1,T2>& a,string end="\n"){
            int i=0;
            for(auto&el:a){
                print(el.fi," : ");print(el.se);
            }print("",end);
        }
    template<class T>
        void _print(T f,string end){
            print(f,end);
        }
    template<class arg1, class... args> 
        void print(arg1 f, args... n){
            _print(f," ");print(n...);}
    template<class T> 
        void print(vector<vector<T>>& a){
            for(auto&el:a)print(el,"\n");
        }
    template<class T> int len(T& a){return a.size();}
    template<class T>
        ll sum(T& a){
            ll s=0;for(auto&el:a)s+=el;
            return s;
        }
    template<class T1,class T2> T1 min(T1 a,T2 b){
        return (a<b)?a:(T1)b;
    }template<class T1,class T2> T1 max(T1 a,T2 b){
        return (a>b)?a:(T1)b;
    }template<class T> T max(vector<T>a){
        T m=a[0];for(auto&el:a)m=max(m,el);
        return m;
    }template<class T> T min(vector<T>a){
        T m=a[0];for(auto&el:a)m=min(m,el);
        return m;
    }
    template<class T1, class... T2>
        T1 min(T1 a, T2... b){
            return min(a, (T1)min(b...));
        }
    template<class T1, class... T2>
        T1 max(T1 a, T2... b){
            return max(a, (T1)max(b...));
        }
}using namespace custom;

void solve(){
    int n,k;cin>>n>>k;
    vi a(n);cin>>a;
    map<int,int>dic;
    range(i,0,n){
        dic[a[i]]+=1;
    }map<int,int>dic2;vi temp;
    range(i,0,n){
        if(dic[a[i]]>=k)
            dic2[a[i]]=1;
        else{temp.pub(i);}
    }sort(temp.begin(),temp.end(),[&](auto&l,auto&r){
        return a[l]<a[r];
    });
    vi ans(n,0);
    int o=temp.size()/k;
    if(o>0){
        int i=0,c=1;
        while(i<o*k){
            range(q,0,o){
            ans[temp[i]]=c;i++;
            c+=1;if(c>k)c=1;}
        }
    }range(i,0,n){
        if(ans[i]==0){
            if(dic2[a[i]]<=k){
            ans[i]=dic2[a[i]];
            dic2[a[i]]+=1;}
        }
    }print(ans);
}

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    IO;
    ll t;
    t=1;
    cin >> t;
    while(t--){
        solve();}
    return 0;
}