#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define INF 1e+9 #define mp make_pair #define pb push_back #define fi first #define fs first #define se second #define i64 long long #define li long long #define lint long long #define pii pair #define vi vector #define forn(i, n) for (int i = 0; i < (int)n; i++) #define fore(i, b, e) for (int i = (int)b; i <= (int)e; i++) struct vertex { int next[26]; vi numbers; int p; char pch; int link; int go[26]; }; const int maxn = 2e6+5; vertex t[maxn]; int sz; int cost[maxn]; 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 num) { int v = 0; for (size_t i=0; i> s; // cout << "s = " << s << endl; add_string(s, j); } forn(j, n) scanf("%d", &cost[j]); int q; scanf("%d", &q); i64 minn = 0; i64 maxx = 0; forn(query, q) { int L, R; scanf("%d%d", &L, &R); string s; cin >> s; int cur = 0; i64 sum = 0; for (char c : s) { cur = go(cur, (int)(c - 'a')); //printf("cur = %d\n", cur); int tmp = cur; while(tmp != 0) { for (int x : t[tmp].numbers) { if (x >= L && x <= R) sum += cost[x]; //printf("%c x = %d sum = %lld\n", c, x, sum); } tmp = get_link(tmp); } } if (query == 0 || sum > maxx) maxx = sum; if (query == 0 || sum < minn) minn = sum; } cout << minn << " " << maxx; }