#include #define LOCAL 0 #define lli long long int #define llu unsigned long long int #define ld long double #define all(v) v.begin(),v.end() #define pb push_back #define mp make_pair #define F first #define S second #define si(n) scanf("%d",&n) #define slli(n) scanf("%lld",&n); #define ss(n) scanf("%s",n); const long double EPS = 1e-10; const int MOD = 1000000007ll; const int mod1 = 1000000009ll; const int mod2 = 1100000009ll; int INF = (int)1e9; lli INFINF = (lli)1e18; int debug = 0; long double PI = acos(-1.0); using namespace std; int bit_count(lli _x){lli _ret=0;while(_x){if(_x%2==1)_ret++;_x/=2;}return _ret;} int bit(lli _mask,int _i){return (_mask&(1ll<<_i))==0?0:1;} int add(int a,int b,int m=MOD){int x=a+b;while(x>=m)x-=m;while(x<0)x+=m;return x;} int sub(int a,int b,int m=MOD){int x=a-b;while(x<0)x+=m;while(x>=m)x-=m;return x;} int mul(int a,int b,int m=MOD){lli x=a*1ll*b;x%=m;while(x<0)x+=m;return (int)x;} int ldtoint(ld x){return (int)(x+0.5);}lli ldtolli(ld x){return (lli)(x+0.5);} int powermod(lli _a,lli _b,int _m=MOD){lli _r=1;while(_b){if(_b%2==1)_r=mul(_r,_a,_m);_b>>=1;_a=mul(_a,_a,_m);}return _r;} templateostream&operator<<(ostream& os,const pair&p){os<<"["<ostream&operator<<(ostream& os,const vector&v){os << "[";bool first=true;for (T it:v){if (!first)os<<", ";first = false;os<ostream&operator<<(ostream& os,set&v){os<<"[";bool first=true;for (T it:v){if(!first)os<<", ";first=false;os<ostream&operator<<(ostream& os,map&v){os<<"[";bool first=true;for(pair it:v){if(!first)os<<", ";first=false;os<<"("<void parr(T a[],int s,int e){cout<<"[";for(int i=s;i j; } void buildSA(){ n = s.size(); for(int i=0;ir) swap(l,r); if(l==r) return INF; if(l+1==r) return lcp[l]; r--; int k=logs[r-l+1]; return min(lcptable[k][l],lcptable[k][r-(1<e) return; if(Segtree[idx].lazy == 0) return; Segtree[idx].val += Segtree[idx].lazy; if(s != e){ Segtree[2*idx+1].lazy += Segtree[idx].lazy; Segtree[2*idx+2].lazy += Segtree[idx].lazy; } Segtree[idx].lazy = 0; } void UpdateSegTree(int s,int e,int x,int y,stt v,int idx){ if(s==x && e==y){ Segtree[idx].lazy += v; lazyupd(s,e,idx); return; } lazyupd(s,e,idx); lli mid = (s+e)>>1; if(y<=mid){ UpdateSegTree(s,mid,x,y,v,2*idx+1); lazyupd(mid+1,e,2*idx+2); } else if(x>mid){ UpdateSegTree(mid+1,e,x,y,v,2*idx+2); lazyupd(s,mid,2*idx+1); } else{ UpdateSegTree(s,mid,x,mid,v,2*idx+1); UpdateSegTree(mid+1,e,mid+1,y,v,2*idx+2); } Segtree[idx] = MergeSegTree(Segtree[2*idx+1],Segtree[2*idx+2]); } lli QuerySegTree(int s,int e,int x,int y,int idx){ lazyupd(s,e,idx); if(s==x && e==y) return Segtree[idx].val; int mid = (s+e)>>1; if(y<=mid) return QuerySegTree(s,mid,x,y,2*idx+1); if(x>mid) return QuerySegTree(mid+1,e,x,y,2*idx+2); return QuerySegTree(s,mid,x,mid,2*idx+1) + QuerySegTree(mid+1,e,mid+1,y,2*idx+2); } }; int N,Q; string A[100010]; int val[100010],L[100010],R[100010]; string q[100010]; lli ans[100010]; vector queries[100010]; int start[100010]; int yahase[100010],yahatak[100010]; Segtree stt; char tempss[2000010]; int main() { if(LOCAL){ freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); debug = 1; } srand (time(NULL)); //cin>>N; si(N); for(int i=1;i<=N;i++) {ss(tempss);A[i]=tempss;}//si(A[i]);//cin>>A[i]; for(int i=1;i<=N;i++) si(val[i]);//cin>>val[i]; //cin>>Q; si(Q); for(int i=1;i<=Q;i++){ //cin>>L[i]>>R[i]>>q[i]; si(L[i]);si(R[i]); ss(tempss); q[i] = tempss; L[i]++;R[i]++; queries[R[i]].pb(i); queries[L[i]-1].pb(-i); } SA::s='$'; for(int i=1;i<=N;i++){ start[i] = SA::s.size(); SA::s += A[i]; SA::s += '$'; } for(int i=1;i<=Q;i++){ yahase[i] = SA::s.size(); SA::s += q[i]; yahatak[i] = SA::s.size()-1; if(i>1; if(SA::lcpQuery(mid,SA::pos[start[i]]) >= A[i].size()){ idx = mid; high = mid - 1; } else low = mid + 1; } s = idx; low = SA::pos[start[i]],high = m; while(low<=high){ int mid = (low + high)>>1; if(SA::lcpQuery(mid,SA::pos[start[i]]) >= A[i].size()){ idx = mid; low = mid + 1; } else high = mid - 1; } e = idx; //cout<