#include<bits/stdc++.h> #define N 500005 usingnamespacestd; typedeflonglong ll;
const ll mod = 23333333333333333; int n, m, t; char s[500005]; int sa[N], sum[N], rnk[N], sa2[N], key[N], height[N], q[N], tmp[N], stk[N], top; ll f[N], ans;
inlineboolcheck(int *num, int a, int b, int l){ return num[a] == num[b] && num[a+l] == num[b+l]; }
inlinevoidDA(int _m){ int i, j, p; for (i = 1; i <= _m; i++) sum[i] = 0; for (i = 1; i <= n; i++) sum[rnk[i]=s[i]]++; for (i = 2; i <= _m; i++) sum[i] += sum[i-1]; for (i = n; i >= 1; i--) sa[sum[rnk[i]]--] = i; for (j = 1, p = 0; j <= n; j <<= 1, _m = p) { p = 0; for (i = n - j + 1; i <= n; i++) sa2[++p] = i; for (i = 1; i <= n; i++) if (sa[i] > j) sa2[++p] = sa[i] - j; for (i = 1; i <= n; i++) key[i] = rnk[sa2[i]]; for (i = 1; i <= _m; i++) sum[i] = 0; for (i = 1; i <= n; i++) sum[key[i]]++; for (i = 2; i <= _m; i++) sum[i] += sum[i-1]; for (i = n; i >= 1; i--) sa[sum[key[i]]--] = sa2[i]; for (swap(rnk, sa2), p = 2, rnk[sa[1]] = 1, i = 2; i <= n; i++) { rnk[sa[i]] = check(sa2, sa[i-1], sa[i], j) ? p - 1 : p++; } } }
inlinevoidgeth(){ ll p = 0; for (int i = 1; i <= n; i++) rnk[sa[i]] = i; for (int i = 1; i <= n; i++) { if (p) p--; int j = sa[rnk[i]-1]; while (s[i + p] == s[j + p]) p++; height[rnk[i]] = p; } }
int st[N][21];
voidpreST(){ for (int i = 1; i <= n; i++) st[i][0] = height[i]; for (int l = 1; (1 << l) <= n; l++) { for (int i = 1; i <= n - (1 << l) + 1; i++) { st[i][l] = min(st[i][l-1], st[i+(1<<(l-1))][l-1]); } } }
inlineintquery(int x, int y){ int l = log2(y - x + 1); return min(st[x][l], st[y - (1 << l) + 1][l]); }
inlineboolcmp(int x, int y){ return rnk[x] < rnk[y]; }
intmain(){ scanf("%d %d %s", &n, &m, s + 1); DA(128); geth(); preST(); for (int i = 1; i <= m; i++) { scanf("%d", &t); ans = 0; for (int j = 1; j <= t; j++) scanf("%d", &q[j]); sort(q + 1, q + t + 1, cmp); t = unique(q + 1, q + t + 1) - q - 1; for (int j = 2; j <= t; j++) { tmp[j] = query(rnk[q[j-1]] + 1, rnk[q[j]]); } stk[top=1] = 1; for (int j = 2; j <= t; j++) { while (top && tmp[stk[top]] > tmp[j]) top--; f[j] = f[stk[top]] + (j - stk[top]) * tmp[j]; stk[++top] = j; ans += f[j]; } printf("%lld\n", ans); } return0; }