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>
#pragma warning(disable : 4996)
using namespace std;
int n, q;
const int bign = 200033;
int alist[bign], blist[bign];
int asize, bsize;
int A[2][bign];
int mhead[bign];
int nxt[bign];
int sa[bign];
char str[bign];
int mrank[bign];
int LOG2[bign];
int mheight[bign][20];
int sumcnt[4 * bign];
int tcover[4 * bign];
long long sumheight[4 * bign];
int op;
int mtotal;
bool cmp(int x1, int y1) { return A[op][x1] < A[op][y1]; }
inline void solve() {
  int m = 27;
  for (int i = 0; i < n; i++) {
    sa[i] = i;
  }
  sort(sa, sa + n, cmp);
  op = 0;
  for (int i = 1; i < n; i <<= 1) {
    memset(mhead, -1, m * sizeof(int));
    op ^= 1;
    for (int j = n - 1; j >= 0; j--) {
      if (sa[j] >= i) {
        int u = sa[j] - i;
        nxt[u] = mhead[A[op ^ 1][u]];
        mhead[A[op ^ 1][u]] = u;
      }
    }
    for (int j = n - i; j < n; j++) {
      nxt[j] = mhead[A[op ^ 1][j]];
      mhead[A[op ^ 1][j]] = j;
    }
    int mlast;
    int tm = -1;
    int xid = 0;
    for (int j = 0; j < m; j++) {
      mlast = -1;
      for (int k = mhead[j]; k >= 0; k = nxt[k]) {
        if (mlast >= 0 && k + i < n && A[op ^ 1][k + i] == mlast) {
        } else {
          tm++;
        }
        sa[xid++] = k;
        A[op][k] = tm;
        if (k + i < n) mlast = A[op ^ 1][k + i];
      }
    }
    m = tm + 1;
  }
  memcpy(mrank, A[op], n * sizeof(int));
}
inline void calcHeight() {
  int nowh = 0;
  for (int i = 0; i < n - 1; i++) {
    int j = sa[mrank[i] - 1];
    while (str[i + nowh] == str[j + nowh]) {
      nowh++;
    }
    mheight[mrank[i]][0] = nowh;
    if (nowh) nowh--;
  }
}
inline void initRmq() {
  LOG2[1] = 0;
  for (int i = 2; i <= n; i++) {
    LOG2[i] = LOG2[i >> 1] + 1;
  }
  for (int i = 1; i <= LOG2[n - 1]; i++) {
    for (int j = 1; j + (1 << i) <= n; j++)
      mheight[j][i] = min(mheight[j][i - 1], mheight[j + (1 << i - 1)][i - 1]);
  }
}
inline int Query(int a, int b) {
  if (b < a) {
    return n - sa[b] - 1;
  }
  int x = LOG2[b - a];
  return min(mheight[a][x], mheight[b - (1 << x) + 1][x]);
}
inline void pushup(int tid) {
  sumcnt[tid] = sumcnt[tid << 1] + sumcnt[(tid << 1) + 1];
  sumheight[tid] = sumheight[tid << 1] + sumheight[(tid << 1) + 1];
}
void mcover(int tb, int te, int b1, int e1, int tid) {
  if (tb >= b1 && te <= e1) {
    mtotal += sumcnt[tid];
    tcover[tid] = 1;
    sumcnt[tid] = 0;
    sumheight[tid] = 0;
    return;
  }
  int mid = (tb + te) >> 1;
  if (tcover[tid] == 1) {
    tcover[tid] = 0;
    tcover[tid << 1] = 1;
    sumcnt[tid << 1] = 0;
    sumheight[tid << 1] = 0;
    tcover[(tid << 1) + 1] = 1;
    sumcnt[(tid << 1) + 1] = 0;
    sumheight[(tid << 1) + 1] = 0;
  }
  if (b1 <= mid) {
    mcover(tb, mid, b1, e1, tid << 1);
  }
  if (e1 > mid) {
    mcover(mid + 1, te, b1, e1, (tid << 1) + 1);
  }
  pushup(tid);
}
inline void mupdate(int tb, int te, int x, int tid, int tnum) {
  if (tb == te) {
    tcover[tid] = 0;
    sumcnt[tid] += tnum;
    sumheight[tid] += 1ll * x * tnum;
    return;
  }
  if (tcover[tid] == 1) {
    tcover[tid] = 0;
    tcover[tid << 1] = 1;
    sumcnt[tid << 1] = 0;
    sumheight[tid << 1] = 0;
    tcover[(tid << 1) + 1] = 1;
    sumcnt[(tid << 1) + 1] = 0;
    sumheight[(tid << 1) + 1] = 0;
  }
  int mid = (tb + te) >> 1;
  if (x <= mid) {
    mupdate(tb, mid, x, tid << 1, tnum);
  } else {
    mupdate(mid + 1, te, x, (tid << 1) + 1, tnum);
  }
  pushup(tid);
}
int main() {
  scanf("%d%d", &n, &q);
  scanf("%s", str);
  for (int i = 0; i < n; i++) {
    A[0][i] = str[i] - 'a' + 1;
  }
  n++;
  solve();
  calcHeight();
  initRmq();
  for (int i = 0; i < q; i++) {
    scanf("%d%d", &asize, &bsize);
    for (int j = 0; j < asize; j++) {
      scanf("%d", alist + j);
      alist[j]--;
    }
    sort(alist, alist + asize, cmp);
    for (int j = 0; j < bsize; j++) {
      scanf("%d", blist + j);
      blist[j]--;
    }
    sort(blist, blist + bsize, cmp);
    mcover(1, n - 1, 1, n - 1, 1);
    int j = 0;
    long long ans = 0;
    for (int i = 0; i < asize; i++) {
      int tmp = mrank[alist[i]];
      if (i) {
        int x = Query(mrank[alist[i - 1]] + 1, tmp);
        mtotal = 0;
        mcover(1, n - 1, x + 1, n - 1, 1);
        mupdate(1, n - 1, x, 1, mtotal);
      }
      while (mrank[blist[j]] <= tmp && j < bsize) {
        int tlcp = Query(mrank[blist[j]] + 1, tmp);
        mupdate(1, n - 1, tlcp, 1, 1);
        j++;
      }
      ans += sumheight[1];
    }
    mcover(1, n - 1, 1, n - 1, 1);
    j = bsize - 1;
    for (int i = asize - 1; i >= 0; i--) {
      int tmp = mrank[alist[i]];
      if (i != asize - 1) {
        int x = Query(tmp + 1, mrank[alist[i + 1]]);
        mtotal = 0;
        mcover(1, n - 1, x + 1, n - 1, 1);
        mupdate(1, n - 1, x, 1, mtotal);
      }
      while (j >= 0 && mrank[blist[j]] > tmp) {
        int tlcp = Query(tmp + 1, mrank[blist[j]]);
        mupdate(1, n - 1, tlcp, 1, 1);
        j--;
      }
      ans += sumheight[1];
    }
    printf("%lld\n", ans);
  }
}