#include using i64 = long long; const int B=3; const i64 mod[B]={998244353,1000000007,1000000021}; i64 base[B]; using H=std::array; bool operator==(const H&l,const H&r){ for(int i=0;i>ha,pw; Hash(const std::string&s){ int n=s.size(); ha.assign(B,std::vector(n+1,0LL)); pw.assign(B,std::vector(n+1,1LL)); for(int k=0;k1){ int mid=(l+r)>>1; if(get(a,a+mid)!=get(b,b+mid))r=mid; else l=mid; } return l; } //Lcp(S[a:],T[b:]) int getLcp(const Hash&T,int a,int b)const{ int len = std::min((int)ha[0].size() - a, (int)ha[0].size() - b); int l = 0, r = len; while(r-l>1){ int mid=(l+r)>>1; if(get(a,a+mid)!=T.get(b,b+mid))r=mid; else l=mid; } return l; } }; void solve() { std::string s; int q; std::cin>>s>>q; int n=s.size(); Hash Hs(s); i64 ans = 0; while(q--){ std::string t;std::cin>>t; Hash Ht(t); H ht=Ht.get(); int m=t.size(); for(int i=0;i+m-1sync_with_stdio(false); solve(); return 0; }