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;
int read() {
  int x = 0, f = 1;
  char ch;
  while (!isdigit(ch = getchar())) (ch == '-') && (f = -1);
  for (x = ch ^ 48; isdigit(ch = getchar());
       x = (x << 3) + (x << 1) + (ch ^ 48))
    ;
  return x * f;
}
const int N = 4e5 + 9;
int fa[N][21], dep[N], hed[N], tot, num, a[N], vis[N], node_cnt, cnt[N][3],
    dfn[N];
int opp[3] = {0, 2, 1};
struct node {
  int to, nxt;
} e[N];
void add(int u, int v) { e[++tot] = node{v, hed[u]}, hed[u] = tot; }
int cmp(int a, int b) { return dfn[a] < dfn[b]; }
struct SAM_ {
  int trs[N][26], siz = 0, link[N], len[N], pos[N], las = ++siz;
  char s[N];
  void extend(int c, int id) {
    int cur = ++siz, p;
    pos[id] = siz, len[cur] = len[las] + 1;
    for (p = las; p && !trs[p][c]; p = link[p]) trs[p][c] = cur;
    if (!p)
      link[cur] = 1;
    else {
      int x = trs[p][c];
      if (len[x] == len[p] + 1)
        link[cur] = x;
      else {
        int cl = ++siz;
        len[cl] = len[p] + 1, link[cl] = link[x], link[x] = link[cur] = cl;
        memcpy(trs[cl], trs[x], sizeof(trs[x]));
        for (; p && trs[p][c] == x; p = link[p]) trs[p][c] = cl;
      }
    }
    las = cur;
  }
  void build() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    reverse(s + 1, s + n + 1);
    for (int i = 1; i <= n; i++) extend(s[i] - 'a', n - i + 1);
    for (int i = 2; i <= siz; i++) add(link[i], i);
  }
  int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 20; i >= 0; i--)
      if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
    if (x == y) return x;
    for (int i = 20; i >= 0; i--) {
      if (fa[x][i] == fa[y][i]) continue;
      x = fa[x][i], y = fa[y][i];
    }
    return fa[x][0];
  }
  void dfs(int x, int fx) {
    dep[x] = dep[fx] + 1, fa[x][0] = fx, dfn[x] = ++node_cnt;
    for (int i = 1; i <= 20; i++) fa[x][i] = fa[fa[x][i - 1]][i - 1];
    for (int i = hed[x]; i; i = e[i].nxt) {
      int y = e[i].to;
      if (y == fx) continue;
      dfs(y, x);
    }
  }
} S;
struct Virtal_Tree {
  int sta[N], fa[N], top;
  void build(int* a, int n) {
    sta[top = 0] = 0, num = n;
    for (int i = 1; i <= n; i++) {
      int x = a[i];
      if (!top)
        fa[x] = 0, sta[++top] = x;
      else {
        int lc = S.lca(sta[top], x);
        while (dep[sta[top]] > dep[lc]) {
          if (dep[sta[top - 1]] <= dep[lc]) fa[sta[top]] = lc;
          top--;
        }
        if (sta[top] != lc) {
          fa[lc] = sta[top], sta[++top] = lc, a[++num] = lc;
        }
        fa[x] = lc, sta[++top] = x;
      }
    }
  }
} V;
void clear() {
  for (int i = 1; i <= num; i++) cnt[a[i]][1] = cnt[a[i]][2] = 0, vis[a[i]] = 0;
}
void solve() {
  int n = read(), m = read(), ind = 0;
  for (int i = 1; i <= n; i++) a[++ind] = S.pos[read()], vis[a[ind]] += 1;
  for (int i = 1; i <= m; i++) a[++ind] = S.pos[read()], vis[a[ind]] += 2;
  sort(a + 1, a + ind + 1, cmp);
  ind = unique(a + 1, a + ind + 1) - a - 1;
  V.build(a, ind);
  sort(a + 1, a + num + 1, cmp);
  num = unique(a + 1, a + num + 1) - a - 1;
  long long ans = 0;
  for (int i = num; i >= 1; i--) {
    int x = a[i], fa = V.fa[x];
    if (vis[x] == 1) cnt[x][1]++;
    if (vis[x] == 2) cnt[x][2]++;
    if (vis[x] == 3) cnt[x][1]++, cnt[x][2]++;
    for (int j = 1; j <= 2; j++) cnt[fa][j] += cnt[x][j];
  }
  for (int i = num; i >= 1; i--) {
    int x = a[i], fa = V.fa[x];
    for (int j = 1; j <= 2; j++)
      ans += 1ll * S.len[fa] * (cnt[fa][j] - cnt[x][j]) * cnt[x][opp[j]];
  }
  for (int i = num; i >= 1; i--) {
    int x = a[i];
    if (vis[x] == 2 || vis[x] == 3) ans += 1ll * S.len[x] * cnt[x][1];
    if (vis[x] == 1 || vis[x] == 3) ans += 1ll * S.len[x] * cnt[x][2];
  }
  cout << ans / 2ll << "\n";
  clear();
}
int main() {
  int n = read(), Q = read();
  S.build(), S.dfs(1, 0);
  while (Q--) solve();
  return 0;
}