#include using namespace std; //construct SA by doubling O(N(log N)^2) #include #include #include #include struct SA{ string s; vectorsa,rank; SA(const string&s_):s(s_) { int n=s.size(); sa.resize(n+1); rank.resize(n+1); for(int i=0;i<=n;i++) { sa[i]=i; rank[i]=itmp(rank); functionf=[&tmp,&k,&n](int i,int j){ return tmp[i]!=tmp[j]?tmp[i]1) { 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<