#define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define rep(i, N) for (int i = 0; i < N; i++) #define pb push_back typedef long long ll; typedef unsigned long long ull; typedef pair i_i; typedef pair ll_i; typedef pair d_i; typedef pair ll_ll; typedef pair d_d; struct edge { int v; ll w; }; // typedef complex C; ll MOD = 1000000007; ll _MOD = 1000000009; int INF = INT_MAX / 2; double EPS = 1e-10; ll freq[2000001], ans[100001]; vector unko; struct aho_corasick { int N, M; vector > next, accepts, uss; vector depth; void dfs(int i, string& s, int j, int u) { if (j == s.length()) { accepts[u].pb(i); return; } int k = s[j] - 'a' + 1; if (next[u][k] == -1) { next.pb(vector(27, -1)); accepts.pb({}); depth.pb(j + 1); if (j + 1 == uss.size()) uss.pb({}); uss[j + 1].pb(M); next[u][k] = M++; } dfs(i, s, j + 1, next[u][k]); } aho_corasick(vector patterns) { N = patterns.size(); M = 1; next.pb(vector(27, -1)); accepts.pb({}); uss.pb({0}); depth.pb(0); rep(i, N) dfs(i, patterns[i], 0, 0); for (vector us: uss) for (int u: us) for (int k = 1; k <= 26; k++) { if (next[u][k] == -1) continue; int v; for (v = next[u][0]; v != -1 && next[v][k] == -1; v = next[v][0]); next[next[u][k]][0] = (v == -1 ? 0 : next[v][k]); } } void search(string s) { vector > _uss(s.length() + 1); int u = 0; for (char c: s) { int k = c - 'a' + 1; for (; u != -1 && next[u][k] == -1; u = next[u][0]); u = (u == -1 ? 0 : next[u][k]); freq[u]++; _uss[depth[u]].pb(u); } for (int j = _uss.size() - 1; j > 0; j--) for (int u: _uss[j]) { if (!freq[u]) continue; for (int i: accepts[u]) ans[i] = freq[u], unko.pb(i); freq[next[u][0]] += freq[u]; freq[u] = 0; _uss[depth[next[u][0]]].pb(next[u][0]); } freq[0] = 0; } }; int main() { int N; cin >> N; vector w(N); rep(i, N) cin >> w[i]; vector h(N); rep(i, N) scanf("%d", &h[i]); vector W = w; sort(W.begin(), W.end()); W.erase(unique(W.begin(), W.end()), W.end()); int M = W.size(); vector > xs(M), hs(M, {0}); rep(i, N) { int j = lower_bound(W.begin(), W.end(), w[i]) - W.begin(); xs[j].pb(i); hs[j].pb(hs[j].back() + h[i]); } aho_corasick ac(W); int Q; cin >> Q; ll mi = LLONG_MAX, ma = LLONG_MIN; while (Q--) { int l, r; scanf("%d%d", &l, &r); r++; string s; cin >> s; ac.search(s); ll sum = 0; for (int j: unko) { // cout << W[j] << ' ' << ans[j] << endl; int L = lower_bound(xs[j].begin(), xs[j].end(), l) - xs[j].begin(); int R = lower_bound(xs[j].begin(), xs[j].end(), r) - xs[j].begin(); sum += ans[j] * (hs[j][R] - hs[j][L]); ans[j] = 0; } unko.clear(); mi = min(mi, sum); ma = max(ma, sum); } cout << mi << ' ' << ma << endl; }