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;
inline int read() {
  register int X = 0;
  register char ch = 0;
  while (ch < 48 || ch > 57) ch = getchar();
  while (ch >= 48 && ch <= 57) X = X * 10 + (ch ^ 48), ch = getchar();
  return X;
}
struct Node {
  int t[26], f, len;
} a[200500 << 1];
int tn, las;
char str[200500];
void ins(int c) {
  int np = ++tn, p = las;
  las = np;
  a[np].len = a[p].len + 1;
  for (; p && !a[p].t[c]; p = a[p].f) a[p].t[c] = np;
  if (!p)
    a[np].f = 1;
  else {
    int v = a[p].t[c];
    if (a[p].len + 1 == a[v].len)
      a[np].f = v;
    else {
      int nv = ++tn;
      a[nv] = a[v];
      a[nv].len = a[p].len + 1;
      for (; p && a[p].t[c] == v; p = a[p].f) a[p].t[c] = nv;
      a[v].f = a[np].f = nv;
    }
  }
}
int tp[200500], dis[200500 << 1], p[21][200500 << 2], dfn[200500 << 1], tim;
bool cmp(int A, int B) { return dfn[A] < dfn[B]; }
vector<int> g[200500 << 1];
void dfspre(int num) {
  p[0][dfn[num] = ++tim] = num;
  for (int i = 0; i < g[num].size(); i++) {
    dis[g[num][i]] = dis[num] + 1;
    dfspre(g[num][i]);
    p[0][++tim] = num;
  }
}
int lg2[200500 << 2];
int minp(int u, int v) { return dis[u] < dis[v] ? u : v; }
void InitST() {
  for (int j = 0; (1 << (j + 1)) <= tim; j++)
    for (int i = 1; i + (1 << j) <= tim; i++)
      p[j + 1][i] = minp(p[j][i], p[j][i + (1 << j)]);
  for (int i = 2; i <= tim; i++) lg2[i] = lg2[i / 2] + 1;
}
int lca(int x, int y) {
  x = dfn[x];
  y = dfn[y];
  if (x > y) swap(x, y);
  int j = lg2[y - x + 1];
  return minp(p[j][x], p[j][y - (1 << j) + 1]);
}
int len, q, a1[200500], a2[200500], in[200500 << 1], ef, t[200500 << 1], tot;
inline void add(int pos) {
  if (in[pos] < ef) in[t[++tot] = pos] = ef;
}
int stk[200500 << 1], top;
long long sum;
int s1[200500 << 1], s2[200500 << 1];
void dfs(int num) {
  int sav = s1[num];
  for (int i = 0, v; i < g[num].size(); i++) {
    dfs(v = g[num][i]);
    s1[num] += s1[v];
    s2[num] += s2[v];
  }
  for (int i = 0; i < g[num].size(); i++)
    sum += 1ll * s1[g[num][i]] * (s2[num] - s2[g[num][i]]) * a[num].len;
  sum += 1ll * sav * s2[num] * a[num].len;
}
int main() {
  len = read();
  q = read();
  scanf("%s", str);
  las = tn = 1;
  for (int i = len - 1; i >= 0; i--) ins(str[i] - 'a');
  for (int i = len - 1, p = 1; i >= 0; i--) {
    p = a[p].t[str[i] - 'a'];
    tp[i + 1] = p;
  }
  for (int i = 2; i <= tn; i++) g[a[i].f].push_back(i);
  dfspre(1);
  InitST();
  for (int i = 1; i <= tn; i++) g[i].clear();
  for (int qt = 1, n1, n2; qt <= q; qt++) {
    n1 = read();
    n2 = read();
    ++ef;
    for (int i = 1, sav; i <= n1; i++) {
      add(sav = tp[read()]);
      s1[sav]++;
    }
    for (int i = 1, sav; i <= n2; i++) {
      add(sav = tp[read()]);
      s2[sav]++;
    }
    sort(t + 1, t + tot + 1, cmp);
    int tmp = tot;
    for (int i = 1; i < tmp; i++) add(lca(t[i], t[i + 1]));
    sort(t + 1, t + tot + 1, cmp);
    stk[top = 1] = t[1];
    for (int i = 2; i <= tot; i++) {
      while (lca(stk[top], t[i]) != stk[top]) top--;
      g[stk[top]].push_back(t[i]);
      stk[++top] = t[i];
    }
    sum = 0;
    dfs(t[1]);
    printf("%I64d\n", sum);
    for (int i = 1; i <= tot; i++) {
      s1[t[i]] = s2[t[i]] = 0;
      g[t[i]].clear();
    }
    tot = 0;
  }
  return 0;
}