Wonderful Coloring - 2.cpp

// https://codeforces.com/problemset/problem/1551/B2
// Concept used : Hashing
//  299143BT
#include<bits/stdc++.h>
#define int long long int
#define MOD 1000000007
#define pi 3.1415926535
#define fi first
#define se second
#define vll vector<int>
#define vpll vector<pair <int,int> >
#define vvll vector< vll >
#define str string
#define umap unordered_map
#define uset unordered_set
#define rep(i,n) for(int i=0;i<n;i++)
#define repA(i,s,n) for(int i=s;i<=n;i++)
#define repD(i,s,n) for(int i=s;i>=n;i--)
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define elif else if
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ALL(v) v.begin(),v.end()
#define sortA(v) sort(ALL(v))
#define sortD(v) sort(ALL(v),greater <int> ())
#define print(v) for(auto itr:v) cout<<itr<<" ";
#define sz size()
#define nl cout<<"\n";
using namespace std;
int factorial(int n){return (n==1||n==0)?1:n*factorial(n-1);}
int power(int x,int y){int res=1;while(y>0){if(y&1)res=res*x;y=y>>1;x=x*x;}return res;}
int powerMod(int x,int y,int m){if(y==0)return 1;int p=powerMod(x,y/2,m)%m;p=(p*p)%m;return (y%2==0)?p:(x*p)%m;}
int modInverse(int a,int m){return powerMod(a,m-2,m);}
int gcd(int a,int b){if(a==0){return b;}else if(b==0){return a;}else{if(a>b){return gcd(a%b,b);}else{return gcd(b%a,a);}}}

void pre(){}

void solve(int t) {


    int n=0,k=0;
    cin>>n>>k;
    vll v(n);
    rep(i,n) cin>>v[i];
    map <int,int> m;
    rep(i,n) m[v[i]]++;
        int ans=0;
    int tmp=0;
    map<int,int> m1,m2;
    map <int,vll> m3;
    for(auto itr:m) {
        if (itr.se >= k) ans++;
        else {
            tmp += itr.se;
            m2[itr.fi]++;
        }
    }
    rep(i,n){
        if(m[v[i]]<k) m3[v[i]].pb(i);
    }
    ans+=(tmp/k);
//    cout<<ans;nl
    int tmp1=(tmp/k)*k;
    int flag=1;
    int j=1;
    vll res(n);
    rep(i,n) res[i]=-1;
    for(auto itr:m3){
        if(j<=tmp1){
            rep(z,itr.se.sz){
                if(j%k==0) res[itr.se[z]]=k;
                else res[itr.se[z]]=j%k;
                j++;
                if(j>tmp1) break;
            }
            rep(z,itr.se.sz) if(res[itr.se[z]]==-1) res[itr.se[z]]=0;
        }
        else{
            rep(z,itr.se.sz) res[itr.se[z]]=0;
        }
    }
    rep(i,n){
        if(m[v[i]]>=k){
            if(m1[v[i]]>=k) res[i]=0;
            else res[i]=++m1[v[i]];
        }
        else{
            if(res[i]==-1) res[i]=0;
        }
    }
    print(res);nl






//    rep(i,n){
//        if(m[v[i]]>=ans){
//            if(m1[v[i]]>ans) cout<<0<<" ";
//            else cout<<++m1[v[i]]<<" ";
//        }
//        else cout<<++m1[v[i]]<<" ";
//    }
//    nl
//    str s;
//    cin>>s;
//    map <char,int> m;
//    int n=s.sz;
//    int ans=0,tmp=0;
//    rep(i,n) m[s[i]]++;
//    for(auto &itr:m){
//        if(itr.se>=2) ans++;
//        else tmp++;
//    }
//    ans+=(tmp/2);
//    cout<<ans;nl
}

int32_t main(){
    fast
    int t=1;
    cin>>t;
    pre();
    rep(i,t) solve(t);
    return 0;
}