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;
int bo;
int n, q, p[200005], dep[400005], top[400005], size[400005], fa[400005],
    son[400005], dfn[400005], ind[400005], m1, m2;
long long ans, b[400005];
char s[200005];
struct segment_tree {
  long long a[3200005], lazy[3200005], c[3200005];
  int bo[3200005];
  void build(int l, int r, int k) {
    if (l == r) {
      c[k] = b[ind[l]];
      return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, k << 1);
    build(mid + 1, r, (k << 1) | 1);
    c[k] = c[k << 1] + c[(k << 1) | 1];
  }
  void update(int l, int r, int k, int x, int y, long long z) {
    if (bo[k]) {
      bo[k] = 0;
      bo[k << 1] = bo[(k << 1) | 1] = 1;
      a[k] = lazy[k] = 0;
    }
    if (l >= x && r <= y) {
      lazy[k] += z;
      a[k] += z * c[k];
      return;
    }
    long long t = lazy[k];
    k <<= 1;
    if (bo[k]) {
      bo[k] = 0;
      bo[k << 1] = bo[(k << 1) | 1] = 1;
      a[k] = lazy[k] = 0;
    }
    ++k;
    if (bo[k]) {
      bo[k] = 0;
      bo[k << 1] = bo[(k << 1) | 1] = 1;
      a[k] = lazy[k] = 0;
    }
    k >>= 1;
    a[(k << 1) | 1] += t * c[(k << 1) | 1];
    a[k << 1] += t * c[k << 1];
    lazy[(k << 1) | 1] += t;
    lazy[k << 1] += t;
    lazy[k] = 0;
    int mid = (l + r) >> 1;
    if (x <= mid) update(l, mid, k << 1, x, y, z);
    if (y > mid) update(mid + 1, r, (k << 1) | 1, x, y, z);
    a[k] = a[k << 1] + a[(k << 1) | 1];
  }
  long long find(int l, int r, int k, int x, int y) {
    if (bo[k]) {
      bo[k] = 0;
      bo[k << 1] = bo[(k << 1) | 1] = 1;
      a[k] = lazy[k] = 0;
    }
    if (l >= x && r <= y) return a[k];
    long long t = lazy[k];
    k <<= 1;
    if (bo[k]) {
      bo[k] = 0;
      bo[k << 1] = bo[(k << 1) | 1] = 1;
      a[k] = lazy[k] = 0;
    }
    ++k;
    if (bo[k]) {
      bo[k] = 0;
      bo[k << 1] = bo[(k << 1) | 1] = 1;
      a[k] = lazy[k] = 0;
    }
    k >>= 1;
    a[(k << 1) | 1] += t * c[(k << 1) | 1];
    a[k << 1] += t * c[k << 1];
    lazy[(k << 1) | 1] += t;
    lazy[k << 1] += t;
    lazy[k] = 0;
    int mid = (l + r) >> 1;
    long long ans = 0;
    if (x <= mid) ans += find(l, mid, k << 1, x, y);
    if (y > mid) ans += find(mid + 1, r, (k << 1) | 1, x, y);
    return ans;
  }
} st;
struct sam_point {
  int len, fa, son[26];
};
struct SAM {
  int m = 0, n = 1, last = 1, len, nex[400005], wen[400005], hea[400005];
  sam_point a[400005];
  void add(int x, int y) {
    ++len;
    nex[len] = hea[x];
    wen[len] = y;
    hea[x] = len;
  }
  void insert(int x) {
    int p1 = last, p2 = ++n;
    last = n;
    a[p2].len = a[p1].len + 1;
    for (; p1 && !a[p1].son[x]; p1 = a[p1].fa) a[p1].son[x] = p2;
    if (!p1)
      a[p2].fa = 1;
    else {
      int q1 = a[p1].son[x];
      if (a[p1].len + 1 == a[q1].len)
        a[p2].fa = q1;
      else {
        int q2 = ++n;
        a[q2] = a[q1];
        a[q2].len = a[p1].len + 1;
        a[q1].fa = a[p2].fa = q2;
        for (; p1 && a[p1].son[x] == q1; p1 = a[p1].fa) a[p1].son[x] = q2;
      }
    }
  }
  void dfs(int x) {
    dep[x] = dep[fa[x]] + 1;
    size[x] = 1;
    for (int i = hea[x]; i; i = nex[i]) {
      dfs(wen[i]);
      if (size[son[x]] < size[wen[i]]) son[x] = wen[i];
      size[x] += size[wen[i]];
    }
  }
  void dfs1(int x) {
    dfn[x] = ++m;
    ind[m] = x;
    top[x] = son[fa[x]] == x ? top[fa[x]] : x;
    if (son[x]) dfs1(son[x]);
    for (int i = hea[x]; i; i = nex[i])
      if (wen[i] != son[x]) dfs1(wen[i]);
  }
  void build() {
    for (int i = 2; i <= n; i++)
      add(fa[i] = a[i].fa, i), b[i] = a[i].len - a[fa[i]].len;
    dfs(1);
    dfs1(1);
  }
  void update(int x) {
    while (x) {
      if (dfn[top[x]] <= dfn[x]) st.update(1, n, 1, dfn[top[x]], dfn[x], 1);
      x = fa[top[x]];
    }
  }
  long long find(int x) {
    long long ans = 0;
    while (x) {
      if (dfn[top[x]] <= dfn[x]) ans += st.find(1, n, 1, dfn[top[x]], dfn[x]);
      x = fa[top[x]];
    }
    return ans;
  }
} sam;
int main() {
  scanf("%d%d", &n, &q);
  scanf("%s", s + 1);
  for (int i = n; i; i--) p[i] = sam.n + 1, sam.insert(s[i] - 97);
  sam.build();
  st.build(1, sam.n, 1);
  do {
    --q;
    scanf("%d%d", &m1, &m2);
    st.bo[1] = 1;
    for (int i = 1; i <= m1; i++) {
      int x;
      scanf("%d", &x);
      sam.update(p[x]);
    }
    for (int i = 1; i <= m2; i++) {
      int x;
      scanf("%d", &x);
      ans += sam.find(p[x]);
    }
    printf("%lld\n", ans);
    ans = 0;
  } while (q);
  return 0;
}