#include #define f first #define s second #define mp make_pair #define pb push_back #define lp(i,a,n) for(int i=(a);i<=(int)(n);++i) #define lpd(i,a,n) for(int i=(a);i>=(int)(n);--i) #define mem(a,b) memset(a,b,sizeof a) #define all(v) v.begin(),v.end() #define println(a) cout <<(a) < pii; typedef pair pll; typedef vector vi; typedef vector vvi; typedef vector vll; typedef set si; typedef map mii; const int N = 100002; int n,q,h[N],nodeId,st,ed; const int maxCh = 27; ll ans; string g[N]; int getVal(char ch){ return ch - 'a'; } struct node{ node *fail; node* childs[maxCh]; vi patIds; vector chars; int id; node(){ id = ++nodeId; mem(childs, 0); } void insert(const char *str , int id){ if(!(*str)){ patIds.pb(id); return; } int ch = getVal(*str); if(!childs[ch]) childs[ch] = new node(), chars.pb(*str); childs[ch]->insert(str+1, id); } }; void fail(node* &k, char ch) { while (!k->childs[getVal(ch)]) k = k -> fail; k = k -> childs[getVal(ch)]; } node* buildAhoTree(string pat[], int n) { node* root = new node(); lp(i,1,n) root->insert(pat[i].c_str(), i); queue Q; lp(i,0,maxCh-2) if(root->childs[i]) Q.push(root->childs[i]), root->childs[i]->fail = root; else root->childs[i] = root; while(!Q.empty()) { node* cur = Q.front(); Q.pop(); for(char ch : cur->chars){ Q.push(cur->childs[getVal(ch)]); node *k = cur->fail; fail(k, ch); cur->childs[getVal(ch)]->fail = k; cur->childs[getVal(ch)]->patIds.insert(cur->childs[getVal(ch)]->patIds.end(), all(k->patIds)); } } return root; } void match(char *str , node* root) { node* k = root; for (int i = 0; str[i]; i++) { fail(k, str[i]); for(int p : k->patIds) if(p >= st and p <= ed) ans += h[p]; } } int main(){ readi(n); lp(i,1,n) cin >>g[i]; lp(i,1,n) readi(h[i]); node *tree = buildAhoTree(g,n); ll mn = infll, mx = 0; readi(q); while(q--){ ans = 0; char a[2000002]; read2i(st, ed); ++st, ++ed; scanf("%s",a); match(a, tree); mn = min(mn, ans); mx = max(mx, ans); } cout <