text: s){ f[s++]=0; } if(m){ my_putchar('-'); } while(s--){ my_putchar(f[s]+'0'); } } template<class S> inline void arrInsert(const int k, int &sz, S a[], const S aval){ int i; sz++; for(i=sz-1;i>k;i--){ a[i] = a[i-1]; } a[k] = aval; } template<class S, class T> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval){ int i; sz++; for(i=sz-1;i>k;i--){ a[i] = a[i-1]; } for(i=sz-1;i>k;i--){ b[i] = b[i-1]; } a[k] = aval; b[k] = bval; } template<class S, class T, class U> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval){ int i; sz++; for(i=sz-1;i>k;i--){ a[i] = a[i-1]; } for(i=sz-1;i>k;i--){ b[i] = b[i-1]; } for(i=sz-1;i>k;i--){ c[i] = c[i-1]; } a[k] = aval; b[k] = bval; c[k] = cval; } template<class S, class T, class U, class V> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval, V d[], const V dval){ int i; sz++; for(i=sz-1;i>k;i--){ a[i] = a[i-1]; } for(i=sz-1;i>k;i--){ b[i] = b[i-1]; } for(i=sz-1;i>k;i--){ c[i] = c[i-1]; } for(i=sz-1;i>k;i--){ d[i] = d[i-1]; } a[k] = aval; b[k] = bval; c[k] = cval; d[k] = dval; } template<class S, class T> inline S chmin(S &a, T b){ if(a>b){ a=b; } return a; } template<class S, class T> inline S chmax(S &a, T b){ if(a<b){ a=b; } return a; } int N; int C; int Q; int A[30000]; int X; long long Y; long long cnt[5][30000+2]; int sz; int lis[5]; int ind[5]; int usz[30000+2]; int ulis[30000+2][5]; int dsz[30000+2]; int dlis[30000+2][5]; long long skipL[5][30000+2]; long long skipR[5][30000+2]; long long skipV[5][30000+2]; int skip = 150; long long skip2L[5][30000+2]; long long skip2R[5][30000+2]; long long skip2V[5][30000+2]; int skip2 = 30; int main(){ int t_ynMSdg; wmem = memarr; int i; int j; int k; int c; for(i=(0);i<(5);i++){ cnt[i][0] = 1; } for(i=(0);i<(5);i++){ for(k=(0);k<(30000);k++){ for(j=(0);j<(min_L(k, i)+1);j++){ cnt[i][k+1] += cnt[i-j][k-j]; if(cnt[i][k+1] > 2000000000000000000LL){ cnt[i][k+1] = 2000000000000000000LL; } } } } int KrdatlYV = rd_int(); for(t_ynMSdg=(0);t_ynMSdg<(KrdatlYV);t_ynMSdg++){ int dtiCQK_a; rd(N); rd(C); rd(Q); { int a2conNHc; for(a2conNHc=(0);a2conNHc<(N);a2conNHc++){ rd(A[a2conNHc]); } } for(k=(0);k<(N);k++){ sz = 0; for(i=(0);i<(C+1);i++){ if(k+i < N){ arrInsert(sz, sz, ind, i, lis, A[k+i]); } } sortA_L(sz, lis, ind); j = usz[k] = dsz[k] = 0; for(i=(0);i<(sz);i++){ if(ind[i] == 0){ j++; continue; } if(j==0){ ulis[k][usz[k]++] = ind[i]; } if(j==1){ dlis[k][dsz[k]++] = ind[i]; } } } for(k=(0);k<(N);k++){ for(c=(0);c<(C+1);c++){ long long sm = 0; skipL[c][k] = -4611686016279904256LL; skipR[c][k] = 4611686016279904256LL; if(k+skip+5 >= N){ swap(skipL[c][k], skipR[c][k]); continue; } for(j=(k);j<(k+skip);j++){ for(i=(0);i<(usz[j]);i++){ if(c >= ulis[j][i]){ sm += cnt[c-ulis[j][i]][N-j-ulis[j][i]-1]; } } if(sm > 4611686016279904256LL){ sm = 2000000000000000000LL; } chmax(skipL[c][k], sm); chmin(skipR[c][k], sm + cnt[c][N-j-1]); } skipV[c][k] = sm; } } for(k=(0);k<(N);k++){ for(c=(0);c<(C+1);c++){ long long sm = 0; skip2L[c][k] = -4611686016279904256LL; skip2R[c][k] = 4611686016279904256LL; if(k+skip2+5 >= N){ swap(skip2L[c][k], skip2R[c][k]); continue; } for(j=(k);j<(k+skip2);j++){ for(i=(0);i<(usz[j]);i++){ if(c >= ulis[j][i]){ sm += cnt[c-ulis[j][i]][N-j-ulis[j][i]-1]; } } if(sm > 4611686016279904256LL){ sm = 2000000000000000000LL; } chmax(skip2L[c][k], sm); chmin(skip2R[c][k], sm + cnt[c][N-j-1]); } skip2V[c][k] = sm; } } for(dtiCQK_a=(0);dtiCQK_a<(Q);dtiCQK_a++){ rd(X);X += (-1); rd(Y);Y += (-1); if(Y >= cnt[C][N]){ wt_L(-1); wt_L('\n'); continue; } c = C; for(k=(0);k<(N);k++){ if(skipL[c][k] <= Y && Y < skipR[c][k]){ if(X < k + skip){ wt_L(A[X]); wt_L('\n'); break; } Y -= skipV[c][k]; k += skip - 1; continue; } if(skip2L[c][k] <= Y && Y < skip2R[c][k]){ if(X < k + skip2){ wt_L(A[X]); wt_L('\n'); break; } Y -= skip2V[c][k]; k += skip2 - 1; continue; } for(i=(0);i<(usz[k]);i++){ if(c >= ulis[k][i]){ if(Y < cnt[c-ulis[k][i]][N-k-ulis[k][i]-1]){ if(X <= k + ulis[k][i]){ wt_L(A[k+ulis[k][i]-(X-k)]); wt_L('\n'); goto qE8LMwYZ; } c -= ulis[k][i]; k += ulis[k][i]; goto lQU550vz; } else{ Y -= cnt[c-ulis[k][i]][N-k-ulis[k][i]-1]; } } } if(Y < cnt[c][N-k-1]){ if(X == k){ wt_L(A[k]); wt_L('\n'); break; } continue; } else{ Y -= cnt[c][N-k-1]; } for(i=(0);i<(dsz[k]);i++){ if(c >= dlis[k][i]){ if(Y < cnt[c-dlis[k][i]][N-k-dlis[k][i]-1]){ if(X <= k + dlis[k][i]){ wt_L(A[k+dlis[k][i]-(X-k)]); wt_L('\n'); goto qE8LMwYZ; } c -= dlis[k][i]; k += dlis[k][i]; goto lQU550vz; } else{ Y -= cnt[c-dlis[k][i]][N-k-dlis[k][i]-1]; } } } lQU550vz:; } qE8LMwYZ:; } } return 0; } // cLay version 20210103-1 // --- original code --- // //no-unlocked // int N, C, Q, A[3d4], X; ll Y; // ll cnt[5][3d4+2]; // int sz, lis[5], ind[5]; // int usz[3d4+2], ulis[3d4+2][5]; // int dsz[3d4+2], dlis[3d4+2][5]; // ll skipL[5][3d4+2], skipR[5][3d4+2], skipV[5][3d4+2]; int skip = 150; // ll skip2L[5][3d4+2], skip2R[5][3d4+2], skip2V[5][3d4+2]; int skip2 = 30; // { // int i, j, k, c; // rep(i,5) cnt[i][0] = 1; // rep(i,5) rep(k,3d4) rep(j,min(k,i)+1){ // cnt[i][k+1] += cnt[i-j][k-j]; // if(cnt[i][k+1] > 2d18) cnt[i][k+1] = 2d18; // } // REP(rd_int()){ // rd(N,C,Q,A(N)); // // rep(k,N){ // sz = 0; // rep(i,C+1) if(k+i < N) arrInsert(sz, sz, ind, i, lis, A[k+i]); // sortA(sz, lis, ind); // j = usz[k] = dsz[k] = 0; // rep(i,sz){ // if(ind[i] == 0) j++, continue; // if(j==0) ulis[k][usz[k]++] = ind[i]; // if(j==1) dlis[k][dsz[k]++] = ind[i]; // } // } // // rep(k,N) rep(c,C+1){ // ll sm = 0; // skipL[c][k] = -ll_inf; // skipR[c][k] = ll_inf; // if(k+skip+5 >= N) swap(skipL[c][k], skipR[c][k]), continue; // rep(j,k,k+skip){ // rep(i,usz[j]) if(c >= ulis[j][i]) sm += cnt[c-ulis[j][i]][N-j-ulis[j][i]-1]; // if(sm > ll_inf) sm = 2d18; // skipL[c][k] >?