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 N = 2 * 1e5 + 10;
int n;
int m;
char mde[N];
int v[2 * N];
int x[2 * N];
int ct;
int al[2 * N];
int len[2 * N];
int fa[2 * N][22];
int dep[2 * N];
int dfi[2 * N];
int dfo[2 * N];
int df;
bool book[2 * N];
int op[4 * N];
int tpop;
int st[2 * N];
int tp;
int dp[2 * N][2];
inline bool cmp(int a, int b) {
  return ((a < 0) ? dfo[-a] : dfi[a]) < ((b < 0) ? dfo[-b] : dfi[b]);
}
inline void add(int u, int V) {
  v[++ct] = V;
  x[ct] = al[u];
  al[u] = ct;
}
struct suffixautomaton {
  int mp[2 * N][30];
  int fa[2 * N];
  int ct;
  inline void ih() {
    for (int i = 1; i <= n; i++) len[i] = i;
    ct = n + 1;
  }
  inline void ins(int nw, int c) {
    int p = (nw == 1) ? n + 1 : nw - 1;
    for (; p && mp[p][c] == 0; p = fa[p]) mp[p][c] = nw;
    if (p == 0) {
      fa[nw] = n + 1;
      return;
    }
    int q = mp[p][c];
    if (len[q] == len[p] + 1) {
      fa[nw] = q;
      return;
    }
    ++ct;
    len[ct] = len[p] + 1;
    for (int i = 1; i <= 26; i++) mp[ct][i] = mp[q][i];
    for (; p && mp[p][c] == q; p = fa[p]) mp[p][c] = ct;
    fa[ct] = fa[q];
    fa[q] = fa[nw] = ct;
  }
  inline void build() {
    for (int i = 1; i <= ct; i++)
      if (fa[i]) add(fa[i], i);
  }
} sam;
inline void dfs(int u) {
  dfi[u] = ++df;
  for (int i = 0; fa[u][i]; i++) fa[u][i + 1] = fa[fa[u][i]][i];
  dep[u] = dep[fa[u][0]] + 1;
  for (int i = al[u]; i; i = x[i]) fa[v[i]][0] = u, dfs(v[i]);
  dfo[u] = ++df;
}
inline int lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  for (int d = dep[u] - dep[v], i = 0; d; d >>= 1, i++)
    if (d & 1) u = fa[u][i];
  if (u == v) return u;
  for (int i = 18; i >= 0; i--)
    if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
  return fa[u][0];
}
int main() {
  scanf("%d%d", &n, &m);
  scanf("%s", mde + 1);
  sam.ih();
  reverse(mde + 1, mde + n + 1);
  for (int i = 1; i <= n; i++) sam.ins(i, mde[i] - 'a' + 1);
  sam.build();
  dfs(n + 1);
  for (int z = 1, k1, k2; z <= m; z++) {
    scanf("%d%d", &k1, &k2);
    tpop = 0;
    for (int i = 1, t; i <= k1; i++)
      scanf("%d", &t), t = n - t + 1, dp[t][0] = 1, op[++tpop] = t,
                       book[t] = true;
    for (int i = 1, t; i <= k2; i++) {
      scanf("%d", &t), t = n - t + 1, dp[t][1] = 1;
      if (!book[t]) op[++tpop] = t, book[t] = true;
    }
    sort(op + 1, op + tpop + 1, cmp);
    for (int i = 1, lim = tpop, lc; i < lim; i++) {
      lc = lca(op[i], op[i + 1]);
      if (!book[lc]) op[++tpop] = lc, book[lc] = true;
    }
    for (int i = 1; i <= tpop; i++) book[op[i]] = false;
    for (int i = 1, lim = tpop; i <= lim; i++) op[++tpop] = -op[i];
    sort(op + 1, op + tpop + 1, cmp);
    long long ans = 0;
    for (int i = 1; i <= tpop; i++)
      if (op[i] > 0) {
        int u = op[i];
        st[++tp] = u;
        ans += (long long)len[u] * dp[u][0] * dp[u][1];
      } else {
        if (tp == 1) {
          dp[st[tp]][0] = dp[st[tp]][1] = 0;
          tp--;
          continue;
        }
        int u = st[tp];
        tp--;
        int f = st[tp];
        ans += (long long)len[f] * ((long long)dp[f][0] * dp[u][1] +
                                    (long long)dp[f][1] * dp[u][0]);
        dp[f][0] += dp[u][0];
        dp[f][1] += dp[u][1];
        dp[u][0] = dp[u][1] = 0;
      }
    printf("%lld\n", ans);
  }
  return 0;
}