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;
const int maxn = 2E5 + 5;
int n, m;
string str;
int where[maxn * 2], len[maxn * 2], fa[maxn * 2][22], dep[maxn * 2];
int TI, dfn[maxn * 2];
int white[maxn * 2], black[maxn * 2];
long long int ans;
struct edge {
  int from, to, next;
};
struct graph {
  edge E[maxn * 2];
  int size, head[maxn * 2];
  inline void add(int u, int v) {
    E[++size].to = v;
    E[size].next = head[u];
    E[size].from = u;
    head[u] = size;
  }
  void clear() {
    for (int i = 1; i <= size; ++i) head[E[i].from] = 0;
    size = 0;
  }
  void dfs(int u, int F, int d) {
    dep[u] = d;
    fa[u][0] = F;
    dfn[u] = ++TI;
    for (int i = 1; i < 22; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (int i = head[u]; i; i = E[i].next) dfs(E[i].to, u, d + 1);
  }
  void NO(int u) {
    white[u] = black[u] = 0;
    for (int i = head[u]; i; i = E[i].next) NO(E[i].to);
  }
  void calc(int u) {
    long long int tot = 0;
    if (white[u] == 1 && black[u] == 1) ++tot;
    for (int i = head[u]; i; i = E[i].next) {
      int v = E[i].to;
      calc(v);
      tot += (long long int)white[u] * (long long int)black[v];
      tot += (long long int)black[u] * (long long int)white[v];
      white[u] += white[v], black[u] += black[v];
    }
    ans += tot * (long long int)len[u];
  }
} T, G;
struct node {
  int len, fa, ch[26];
};
struct SAM {
  node t[maxn * 2];
  int last, tot;
  SAM() { last = tot = 1; }
  inline void insert(int x, int pos) {
    int now = ++tot, u = last;
    last = tot;
    where[pos] = tot;
    t[now].len = t[u].len + 1;
    for (; u && !t[u].ch[x]; u = t[u].fa) t[u].ch[x] = now;
    if (!u)
      t[now].fa = 1;
    else {
      int v = t[u].ch[x];
      if (t[v].len == t[u].len + 1)
        t[now].fa = v;
      else {
        int w = ++tot;
        t[w] = t[v];
        t[w].len = t[u].len + 1;
        t[v].fa = t[now].fa = w;
        for (; u && t[u].ch[x] == v; u = t[u].fa) t[u].ch[x] = w;
      }
    }
  }
  void build() {
    for (int i = 2; i <= tot; ++i) {
      T.add(t[i].fa, i);
      len[i] = t[i].len;
    }
  }
} S;
int a[maxn], b[maxn], wait[maxn], sta[maxn * 2];
inline int lca(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  int d = dep[x] - dep[y];
  for (int i = 0; i < 22; ++i)
    if (d & (1 << i)) x = fa[x][i];
  if (x == y) return x;
  for (int i = 21; i >= 0; --i)
    if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
  return fa[x][0];
}
inline int cmp(int x, int y) { return dfn[x] < dfn[y]; }
inline void solve() {
  int k1, k2, tot = 0, top = 0;
  cin >> k1 >> k2;
  for (int i = 1; i <= k1; ++i) {
    cin >> a[i];
    a[i] = where[n - a[i] + 1];
    white[a[i]] = 1;
    wait[++tot] = a[i];
  }
  for (int i = 1; i <= k2; ++i) {
    cin >> b[i];
    b[i] = where[n - b[i] + 1];
    black[b[i]] = 1;
    wait[++tot] = b[i];
  }
  wait[++tot] = 1;
  sort(wait + 1, wait + tot + 1, cmp);
  G.clear();
  for (int i = 1; i <= tot; ++i) {
    if (wait[i] == wait[i - 1]) continue;
    while (top >= 2) {
      int F = lca(wait[i], sta[top]);
      if (dep[F] == dep[sta[top]])
        break;
      else if (dep[F] >= dep[sta[top - 1]]) {
        G.add(F, sta[top]);
        --top;
        if (sta[top] != F) sta[++top] = F;
      } else {
        G.add(sta[top - 1], sta[top]);
        --top;
      }
    }
    sta[++top] = wait[i];
  }
  while (top >= 2) {
    G.add(sta[top - 1], sta[top]);
    --top;
  }
  ans = 0;
  G.calc(1);
  G.NO(1);
  cout << ans << endl;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m >> str;
  reverse(str.begin(), str.end());
  for (int i = 0; i < n; ++i) S.insert(str[i] - 'a', i + 1);
  S.build();
  T.dfs(1, 1, 0);
  while (m--) solve();
  return 0;
}