#include <bits/stdc++.h> using namespace std; #define sim template < class c #define ris return * this #define dor > debug & operator << #define eni(x) sim > typename \ enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) { sim > struct rge { c b, e; }; sim > rge<c> range(c i, c j) { return rge<c>{i, j}; } sim > auto dud(c* x) -> decltype(cerr << *x, 0); sim > char dud(...); struct debug { #ifdef LOCAL ~debug() { cerr << endl; } eni(!=) cerr << boolalpha << i; ris; } eni(==) ris << range(begin(i), end(i)); } sim, class b dor(pair < b, c > d) { ris << "(" << d.first << ", " << d.second << ")"; } sim dor(rge<c> d) { for (auto it = d.b; it != d.e; ++it) *this << ", \0[" + 3 * (it == d.b) << *it; ris << "]"; } #else sim dor(const c&) { ris; } #endif }; #define imie(x) "[" << #x ": " << (x) << "] " const int nax=2000*1007; int n; char wcz[nax]; int l; int dzie[nax][30]; int war[nax]; int oj[nax]; int suf[nax]; vector <int> ctree[nax]; vector <int> kon[nax]; long long dod[nax]; long long wyn[nax]; int q; int lew[nax]; int pra[nax]; vector <int> co_tu[nax]; void sufy() { queue <int> bfs; bfs.push(0); while(!bfs.empty()) { int v=bfs.front(); bfs.pop(); for (int i=0; i<26; i++) if (dzie[v][i]) bfs.push(dzie[v][i]); if (!oj[v]) continue; int w=suf[oj[v]]; while(w && !dzie[w][war[v]]) w=suf[w]; suf[v]=dzie[w][war[v]]; } for (int i=1; i<=l; i++) ctree[suf[i]].push_back(i); } long long drzewo[nax]; void dodaj(int v, long long w) { debug() << "wale w " << v; for (int i=v; i<=n; i+=(-i&i)) drzewo[i]+=w; } long long czytaj(int v, int u) { debug() << "z " << v << " " << u; long long ret=0; for (int i=v-1; i; i-=(-i&i)) ret-=drzewo[i]; for (int i=u; i; i-=(-i&i)) ret+=drzewo[i]; return ret; } void dfs(int v) { debug() << imie(v); for (int i=0; i<kon[v].size(); i++) dodaj(kon[v][i], dod[kon[v][i]]); debug() << "dodajem"; for (int i=0; i<co_tu[v].size(); i++) { int x=co_tu[v][i]; wyn[x]+=czytaj(lew[x], pra[x]); } debug() << "po zap"; for (int i=0; i<ctree[v].size(); i++) dfs(ctree[v][i]); for (int i=0; i<kon[v].size(); i++) dodaj(kon[v][i], -dod[kon[v][i]]); } int main() { scanf("%d", &n); for (int i=1; i<=n; i++) { scanf("%s", wcz); int v=0; for (int j=0; wcz[j]; j++) { if (!dzie[v][wcz[j]-'a']) { l++; dzie[v][wcz[j]-'a']=l; oj[l]=v; war[l]=wcz[j]-'a'; } v=dzie[v][wcz[j]-'a']; } kon[v].push_back(i); } for (int i=1; i<=n; i++) scanf("%lld", &dod[i]); debug() << "trie"; sufy(); debug() << "sufy"; scanf("%d", &q); for (int i=1; i<=q; i++) { scanf("%d%d", &lew[i], &pra[i]); lew[i]++; pra[i]++; scanf("%s", wcz); int v=0; for (int j=0; wcz[j]; j++) { while (v && !dzie[v][wcz[j]-'a']) v=suf[v]; v=dzie[v][wcz[j]-'a']; co_tu[v].push_back(i); } } debug() << "zapy"; dfs(0); debug() << "po dfs"; debug() << range(wyn+1, wyn+1+q); sort(wyn+1, wyn+1+q); printf("%lld %lld\n", wyn[1], wyn[q]); return 0; }