#include #include #include #include #include #include #include #include #include #include using namespace std; const int MAX_N = 100005; const int K = 26; const int MAX_ST = 2000005; struct vertex { int next[K]; bool leaf; int p; char pch; int link; int ind; int go[K]; }; vertex t[MAX_ST]; int sz; void init() { t[0].p = t[0].link = -1; memset(t[0].next, 255, sizeof(t[0].next)); memset(t[0].go, 255, sizeof(t[0].go)); sz = 1; } void add_string(const string &s, int ind) { int v = 0; for (size_t i = 0; i < s.length(); ++i) { char c = s[i] - 'a'; if (t[v].next[c] == -1) { memset(t[sz].next, 255, sizeof(t[sz].next)); memset(t[sz].go, 255, sizeof(t[sz].go)); t[sz].link = -1; t[sz].p = v; t[sz].pch = c; t[v].next[c] = sz++; } v = t[v].next[c]; } t[v].ind = ind; t[v].leaf = true; } int go(int v, char c); int get_link(int v) { if (t[v].link == -1) { if (v == 0 || t[v].p == 0) { t[v].link = 0; } else { t[v].link = go(get_link(t[v].p), t[v].pch); } } return t[v].link; } int go(int v, char c) { if (t[v].go[c] == -1) { if (t[v].next[c] != -1) { t[v].go[c] = t[v].next[c]; } else { t[v].go[c] = v == 0? 0: go(get_link (v), c); } } return t[v].go[c]; } string genes[MAX_N]; int n, health[MAX_N]; unordered_map>> g; long long calc(int a, int b, int d) { auto& v = g[genes[d]]; auto last = lower_bound(v.begin(), v.end(), make_pair(b + 1, (long long)-1)); auto first = lower_bound(v.begin(), v.end(), make_pair(a, (long long)-1)); if (last == v.begin()) { return 0; } last--; if (last->first < a) { return 0; } long long ans = last->second; if (first == v.begin()) { return ans; } first--; ans -= first->second; return ans; } long long calc(int a, int b, string d) { int node = 0; long long ans = 0; for (int i = 0; i < d.size(); i++) { node = go(node, d[i] - 'a'); int v = node; while (v) { if (t[v].leaf) { ans += calc(a, b, t[v].ind); } v = get_link(v); } } return ans; } void add_gene(int i) { auto& v = g[genes[i]]; if (v.empty()) { v.push_back(make_pair(i, health[i])); } else { v.push_back(make_pair(i, health[i] + v[v.size() - 1].second)); } } int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ cin >> n; init(); for (int i = 0; i < n; i++) { cin >> genes[i]; add_string(genes[i], i); } for (int i =0 ; i < n; i++) { cin >> health[i]; add_gene(i); } int s; cin >> s; long long mn = 1000000000000000000ll; long long mx = 0; for (int i = 0; i < s; i++) { int a, b; string d; cin >> a >> b >> d; long long cur = calc(a, b, d); mn = min(mn, cur); mx = max(mx, cur); } cout << mn << " " << mx << endl; return 0; }