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 = 2e5 + 10;
struct state {
  int len, link;
  int next[26];
};
state st[N << 1];
int sz, last;
void init() { sz = last = 1; }
int val[N << 1], endpos[N];
void extend(int c, int id) {
  int cur = ++sz, p;
  endpos[id] = cur;
  val[cur] = 1;
  st[cur].len = st[last].len + 1;
  for (p = last; p && !st[p].next[c]; p = st[p].link) st[p].next[c] = cur;
  if (!p)
    st[cur].link = 1;
  else {
    long long q = st[p].next[c];
    if (st[p].len + 1 == st[q].len)
      st[cur].link = q;
    else {
      long long clone = ++sz;
      st[clone].len = st[p].len + 1;
      st[clone].link = st[q].link;
      memcpy(st[clone].next, st[q].next, sizeof(st[clone].next));
      for (; p && st[p].next[c] == q; p = st[p].link) st[p].next[c] = clone;
      st[q].link = st[cur].link = clone;
    }
  }
  last = cur;
}
struct E {
  int to, nex;
} e[N << 1];
int head[N << 1], ecnt;
void adde(int fr, int to) {
  e[++ecnt] = (E){to, head[fr]};
  head[fr] = ecnt;
}
int dfn[N << 1], clk, tdfn[N << 1];
int jp[N << 1][18], dep[N << 1];
int lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  int del = dep[u] - dep[v];
  for (int j = 17; j >= 0; j--)
    if (del & (1 << j)) u = jp[u][j];
  if (u == v) return u;
  for (int j = 16; j >= 0; j--)
    if (jp[u][j] != jp[v][j]) {
      u = jp[u][j];
      v = jp[v][j];
    }
  return jp[u][0];
}
void init2() {
  for (int j = 1; j < 18; j++)
    for (int i = 1; i <= sz; i++) {
      jp[i][j] = jp[jp[i][j - 1]][j - 1];
    }
}
void dfs(int o, int fa) {
  jp[o][0] = fa;
  dep[o] = dep[fa] + 1;
  dfn[++clk] = o;
  tdfn[o] = clk;
  for (int j = head[o]; j; j = e[j].nex) {
    int v = e[j].to;
    dfs(v, o);
  }
}
vector<int> G[N << 1];
void addE(int fr, int to) { G[fr].push_back(to); }
long long ans;
int col[N << 1], siz[N << 1][2];
int mul(int x, int y) { return (long long)x * y; }
void dp(int x) {
  siz[x][0] = siz[x][1] = 0;
  if (col[x] & 1) siz[x][0] = val[x];
  if (col[x] & 2) siz[x][1] = val[x];
  ans += mul(st[x].len, mul(siz[x][0], siz[x][1]));
  for (int j = 0; j < G[x].size(); j++) {
    dp(G[x][j]);
    ans += mul(st[x].len, mul(siz[x][0], siz[G[x][j]][1]));
    ans += mul(st[x].len, mul(siz[x][1], siz[G[x][j]][0]));
    siz[x][0] += siz[G[x][j]][0];
    siz[x][1] += siz[G[x][j]][1];
  }
  G[x].clear();
}
char s[N];
int n, q;
int sta[N << 1], top;
int a[N], acnt;
bool cmp(int x, int y) { return tdfn[x] < tdfn[y]; }
int main() {
  scanf("%d%d", &n, &q);
  scanf("%s", s + 1);
  init();
  for (int i = n; i >= 1; i--) {
    extend(s[i] - 'a', i);
  }
  for (int i = 2; i <= sz; i++) adde(st[i].link, i);
  dep[1] = -1;
  dfs(1, 1);
  init2();
  while (q--) {
    int k, l;
    acnt = 0;
    cin >> k >> l;
    for (int i = 1; i <= k; i++) {
      int tmp;
      scanf("%d", &tmp);
      col[endpos[tmp]] |= 1;
      a[++acnt] = endpos[tmp];
    }
    for (int i = 1; i <= l; i++) {
      int tmp;
      scanf("%d", &tmp);
      col[endpos[tmp]] |= 2;
      a[++acnt] = endpos[tmp];
    }
    sort(a + 1, a + 1 + acnt, cmp);
    acnt = unique(a + 1, a + 1 + acnt) - a - 1;
    sta[top = 1] = 1;
    for (int i = 1; i <= acnt; i++) {
      int p = a[i], x = sta[top], lca = ::lca(p, x);
      if (top == 1 || lca == sta[top]) {
        sta[++top] = a[i];
      } else {
        while (top >= 2 && tdfn[sta[top - 1]] >= tdfn[lca]) {
          addE(sta[top - 1], sta[top]);
          top--;
        }
        if (sta[top] != lca) {
          addE(lca, sta[top]);
          sta[top] = lca;
        }
        sta[++top] = a[i];
      }
    }
    while (top > 1) {
      addE(sta[top - 1], sta[top]);
      top--;
    }
    ans = 0;
    dp(1);
    printf("%lld\n", ans);
    for (int i = 1; i <= acnt; i++) col[a[i]] = 0;
  }
  return 0;
}