#include using namespace std; //construct SA by SA-IS O(N) #include #include struct SA{ string s; vectorsa; SA(const string&s_):s(s_) { sa=build(vector(s.begin(),s.end()),256); } vectorinduced_sort(const vector&S,const vector&id,const vector&SL,vectorlast) { vectorfirst(last); vectorret(id.size()); ret[0]=id[0]; for(int i=0;i=1&&!SL[id[i]-1]) { ret[first[S[id[i]-1]-1]++]=id[i]-1; } else if(ret[i]>=1&&!SL[ret[i]-1]) { ret[first[S[ret[i]-1]-1]++]=ret[i]-1; } } for(int i=id.size();i--;) { if(ret[i]>=1&&SL[ret[i]-1]) { ret[--last[S[ret[i]-1]]]=ret[i]-1; } } return ret; } vectorbuild(vectorS,int maxval) { if(S.size()<=1) { return S.empty()?(vector){0}:(vector){1,0}; } S.push_back(0); vectorcnt(maxval,0); vectorSL(S.size());//S=>true,L=>false for(int i=S.size();i--;) { cnt[S[i]]+=1; SL[i]=i+1==S.size()||S[i]last(cnt); vectorid(S.size()); vectoris_LMS(S.size()); int LMScnt=0; for(int i=1;i=0&&S[pre]==S[id[i]]) { int k; for(k=1;S[pre+k]==S[id[i]+k]&&!is_LMS[pre+k]&&!is_LMS[id[i]+k];k++); LMSsub-=S[pre+k]==S[id[i]+k]&&is_LMS[pre+k]&&is_LMS[id[i]+k]; } pre=id[i]; is_LMS[id[i]]=LMSsub++; } } vectornewstr(LMScnt); vectorrev(LMScnt); int counter=0; for(int i=0;isortedLMS=build(newstr,LMSsub); id.assign(S.size(),0); for(int i=1;i1) { int M=L+R>>1; if(s.compare(sa[M],t.size(),t)>=0)R=M; else L=M; } return R; } int upper_bound(const string&t)const { int L=-1,R=sa.size(); while(R-L>1) { int M=L+R>>1; if(s.compare(sa[M],t.size(),t)<=0)L=M; else R=M; } return R; } bool contain(const string&t)const { int id=lower_bound(t); return idlcp; LCP(const SA&sa) { int n=sa.size()-1; lcp.assign(n,0); vectorrank(n+1); for(int i=0;i<=n;i++)rank[sa[i]]=i; int h=0; lcp[0]=0; for(int i=0;i0; for(;i+h #include template struct DST{ functioncalcfn; int n; vector >dat; DST(const vector&v={}, functioncalcfn_=[](T a,T b){return a(n)); for(int j=i;jn)r=n; r--; if(l==r)return dat[0][l]; int k=31-__builtin_clz(l^r); return calcfn(dat[k][l],dat[k][r]); } }; int id[1<<17]; int rev[1<<20]; int len[1<<17]; main() { int N; cin>>N; string s=""; for(int i=0;i>t; id[i]=s.size(); len[i]=t.size(); s+=t; } SA P(s); for(int i=0;iX(Q.lcp); int M; long x,d; cin>>M>>x>>d; long ans=0; for(;M--;) { int i=x/(N-1),j=x%(N-1); if(i>j)i^=j^=i^=j; else j++; int I=rev[id[i]],J=rev[id[j]]; if(I>J)I^=J^=I^=J; ans+=min(X.query(I,J),min(len[i],len[j])); x=(x+d)%((long)N*(N-1)); } cout<