ll@n,@q; string@s; ll ax[2n+1],ay[2n+1]; ax[0]=0; ay[0]=0; rep(i,2n){ if(s[i%n]=='D'){ ax[i+1]=ax[i]+1; ay[i+1]=ay[i]; }else{ ax[i+1]=ax[i]; ay[i+1]=ay[i]+1; } } rep(q){ ll@h,@w,@p,z; if(ax[n]==0||ay[n]!=0&&(h-1)/ax[n]>(w-1)/ay[n]){ w=(w-1)%ay[n]+1; z=bsearch_min[ll,j,p,p+n](ay[j]-ay[p]>=w); } else if(ay[n]==0||ax[n]!=0&&(h-1)/ax[n]<(w-1)/ay[n]){ h=(h-1)%ax[n]+1; z=bsearch_min[ll,j,p,p+n](ax[j]-ax[p]>=h); } else{ h=(h-1)%ax[n]+1; w=(w-1)%ay[n]+1; z=bsearch_min[ll,j,p,p+n](ax[j]-ax[p]>=h||ay[j]-ay[p]>=w); } wt(z%n); }