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 = 400005;
inline int read() {
  int a = 0, c;
  do c = getchar();
  while (!isdigit(c));
  while (isdigit(c)) {
    a = a * 10 + c - '0';
    c = getchar();
  }
  return a;
}
int chl[MAXN][26], maxl[MAXN], fa[MAXN], top = 1, root = 1, last = 1;
int n, q;
char str[MAXN];
inline int push(int x) {
  int p = last, np = ++top;
  maxl[np] = maxl[last] + 1;
  while (p && !chl[p][x]) chl[p][x] = np, p = fa[p];
  if (!p)
    fa[np] = root;
  else {
    int q = chl[p][x];
    if (maxl[q] == maxl[p] + 1)
      fa[np] = q;
    else {
      int nq = ++top;
      maxl[nq] = maxl[p] + 1;
      memcpy(chl[nq], chl[q], sizeof chl[q]);
      fa[nq] = fa[q], fa[q] = fa[np] = nq;
      while (p && chl[p][x] == q) chl[p][x] = nq, p = fa[p];
    }
  }
  return last = np;
}
struct node {
  int to, next;
} edge[MAXN], e[MAXN];
int head[MAXN], tot = 0;
int h[MAXN], t = 0;
inline void push(int i, int j) {
  edge[++tot] = (node){j, head[i]}, head[i] = tot;
}
inline void push2(int i, int j) { e[++t] = (node){j, h[i]}, h[i] = t; }
int dfn[MAXN], dfn_top = 0, out[MAXN];
int father[20][MAXN], depth[MAXN];
int cur[MAXN];
void dfs(int nd) {
  dfn[nd] = ++dfn_top;
  for (int i = head[nd]; i; i = edge[i].next) {
    int to = edge[i].to;
    father[0][to] = nd, depth[to] = depth[nd] + 1;
    dfs(to);
  }
  out[nd] = dfn_top;
}
void readln() {
  scanf("%d%d", &n, &q);
  scanf("%s", str + 1);
  for (int i = n; i >= 1; i--) cur[i] = push(str[i] - 'a');
  for (int i = 1; i <= top; i++)
    if (fa[i]) {
      push(fa[i], i);
    }
  dfs(root);
  for (int i = 1; i < 20; i++)
    for (int j = 1; j <= top; j++)
      father[i][j] = father[i - 1][father[i - 1][j]];
}
inline int lca(int a, int b) {
  if (depth[a] < depth[b]) swap(a, b);
  for (int i = 0, d = depth[a] - depth[b]; i < 20; i++)
    if (d >> i & 1) a = father[i][a];
  if (a == b) return a;
  for (int i = 19; i >= 0; i--)
    if (father[i][a] != father[i][b]) a = father[i][a], b = father[i][b];
  return father[0][a];
}
inline bool inside(int a, int T) {
  return dfn[T] <= dfn[a] && dfn[a] <= out[T];
}
int dp[MAXN][2];
int color[MAXN][2];
inline void do_dp(int nd, long long &ans) {
  dp[nd][0] = dp[nd][1] = 0;
  for (int j = 0; j < 2; j++) dp[nd][j] += color[nd][j];
  ans += 1ll * maxl[nd] * dp[nd][0] * dp[nd][1];
  for (int i = h[nd]; i; i = e[i].next) {
    int to = e[i].to;
    do_dp(to, ans);
    for (int j = 0; j < 2; j++)
      ans += 1ll * maxl[nd] * dp[nd][j] * dp[to][j ^ 1];
    for (int j = 0; j < 2; j++) dp[nd][j] += dp[to][j];
  }
}
long long build_vtree(int a[], int k) {
  sort(a + 1, a + k + 1, [](int x, int y) { return dfn[x] < dfn[y]; });
  k = unique(a + 1, a + k + 1) - a - 1;
  static int stk[MAXN];
  int stk_top = 0;
  static int vis[MAXN];
  int vis_top = 0;
  for (int i = 1; i <= k; i++) vis[++vis_top] = a[i];
  stk[++stk_top] = a[1];
  for (int i = 2; i <= k; i++) {
    int nd = a[i];
    while (stk_top >= 2 && !inside(nd, stk[stk_top]) &&
           !inside(nd, stk[stk_top - 1])) {
      push2(stk[stk_top - 1], stk[stk_top]);
      stk_top--;
    }
    if (inside(nd, stk[stk_top])) {
      stk[++stk_top] = nd;
    } else {
      int c = lca(stk[stk_top], nd);
      if (stk_top > 1 && stk[stk_top - 1] == c) {
        push2(stk[stk_top - 1], stk[stk_top]);
        stk[stk_top] = nd;
      } else {
        vis[++vis_top] = c;
        push2(c, stk[stk_top]);
        stk[stk_top] = c;
        stk[++stk_top] = nd;
      }
    }
  }
  while (stk_top > 1) {
    push2(stk[stk_top - 1], stk[stk_top]);
    stk_top--;
  }
  stk_top = 0;
  long long ans = 0;
  int rt = a[1];
  for (int i = 1; i <= vis_top; i++)
    if (depth[vis[i]] < depth[rt]) rt = vis[i];
  do_dp(rt, ans);
  while (vis_top) h[vis[vis_top--]] = 0;
  t = 0;
  return ans;
}
void solve() {
  int k, l;
  k = read(), l = read();
  static int a[MAXN];
  int top = 0;
  for (int i = 1; i <= k; i++) {
    int bx = cur[read()];
    color[bx][0]++;
    a[++top] = bx;
  }
  for (int i = 1; i <= l; i++) {
    int wx = cur[read()];
    color[wx][1]++;
    a[++top] = wx;
  }
  printf("%lld\n", build_vtree(a, top));
  for (int i = 1; i <= top; i++) color[a[i]][0] = color[a[i]][1] = 0;
}
int main() {
  readln();
  while (q--) solve();
  return 0;
}