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 bool isdigit(char ch) { return ch >= '0' && ch <= '9'; }
inline int read() {
  int res = 0, f = 1;
  char ch;
  while (!isdigit(ch = getchar()))
    if (ch == '-') f = -1;
  do {
    res = res * 10 + ch - '0';
  } while (isdigit(ch = getchar()));
  return res * f;
}
const int N = 1e6 + 5;
int n, q;
char S[N];
int link[N], ch[N][26];
int len[N];
int rev[N];
int lst = 1, cnt = 1;
inline void insert(int pos) {
  int c = S[pos] - 'a';
  int np = ++cnt, p = lst;
  len[np] = len[lst] + 1;
  while (p && !ch[p][c]) ch[p][c] = np, p = link[p];
  if (!p)
    link[np] = 1;
  else {
    int q = ch[p][c];
    if (len[q] == len[p] + 1)
      link[np] = q;
    else {
      int nq = ++cnt;
      len[nq] = len[p] + 1, link[nq] = link[q];
      for (int i = 0; i < 26; ++i) ch[nq][i] = ch[q][i];
      while (p && ch[p][c] == q) ch[p][c] = nq, p = link[p];
      link[np] = link[q] = nq;
    }
  }
  lst = np, rev[pos] = np;
}
inline void readdata() {
  n = read(), q = read();
  scanf("%s", S + 1);
  for (int i = 1; i <= n / 2; ++i) swap(S[i], S[n - i + 1]);
}
struct Edge {
  int next, to;
} a[N << 1];
int head[N], sze;
inline void add(int u, int v) {
  a[++sze].next = head[u], a[sze].to = v, head[u] = sze;
}
inline void insert(int u, int v) { add(u, v), add(v, u); }
int f[N], son[N], top[N], dep[N], seg[N], size[N];
void dfs1(int u, int fa) {
  seg[u] = ++seg[0], size[u] = 1, dep[u] = dep[fa] + 1, f[u] = fa;
  for (int i = head[u]; i; i = a[i].next) {
    int v = a[i].to;
    if (v != fa)
      dfs1(v, u), size[u] += size[v],
          son[u] = (size[v] > size[son[u]]) ? v : son[u];
  }
}
void dfs2(int u) {
  int v = son[u];
  if (v) top[v] = top[u], dfs2(v);
  for (int i = head[u]; i; i = a[i].next) {
    v = a[i].to;
    if (!top[v]) top[v] = v, dfs2(v);
  }
}
inline int LCA(int x, int y) {
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]]) swap(x, y);
    x = f[top[x]];
  }
  return dep[x] < dep[y] ? x : y;
}
inline void build() {
  for (int i = 1; i <= n; ++i) insert(i);
  for (int i = 2; i <= cnt; ++i) insert(link[i], i);
  dfs1(1, 0);
  top[1] = 1;
  dfs2(1);
}
int l1, l2;
int p1[N], p2[N];
int w[N];
bool vis[N];
int s1[N], s2[N];
inline bool cmp(int a, int b) { return seg[a] < seg[b]; }
int s[N], ss[N], t, tt;
vector<int> vec[N];
long long ans;
void dp(int u) {
  ans += 1LL * s1[u] * s2[u] * len[u];
  for (unsigned i = 0; i < vec[u].size(); ++i) {
    int v = vec[u][i];
    dp(v);
    ans += 1LL * s1[u] * s2[v] * len[u];
    ans += 1LL * s2[u] * s1[v] * len[u];
    s1[u] += s1[v], s2[u] += s2[v];
  }
}
inline void solve() {
  while (q--) {
    l1 = read(), l2 = read();
    int num = 0;
    for (int i = 1; i <= l1; ++i) {
      p1[i] = n - read() + 1, ++s1[rev[p1[i]]];
      if (!vis[rev[p1[i]]]) w[++num] = rev[p1[i]], vis[rev[p1[i]]] = 1;
    }
    for (int i = 1; i <= l2; ++i) {
      p2[i] = n - read() + 1, ++s2[rev[p2[i]]];
      if (!vis[rev[p2[i]]]) w[++num] = rev[p2[i]], vis[rev[p2[i]]] = 1;
    }
    sort(w + 1, w + num + 1, cmp);
    s[t = 1] = 1, ss[tt = 1] = 1;
    for (int i = 1; i <= num; ++i) {
      if (w[i] == s[t]) continue;
      if (seg[s[t]] + size[s[t]] > seg[w[i]]) {
        s[++t] = w[i], ss[++tt] = w[i];
        continue;
      }
      while (t && seg[s[t - 1]] + size[s[t - 1]] <= seg[w[i]])
        vec[s[t - 1]].push_back(s[t]), --t;
      int lca = LCA(s[t], w[i]);
      vec[lca].push_back(s[t]);
      if (lca != s[t - 1])
        s[t] = lca, ss[++tt] = lca;
      else
        --t;
      s[++t] = w[i], ss[++tt] = w[i];
    }
    while (t > 1) vec[s[t - 1]].push_back(s[t]), --t;
    ans = 0, dp(1);
    printf("%lld\n", ans);
    for (int i = 1; i <= tt; ++i)
      vis[ss[i]] = s1[ss[i]] = s2[ss[i]] = 0, vec[ss[i]].clear();
  }
}
int main() {
  readdata();
  build();
  solve();
  return 0;
}