#include using namespace std; #define ALL(x) begin(x),end(x) #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<bool chmax(T &a,const T &b){if(abool chmin(T &a,const T &b){if(b ostream &operator<<(ostream &os,const vector&v){ for(int i=0;i<(int)v.size();i++) os< istream &operator>>(istream &is,vector&v){ for(T &x:v)is>>x; return is; } struct SuffixArray{ vector SA; const string s; SuffixArray(const string &str):s(str){ SA.resize(s.size()); iota(begin(SA),end(SA),0); sort(begin(SA),end(SA),[&](int a,int b){ return s[a]==s[b]?a>b:s[a] classes(s.size()),c(s.begin(),s.end()),cnt(s.size()); for(int len=1;len<(int)s.size();len<<=1){ for(int i=0;i<(int)s.size();i++) { if(i>0 and c[SA[i-1]]==c[SA[i]] and SA[i-1]+len<(int)s.size() and c[SA[i-1]+len/2]==c[SA[i]+len/2]){ classes[SA[i]]=classes[SA[i - 1]]; } else { classes[SA[i]]=i; } } iota(begin(cnt),end(cnt),0); copy(begin(SA),end(SA),begin(c)); for(int i=0;i<(int)s.size();i++){ int s1=c[i]-len; if(s1>=0) SA[cnt[classes[s1]]++]=s1; } classes.swap(c); } } int operator[](int k)const{ return SA[k]; } int size()const{ return (int)s.size(); } bool lt_substr(const string &t,int si = 0,int ti = 0){ int sn=(int)s.size(),tn=(int)t.size(); while(sit[ti]) return false; ++si,++ti; } return si>=sn and ti1){ int mid=(low+high)/2; if(lt_substr(t,SA[mid])) low=mid; else high=mid; } return high; } pair lower_upper_bound(string &t){ int idx=lower_bound(t); int low=idx-1,high=(int)SA.size(); t.back()++; while(high-low>1){ int mid=(low+high)/2; if(lt_substr(t,SA[mid])) low=mid; else high=mid; } t.back()--; return {idx, high}; } void output(){ for(int i=0;i>s; SuffixArray sa(s); int q;cin>>q; ll res=0; while(q--){ string t;cin>>t; auto [lw,hi]=sa.lower_upper_bound(t); res+=hi-lw; } cout<