Problem: Let LCP(s, t) be the length of the longest common prefix of strings s and t. Also let s[x ... y] be the substring of s from index x to index y (inclusive). For example, if s =  "abcde", then s[1 ... 3] = "abc", s[2 ... 5] = "bcde".

You are given a string s of length n and q queries. Each query is a pair of integer sets a_1, a_2, ..., a_k and b_1, b_2, ..., b_l. Calculate ∑_{i = 1}^{i = k} ∑_{j = 1}^{j = l}{LCP(s[a_i ... n], s[b_j ... n])} for each query.

Input

The first line contains two integers n and q (1 ≤ n, q ≤ 2 ⋅ 10^5) — the length of string s and the number of queries, respectively.

The second line contains a string s consisting of lowercase Latin letters (|s| = n).

Next 3q lines contains descriptions of queries — three lines per query. The first line of each query contains two integers k_i and l_i (1 ≤ k_i, l_i ≤ n) — sizes of sets a and b respectively.

The second line of each query contains k_i integers a_1, a_2, ... a_{k_i} (1 ≤ a_1 < a_2 < ... < a_{k_i} ≤ n) — set a.

The third line of each query contains l_i integers b_1, b_2, ... b_{l_i} (1 ≤ b_1 < b_2 < ... < b_{l_i} ≤ n) — set b.

It is guaranteed that ∑_{i = 1}^{i = q}{k_i} ≤ 2 ⋅ 10^5 and ∑_{i = 1}^{i = q}{l_i} ≤ 2 ⋅ 10^5.

Output

Print q integers — answers for the queries in the same order queries are given in the input.

Example

Input

7 4
abacaba
2 2
1 2
1 2
3 1
1 2 3
7
1 7
1
1 2 3 4 5 6 7
2 2
1 5
1 5


Output

13
2
12
16

Note

Description of queries: 

  1. In the first query s[1 ... 7] = abacaba and s[2 ... 7] = bacaba are considered. The answer for the query is LCP(abacaba, abacaba) + LCP(abacaba, bacaba) + LCP(bacaba, abacaba) + LCP(bacaba, bacaba) = 7 + 0 + 0 + 6 = 13.
  2. In the second query s[1 ... 7] = abacaba, s[2 ... 7] = bacaba, s[3 ... 7] = acaba and s[7 ... 7] = a are considered. The answer for the query is LCP(abacaba, a) + LCP(bacaba, a) + LCP(acaba, a) = 1 + 0 + 1 = 2.
  3. In the third query s[1 ... 7] = abacaba are compared with all suffixes. The answer is the sum of non-zero values: LCP(abacaba, abacaba) + LCP(abacaba, acaba) + LCP(abacaba, aba) + LCP(abacaba, a) = 7 + 1 + 3 + 1 = 12.
  4. In the fourth query s[1 ... 7] = abacaba and s[5 ... 7] = aba are considered. The answer for the query is LCP(abacaba, abacaba) + LCP(abacaba, aba) + LCP(aba, abacaba) + LCP(aba, aba) = 7 + 3 + 3 + 3 = 16. 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
char buf[1 << 20], *p1, *p2;
template <class T>
inline void read(T &n) {
  char ch =
      (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)
           ? 0
           : *p1++);
  T w = 1, x = 0;
  while (!isdigit(ch)) {
    if (ch == '-') w = -1;
    ch =
        (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)
             ? 0
             : *p1++);
  }
  while (isdigit(ch)) {
    x = (x << 3) + (x << 1) + (ch ^ 48);
    ch =
        (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)
             ? 0
             : *p1++);
  }
  n = x * w;
}
const int maxn = 200005;
int n, m, q;
char s[maxn];
int sa[maxn], rk[maxn], y[maxn];
void Rsort() {
  static int c[maxn];
  for (int i = 1; i <= m; i++) c[i] = 0;
  for (int i = 1; i <= n; i++) c[rk[i]]++;
  for (int i = 1; i <= m; i++) c[i] += c[i - 1];
  for (int i = n; i >= 1; i--) sa[c[rk[y[i]]]--] = y[i];
}
void getSA() {
  for (int i = 1; i <= n; i++) rk[i] = s[i], y[i] = i;
  m = 122, Rsort();
  for (int k = 1;; k <<= 1) {
    int num = 0;
    for (int i = n - k + 1; i <= n; i++) y[++num] = i;
    for (int i = 1; i <= n; i++)
      if (sa[i] > k) y[++num] = sa[i] - k;
    Rsort(), swap(rk, y);
    num = rk[sa[1]] = 1;
    for (int i = 2; i <= n; i++) {
      if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k])
        rk[sa[i]] = num;
      else
        rk[sa[i]] = ++num;
    }
    if (num == n) return;
    m = num;
  }
}
int height[maxn], st[maxn][19], Log[maxn];
void getheight() {
  for (int i = 1, k = 0; i <= n; i++) {
    if (rk[i] == 1) continue;
    if (k) k--;
    int j = sa[rk[i] - 1];
    while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++;
    height[rk[i]] = k;
  }
  for (int i = 2; i <= n; i++) Log[i] = Log[i >> 1] + 1;
  for (int i = 1; i <= n; i++) st[i][0] = height[i];
  for (int j = 1; j <= Log[n]; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
int query(int l, int r) {
  if (rk[l] > rk[r]) swap(l, r);
  int L = rk[l] + 1, R = rk[r];
  int i = Log[R - L + 1];
  return min(st[L][i], st[R - (1 << i) + 1][i]);
}
int A[maxn], B[maxn], X, Y, bel[maxn];
int bot[maxn << 1], tot, S[maxn << 1], top, sum[maxn << 1], h[maxn << 1];
bool cmp(int x, int y) { return rk[x] < rk[y]; }
long long ans, f[maxn << 1];
void solve() {
  read(X), read(Y);
  ans = tot = 0;
  for (int i = 1; i <= X; i++) {
    read(A[i]);
    bel[A[i]] = 1, bot[++tot] = A[i];
  }
  for (int i = 1; i <= Y; i++) {
    read(B[i]);
    if (bel[B[i]])
      ans += n - B[i] + 1, bel[B[i]] = 3;
    else
      bel[B[i]] = 2, bot[++tot] = B[i];
  }
  sort(bot + 1, bot + tot + 1, cmp);
  top = 0;
  for (int i = 1; i <= tot; i++) sum[i] = sum[i - 1] + (bel[bot[i]] >= 2);
  for (int i = 1; i <= tot; i++) {
    h[i] = query(bot[i], bot[i - 1]);
    while (top && h[i] < h[S[top]]) top--;
    f[i] = f[S[top]] + 1ll * h[i] * (sum[i - 1] - sum[S[top] - 1]);
    if (bel[bot[i]] & 1) ans += f[i];
    S[++top] = i;
  }
  top = 0;
  for (int i = 1; i <= tot; i++) sum[i] = sum[i - 1] + (bel[bot[i]] & 1);
  for (int i = 1; i <= tot; i++) {
    while (top && h[i] < h[S[top]]) top--;
    f[i] = f[S[top]] + 1ll * h[i] * (sum[i - 1] - sum[S[top] - 1]);
    if (bel[bot[i]] >= 2) ans += f[i];
    S[++top] = i;
  }
  for (int i = 1; i <= X; i++) bel[A[i]] = 0;
  for (int i = 1; i <= Y; i++) bel[B[i]] = 0;
  printf("%lld\n", ans);
}
int main() {
  scanf("%d%d", &n, &q);
  scanf("%s", s + 1);
  getSA(), getheight();
  for (int i = 1; i <= q; i++) solve();
  return 0;
}