#include <bits/stdc++.h> #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;} template<class T1,class T2>ostream&operator<<(ostream& os,const pair<T1,T2>&p){os<<"["<<p.first<<","<<p.second<<"]";return os;} template<class T>ostream&operator<<(ostream& os,const vector<T>&v){os << "[";bool first=true;for (T it:v){if (!first)os<<", ";first = false;os<<it;}os<<"]";return os;} template<class T>ostream&operator<<(ostream& os,set<T>&v){os<<"[";bool first=true;for (T it:v){if(!first)os<<", ";first=false;os<<it;}os<<"]";return os;} template<class T1,class T2>ostream&operator<<(ostream& os,map<T1,T2>&v){os<<"[";bool first=true;for(pair<T1,T2> it:v){if(!first)os<<", ";first=false;os<<"("<<it.F<<","<<it.S<<")";}os<<"]";return os;} template<class T>void parr(T a[],int s,int e){cout<<"[";for(int i=s;i<e;i++)cout<<a[i]<<", ";cout<<a[e]<<"]\n";} namespace SA{ static const int MAXN = 2200010; static const int MAXLOGN = 23; string s; int n,gap; int sa[MAXN], pos[MAXN], tmp[MAXN], lcp[MAXN], logs[MAXN], lcptable[MAXLOGN][MAXN]; bool sufCmp(int i,int j){ if(pos[i] != pos[j]) return pos[i] < pos[j]; i += gap;j += gap; return(i < n && j < n) ? pos[i] < pos[j] : i > j; } void buildSA(){ n = s.size(); for(int i=0;i<n;i++) sa[i] = i,pos[i] = s[i]; for(gap = 1;;gap *= 2){ sort(sa,sa+n,sufCmp); for(int i=0;i<n-1;i++) tmp[i + 1] = tmp[i] + sufCmp(sa[i],sa[i + 1]); for(int i=0;i<n;i++) pos[sa[i]] = tmp[i]; if(tmp[n-1] == n-1) break; } } void buildLCP(){ for (int i=0,k=0;i<n;++i){ if(pos[i]!=n-1){ for(int j=sa[pos[i]+1];s[i+k]==s[j+k];) ++k; lcp[pos[i]]=k; if(k) --k; } } } void buildLogs(){ int g=2; while(g<=n){ logs[g]=1; g=(g<<1); } for(int i=1;i<=n;i++) logs[i]+=logs[i-1]; } void buildLcpSparseTable(){ for(int i=0;i<n;i++) lcptable[0][i]=lcp[i]; for(int j=1;(1<<j)<=n;j++) for(int i=0;i+(1<<j)-1<n;i++) lcptable[j][i]=min(lcptable[j-1][i],lcptable[j-1][i+(1<<(j-1))]); } int lcpQuery(int l,int r){ if(l>r) 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<<k)+1]); } }; struct Segtree{ typedef lli stt; static const int MAXN = 2200010; struct Node{ stt val; stt lazy; }; struct Node Segtree[4*MAXN]; Node MergeSegTree(Node a,Node b){ struct Node temp; temp.val = a.val + b.val; temp.lazy = 0; return temp; } void lazyupd(int s,int e,int idx){ if(s>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<int> 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<Q) SA::s += '$'; } int m = SA::s.size() - 1; SA::buildSA(); SA::buildLogs(); SA::buildLCP(); SA::buildLcpSparseTable(); //cout<<SA::s<<"\n"; //for(int i=1;i<=m;i++)cout<<i<<" - "<<SA::sa[i]<<" "<<SA::s.substr(SA::sa[i])<<"\n"; for(int i=1;i<=N;i++){ int low,high,idx,s,e; low = 1,high = SA::pos[start[i]]; while(low<=high){ int mid = (low + high)>>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<<i<<" - "<<SA::pos[start[i]]<<" "<<s<<" "<<e<<"\n"; stt.UpdateSegTree(1,m,s,e,val[i],0); //for(int i=1;i<=m;i++)cout<<stt.QuerySegTree(1,m,i,i,0).val<<" ";cout<<"\n"; for(int idx : queries[i]){ int j = abs(idx); int sign = 1; if(idx < 0) sign = -1; for(int k = yahase[j];k<=yahatak[j];k++){ ans[j] += sign*stt.QuerySegTree(1,m,SA::pos[k],SA::pos[k],0); } } } lli mmm = INFINF,MMM = -1; for(int i=1;i<=Q;i++){ mmm = min(mmm,ans[i]); MMM = max(MMM,ans[i]); } cout<<mmm<<" "<<MMM<<"\n"; return 0; }