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;
vector<int> T[400005];
char s[200005];
long long Ans;
int N, M, n, m, cnt, tim;
int head[400005], to[400005], Next[400005];
int P[400005], vis[400005], pos[400005], siz1[400005], siz2[400005];
int fa[400005], dfn[400005], dep[400005], son[400005], top[400005],
    size[400005];
struct SAM {
  int tot, lst;
  struct Trans {
    int len, link;
    int Next[26];
  } s[400005];
  void Initialize() {
    s[0].link = -1;
    s[0].len = tot = lst = 0;
  }
  void Insert(char c) {
    int p = lst, Now = ++tot;
    s[Now].len = s[p].len + 1;
    while (~p && !s[p].Next[c - 'a']) {
      s[p].Next[c - 'a'] = Now;
      p = s[p].link;
    }
    if (p == -1)
      s[Now].link = 0;
    else {
      int q = s[p].Next[c - 'a'];
      if (s[q].len == s[p].len + 1)
        s[Now].link = q;
      else {
        int New = ++tot;
        s[New] = s[q];
        s[New].len = s[p].len + 1;
        while (~p && s[p].Next[c - 'a'] == q) {
          s[p].Next[c - 'a'] = New;
          p = s[p].link;
        }
        s[Now].link = s[q].link = New;
      }
    }
    lst = Now;
    return;
  }
} S;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = (x << 1) + (x << 3) + ch - '0';
    ch = getchar();
  }
  return x * f;
}
inline bool Cmp(int x, int y) { return dfn[x] < dfn[y]; }
inline void add(int u, int v) {
  to[++cnt] = v;
  Next[cnt] = head[u];
  head[u] = cnt;
}
void dfs1(int u, int f) {
  dfn[u] = ++tim;
  dep[u] = dep[fa[u] = f] + (size[u] = 1);
  for (register int i = head[u]; i; i = Next[i]) {
    int v = to[i];
    dfs1(v, u);
    size[u] += size[v];
    son[u] = size[v] > size[son[u]] ? v : son[u];
  }
  return;
}
void dfs2(int u, int f) {
  if (son[u]) {
    top[son[u]] = top[u];
    dfs2(son[u], u);
  }
  for (register int i = head[u]; i; i = Next[i]) {
    int v = to[i];
    if (!top[v]) {
      top[v] = v;
      dfs2(v, u);
    }
  }
  return;
}
int LCA(int x, int y) {
  int fx = top[x], fy = top[y];
  while (fx != fy) {
    if (dep[fx] < dep[fy]) {
      swap(x, y);
      swap(fx, fy);
    }
    x = fa[fx];
    fx = top[x];
  }
  return dep[x] < dep[y] ? x : y;
}
void build(int N) {
  static int top, s[400005];
  top = 0;
  sort(P + 1, P + N + 1, Cmp);
  if (P[1] != 1) s[++top] = 1;
  for (register int i = 1; i <= N; ++i) {
    int u = P[i];
    if (!top)
      s[++top] = u;
    else {
      int Lca = LCA(u, s[top]);
      while (top > 1 && dep[Lca] < dep[s[top - 1]])
        T[s[top - 1]].push_back(s[top]), --top;
      if (dep[Lca] < dep[s[top]]) T[Lca].push_back(s[top]), --top;
      if (!top || s[top] != Lca) s[++top] = Lca;
      s[++top] = u;
    }
  }
  if (top) {
    while (--top) T[s[top]].push_back(s[top + 1]);
  }
  return;
}
void Dfs1(int u) {
  Ans += 1LL * siz1[u] * siz2[u] * S.s[u - 1].len;
  for (register int i = 0; i < T[u].size(); ++i) {
    int v = T[u][i];
    Dfs1(v);
    Ans += 1LL * siz1[u] * siz2[v] * S.s[u - 1].len;
    Ans += 1LL * siz2[u] * siz1[v] * S.s[u - 1].len;
    siz1[u] += siz1[v];
    siz2[u] += siz2[v];
  }
  return;
}
void Dfs2(int u) {
  vis[u] = siz1[u] = siz2[u] = 0;
  for (register int i = 0; i < T[u].size(); ++i) {
    int v = T[u][i];
    Dfs2(v);
  }
  T[u].clear();
  return;
}
int main() {
  n = read();
  m = read();
  scanf("%s", s + 1);
  S.Initialize();
  for (register int i = n; i >= 1; --i) {
    S.Insert(s[i]);
    pos[i] = S.lst + 1;
  }
  for (register int i = 1; i <= S.tot; ++i) add(S.s[i].link + 1, i + 1);
  top[1] = 1;
  dfs1(1, 0);
  dfs2(1, 0);
  for (register int Q = 1; Q <= m; ++Q) {
    int num = 0;
    N = read();
    M = read();
    for (register int i = 1; i <= N; ++i) {
      int x = pos[read()];
      if (!vis[x]) {
        vis[x] = 1;
        P[++num] = x;
      }
      siz1[x] = 1;
    }
    for (register int i = 1; i <= M; ++i) {
      int x = pos[read()];
      if (!vis[x]) {
        vis[x] = 1;
        P[++num] = x;
      }
      siz2[x] = 1;
    }
    build(num);
    Dfs1(1);
    Dfs2(1);
    printf("%lld\n", Ans);
    Ans = 0;
  }
  return 0;
}