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 n, m, q1, q2, Q1[200005], Q2[200005];
char s[200005];
int cnt = 1, lst = 1, tr[200005 << 1][26], pre[200005 << 1], len[200005 << 1],
    ed[200005];
long long ans = 0;
void ins(int c) {
  int np = ++cnt, p = lst;
  len[np] = len[p] + 1, lst = np;
  for (; p && !tr[p][c]; p = pre[p]) tr[p][c] = np;
  if (!p)
    pre[np] = 1;
  else {
    int q = tr[p][c];
    if (len[p] + 1 == len[q])
      pre[np] = q;
    else {
      int g = ++cnt;
      memcpy(tr[g], tr[q], sizeof(tr[q]));
      len[g] = len[p] + 1, pre[g] = pre[q];
      for (; p && tr[p][c] == q; p = pre[p]) tr[p][c] = g;
      pre[np] = pre[q] = g;
    }
  }
}
struct edge {
  int nxt, v;
  edge(int Nxt = 0, int V = 0) { nxt = Nxt, v = V; }
} e[200005 << 1];
int tot, fr[200005 << 1], dep[200005 << 1];
int ct, bg[200005 << 1], lg2[200005 << 2], st[200005 << 2][26];
int crt, r[200005 << 2];
bool col1[200005 << 1], col2[200005 << 1];
void add(int x, int y) {
  ++tot;
  e[tot] = edge(fr[x], y), fr[x] = tot;
}
void dfs(int u) {
  bg[u] = ++ct, st[ct][0] = u;
  for (int i = fr[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    dep[v] = dep[u] + 1;
    dfs(v);
    st[++ct][0] = u;
  }
}
int lca(int x, int y) {
  x = bg[x], y = bg[y];
  if (x > y) swap(x, y);
  int k = lg2[y - x + 1];
  return (dep[st[x][k]] < dep[st[y - (1 << k) + 1][k]])
             ? st[x][k]
             : st[y - (1 << k) + 1][k];
}
bool cmp(int x, int y) { return bg[x] < bg[y]; }
namespace Tree {
int tot, fr[200005 << 1];
edge e[200005 << 1];
int t, st[200005 << 1], sz[200005 << 1][2];
void add(int x, int y) {
  ++tot;
  e[tot] = edge(fr[x], y), fr[x] = tot;
}
void ins(int x) {
  if (!t) {
    st[++t] = x;
    return;
  }
  int g = lca(st[t], x);
  while (t > 1 && dep[g] < dep[st[t - 1]]) add(st[t - 1], st[t]), --t;
  if (t && dep[g] < dep[st[t]]) add(g, st[t]), --t;
  if (!t || st[t] != g) st[++t] = g;
  st[++t] = x;
}
void dfs(int u) {
  if (col1[u]) ++sz[u][0];
  if (col2[u]) ++sz[u][1];
  long long cnt = sz[u][0] * sz[u][1];
  for (int i = fr[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    dfs(v);
    cnt += (long long)sz[u][0] * sz[v][1] + (long long)sz[v][0] * sz[u][1];
    sz[u][0] += sz[v][0], sz[u][1] += sz[v][1];
  }
  ans += cnt * len[u];
}
void clean(int u) {
  sz[u][0] = sz[u][1] = 0;
  col1[u] = col2[u] = false;
  for (int i = fr[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    clean(v);
  }
  fr[u] = 0;
}
};  // namespace Tree
int main() {
  scanf("%d%d", &n, &m);
  scanf("%s", s + 1);
  reverse(s + 1, s + n + 1);
  for (int i = 1; i <= n; ++i) ins(s[i] - 'a');
  for (int i = 2; i <= cnt; ++i) add(pre[i], i);
  dep[1] = 1;
  dfs(1);
  lg2[0] = -1;
  for (int i = 1; i <= ct; ++i) lg2[i] = lg2[i >> 1] + 1;
  for (int j = 1; j <= 20; ++j)
    for (int i = 1; i <= ct - (1 << j) + 1; ++i)
      st[i][j] = (dep[st[i][j - 1]] < dep[st[i + (1 << j - 1)][j - 1]])
                     ? st[i][j - 1]
                     : st[i + (1 << j - 1)][j - 1];
  int w = 1;
  for (int i = 1; i <= n; ++i) ed[i] = w = tr[w][s[i] - 'a'];
  while (m--) {
    scanf("%d%d", &q1, &q2);
    crt = 0, ans = 0;
    for (int i = 1; i <= q1; ++i)
      scanf("%d", &Q1[i]), Q1[i] = n - Q1[i] + 1, col1[ed[Q1[i]]] = true,
                           r[++crt] = ed[Q1[i]];
    for (int i = 1; i <= q2; ++i)
      scanf("%d", &Q2[i]), Q2[i] = n - Q2[i] + 1, col2[ed[Q2[i]]] = true,
                           r[++crt] = ed[Q2[i]];
    sort(r + 1, r + crt + 1, cmp);
    crt = unique(r + 1, r + crt + 1) - r - 1;
    for (int i = 1; i <= crt; ++i) Tree::ins(r[i]);
    for (int i = 2; i <= Tree::t; ++i) Tree::add(Tree::st[i - 1], Tree::st[i]);
    Tree::dfs(Tree::st[1]);
    Tree::clean(Tree::st[1]);
    Tree::tot = Tree::t = 0;
    printf("%lld\n", ans);
  }
  return 0;
}