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;
template <class T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool f = 0;
  for (; c > '9' || c < '0'; f = c == '-', c = getchar())
    ;
  for (; c >= '0' && c <= '9'; x = (x << 1) + (x << 3) + c - '0', c = getchar())
    ;
  x = f ? -x : x;
}
template <class T>
inline void write(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) write(x / 10);
  putchar(x % 10 + 48);
}
template <class T>
inline bool chkmax(T &a, T const &b) {
  return a < b ? a = b, 1 : 0;
}
template <class T>
inline bool chkmin(T &a, T const &b) {
  return a > b ? a = b, 1 : 0;
}
const int N = 2e5 + 10;
struct edge {
  int to, nxt;
  edge() {}
  edge(int to, int nxt) : to(to), nxt(nxt) {}
} e[N * 4];
int ecnt, head[N * 2], color[N * 2], val[N * 2];
void addEdge(int u, int v) {
  e[++ecnt] = edge(v, head[u]), head[u] = ecnt;
  e[++ecnt] = edge(u, head[v]), head[v] = ecnt;
}
namespace treeChainDivison {
const int M = N * 2;
int dfsClock, top[M], size[M], fa[M], son[M], dep[M], l[M], r[M];
void dfs1(int u) {
  size[u] = 1;
  for (int i = head[u], v; i; i = e[i].nxt)
    if ((v = e[i].to) != fa[u]) {
      fa[v] = u;
      dep[v] = dep[u] + 1;
      dfs1(v);
      size[u] += size[v];
      if (size[v] > size[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int anc) {
  l[u] = ++dfsClock;
  top[u] = anc;
  if (son[u]) dfs2(son[u], anc);
  for (int i = head[u], v; i; i = e[i].nxt)
    if ((v = e[i].to) != fa[u] && v != son[u]) dfs2(v, v);
  r[u] = dfsClock;
}
void init(int root) {
  dfsClock = 0;
  dfs1(root);
  dfs2(root, root);
}
int getLca(int x, int y) {
  for (; top[x] != top[y]; x = fa[top[x]])
    if (dep[top[x]] < dep[top[y]]) swap(x, y);
  return dep[x] < dep[y] ? x : y;
}
}  // namespace treeChainDivison
namespace suffixAutomation {
struct node {
  node *par, *go[26];
  int mx, id;
} T[N * 2];
struct node *last, *root, *cur = T;
int endpos[N * 2];
node *newNode(int mx = 0) {
  static int id = 0;
  node *o = cur++;
  o->id = ++id;
  o->par = NULL;
  for (int i = 0; i < 26; ++i) o->go[i] = NULL;
  o->mx = mx;
  return o;
}
void extend(int c) {
  node *p = last, *np = newNode(p->mx + 1);
  for (; p && !p->go[c]; p = p->par) p->go[c] = np;
  if (!p)
    np->par = root;
  else {
    node *q = p->go[c];
    if (p->mx + 1 == q->mx)
      np->par = q;
    else {
      node *nq = newNode(p->mx + 1);
      memcpy(nq->go, q->go, sizeof q->go);
      nq->par = q->par;
      for (; p && p->go[c] == q; p = p->par) p->go[c] = nq;
      q->par = np->par = nq;
    }
  }
  last = np;
}
void init(char *s) {
  last = root = newNode();
  int len = strlen(s + 1);
  for (int i = 1; i <= len; ++i) extend(s[i] - 'a');
}
void build(char *s) {
  int len = strlen(s + 1);
  node *o = root + 1;
  for (; o != cur; ++o) {
    val[o->id] = o->mx;
    addEdge(o->id, o->par->id);
  }
  o = root;
  for (int i = 1; i <= len; ++i) {
    o = o->go[s[i] - 'a'];
    endpos[i] = o->id;
  }
}
}  // namespace suffixAutomation
namespace virtualTree {
const int M = N * 2;
int stk[M], f[M][2], fa[M];
bool vis[M];
bool cmp(const int &x, const int &y) {
  return treeChainDivison::l[x] < treeChainDivison::l[y];
}
long long solve(vector<int> ve) {
  long long res = 0;
  for (auto x : ve) {
    vis[x] = 1;
  }
  sort(ve.begin(), ve.end(), cmp);
  for (int i = 1, sz = ve.size(); i < sz; ++i) {
    int x = treeChainDivison::getLca(ve[i], ve[i - 1]);
    if (!vis[x]) {
      ve.push_back(x);
      vis[x] = 1;
    }
  }
  if (!vis[1]) {
    ve.push_back(1);
    vis[1] = 1;
  }
  sort(ve.begin(), ve.end(), cmp);
  stk[ *stk = 1] = ve[0];
  for (int i = 1; i < ve.size(); ++i) {
    for (; treeChainDivison::l[ve[i]] > treeChainDivison::r[stk[*stk]]; --*stk)
      ;
    fa[ve[i]] = stk[*stk];
    stk[++*stk] = ve[i];
  }
  for (int i = ve.size() - 1; i >= 0; --i) {
    int x = ve[i];
    if (x == 1) continue;
    if (color[x] >= 2) {
      res += (long long)f[x][0] * val[x];
      ++f[x][1];
      color[x] ^= 2;
    }
    if (color[x] >= 1) {
      res += (long long)f[x][1] * val[x];
      ++f[x][0];
      color[x] ^= 1;
    }
    int y = fa[x];
    res += (long long)f[y][0] * f[x][1] * val[y];
    res += (long long)f[y][1] * f[x][0] * val[y];
    f[y][0] += f[x][0];
    f[y][1] += f[x][1];
  }
  for (auto x : ve) {
    fa[x] = f[x][0] = f[x][1] = 0;
    vis[x] = 0;
  }
  color[1] = 0;
  return res;
}
}  // namespace virtualTree
int main() {
  int tim = clock();
  int n, q;
  static char s[N];
  read(n), read(q);
  scanf("%s", s + 1);
  int len = strlen(s + 1);
  reverse(s + 1, s + len + 1);
  suffixAutomation::init(s);
  suffixAutomation::build(s);
  treeChainDivison::init(1);
  vector<int> ve;
  for (int i = 1; i <= q; ++i) {
    int tim = clock();
    int k, l, a, b;
    ve.clear();
    read(k), read(l);
    for (int j = 1; j <= k; ++j) {
      read(a);
      a = suffixAutomation::endpos[len - a + 1];
      color[a] |= 1;
      ve.push_back(a);
    }
    for (int j = 1; j <= l; ++j) {
      read(b);
      b = suffixAutomation::endpos[len - b + 1];
      color[b] |= 2;
      ve.push_back(b);
    }
    sort(ve.begin(), ve.end());
    ve.erase(unique(ve.begin(), ve.end()), ve.end());
    write(virtualTree::solve(ve));
    puts("");
  }
}