仓鼠家里有n堆鸡蛋，每堆有ai个鸡蛋，仓鼠准备了n个篮子(按照1,2,3,...n编号)，每个篮子最多能放m个鸡蛋，仓鼠想要把鸡蛋全部放在篮子里。
这时候，它想起了智乃酱说过，不能把鸡蛋都放在一个篮子里。所以它决定每个篮子不能放超过k堆鸡蛋。
因为仓鼠很懒，所以它每次都会按顺序拿起一堆鸡蛋，然后放在编号最小的，可行的篮子里。
现在它想知道，如果按照这样操作，每一堆鸡蛋会被放在哪个篮子里？
输入描述:
首先输入一个T(1≤T≤100)，代表测试数据数. 每个案例的第一行输入三个整数，n(1≤n≤3×10^5)，m(1≤m≤10^9)，k(1≤k≤10^6). 第二行输入n个整数，a1,a2,a3...(1≤ai≤109)。
输入保证sigma(n)<=1e6
输出描述:
输出n行，每行一个整数，第i行输出代表第i堆鸡蛋被放在哪个篮子里。(如果鸡蛋没被放在任何一个篮子里，输出"−1"
示例1
输入
1 7 5 2 5 5 1 4 3 3 1
输出
1 2 3 3 4 5 4
#include<bits/stdc++.h>
using namespace std;
const int MAXN=300005;
#define int long long
struct tnode
{
int maxx;
int l,r;
};
int n,m,k,cnt[MAXN];
struct Segment_Tree
{
tnode t[4*MAXN];
void update (int root)
{
int ch=root<<1;
t[root].maxx=max(t[ch].maxx,t[ch+1].maxx);
}
void buildt(int root,int l,int r)
{
t[root].l=l;
t[root].r=r;
if(l!=r)
{
int mid=(l+r)>>1;
int ch=root<<1;
buildt(ch,l,mid);
buildt(ch+1,mid+1,r);
update(root);
}
else
{
t[root].maxx=m;
cnt[l]=0;
}
}
int gao(int val)
{
int root=1;
while(t[root].l!=t[root].r)
{
if(t[root<<1].maxx>=val)
{
root<<=1;
}
else
{
root=root*2+1;
}
}
t[root].maxx-=val;
++cnt[t[root].l];
int ans=t[root].l;
if(cnt[t[root].l]==k)
{
t[root].maxx=0;
}
root>>=1;
while(root)
{
update(root);
root>>=1;
}
return ans;
}
};
Segment_Tree ST;
int x,T;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>T;
while(T--)
{
cin>>n>>m>>k;
ST.buildt(1,1,n);
for(int i=1; i<=n; ++i)
{
cin>>x;
if(x>m)
{
cout<<-1<<"n";
}
else
{
cout<<ST.gao(x)<<"n";
}
}
}
return 0;
}
