#include #include #include #include #include using namespace std; using dat=pair; dat op(dat a,dat b){return make_pair(a.first+b.first,a.second+b.second);} dat e(){return make_pair(0L,0);} dat mp(int f,dat x) { if(f)x.first=x.second*(long)f; return x; } int cmp(int f,int g){return f?f:g;} int id(){return 0;} int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T;cin>>T; for(;T--;) { int N;long long K; cin>>N>>K; vectorA(N); for(int i=0;i>A[i]; vectorsa=atcoder::suffix_array(A); vectorlcp=atcoder::lcp_array(A,sa); atcoder::lazy_segtreeseg(vector(N,make_pair(N,1))); K=(long long)N*(N+1)/2-K; for(int i=N;i--;) { int r=N-sa[i]; int l=seg.min_left(r,[&](dat x){ return x.first-(long long)i*x.second<=K; }); int mn=i==0?0:lcp[i-1]; if(l<=mn) { dat x=seg.prod(mn,r); K-=x.first-(long long)i*x.second; seg.apply(mn,N,i); continue; } for(int j=0;j