#include using namespace std; using Int = long long; template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a sa,lcp,rev; SuffixArray(){} SuffixArray(string &S):S(S){init();} void init(){ n=S.length(); S.push_back('$'); build_sa(); build_lcp(); build_rmq(); } void build_sa(){ sa.assign(n+1,0); iota(sa.begin(),sa.end(),0); sort(sa.begin(),sa.end(), [&](int a,int b){ if(S[a]==S[b]) return a>b; return S[a] c(n+1,0),r(n+1),cnt(n+1),s(n+1); for(int i=0;i<=n;i++) r[i]=S[i]; for(int len=1;len<=n;len*=2){ for(int i=0;i<=n;i++){ c[sa[i]]= i>0 && r[sa[i-1]]==r[sa[i]] && sa[i-1]+len<=n && r[sa[i-1]+len/2]==r[sa[i]+len/2] ? c[sa[i-1]]:i; } iota(cnt.begin(),cnt.end(),0); copy(sa.begin(),sa.end(),r.begin()); for(int i=0;i<=n;i++){ int s1=r[i]-len; if(s1>=0) sa[cnt[c[s1]]++]=s1; } c.swap(r); } } bool lt_substr(string &T,int si=0,int ti=0){ int sn=S.size(),tn=T.size(); while(siT[ti]) return 0; si++;ti++; } return si>=sn&&ti0) h--; for(;j+h > dat; vector ht; void init(int n){ int h=1; while((1<(n)); ht.assign(n+1,0); for(int j=2;j<=n;j++) ht[j]=ht[j>>1]+1; } void build(int n,vector &v){ int h=1; while((1<b) swap(a,b); int l=b-a; return min(dat[ht[l]][a],dat[ht[l]][b-(1<=r){ int m=rmq.query(low,mid); if(m>s; int m; cin>>m; vector c(m); for(int i=0;i>c[i]; SuffixArray sa(s); Int cnt=0; for(int i=0;i