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;
long long gcd(long long n1, long long n2) {
  if (!n1) return n2;
  if (!n2) return n1;
  if (n1 % n2 == 0) return n2;
  return gcd(n2, n1 % n2);
}
long long powmod(long long base, long long exponent) {
  base %= 1000000007;
  long long ans = 1;
  while (exponent) {
    if (exponent & 1) ans = (ans * base) % 1000000007;
    base = (base * base) % 1000000007;
    exponent /= 2;
  }
  ans %= 1000000007;
  return ans;
}
unsigned char mask[] = {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01};
const int maxn = 500005;
int sa[maxn];
int rankk[maxn];
unsigned char *s;
int nn;
void getBuckets(unsigned char *s, int *bkt, int nn, int K, int cs, bool end) {
  int i, sum = 0;
  for (i = 0; i <= K; i++) bkt[i] = 0;
  for (i = 0; i < nn; i++)
    bkt[(cs == sizeof(int) ? ((int *)s)[i] : ((unsigned char *)s)[i])]++;
  for (i = 0; i <= K; i++) {
    sum += bkt[i];
    bkt[i] = end ? sum : sum - bkt[i];
  }
}
void induceSAl(unsigned char *t, int *SA, unsigned char *s, int *bkt, int nn,
               int K, int cs, bool end) {
  int i, j;
  getBuckets(s, bkt, nn, K, cs, end);
  for (i = 0; i < nn; i++) {
    j = SA[i] - 1;
    if (j >= 0 && !((t[(j) / 8] & mask[(j) % 8]) ? 1 : 0))
      SA[bkt[(cs == sizeof(int) ? ((int *)s)[j] : ((unsigned char *)s)[j])]++] =
          j;
  }
}
void induceSAs(unsigned char *t, int *SA, unsigned char *s, int *bkt, int nn,
               int K, int cs, bool end) {
  int i, j;
  getBuckets(s, bkt, nn, K, cs, end);
  for (i = nn - 1; i >= 0; i--) {
    j = SA[i] - 1;
    if (j >= 0 && ((t[(j) / 8] & mask[(j) % 8]) ? 1 : 0))
      SA[--bkt[(cs == sizeof(int) ? ((int *)s)[j] : ((unsigned char *)s)[j])]] =
          j;
  }
}
void SA_IS(unsigned char *s, int *SA, int nn, int K, int cs) {
  int i, j;
  unsigned char *t = (unsigned char *)malloc(nn / 8 + 1);
  t[(nn - 2) / 8] = (0) ? (mask[(nn - 2) % 8] | t[(nn - 2) / 8])
                        : ((~mask[(nn - 2) % 8]) & t[(nn - 2) / 8]);
  t[(nn - 1) / 8] = (1) ? (mask[(nn - 1) % 8] | t[(nn - 1) / 8])
                        : ((~mask[(nn - 1) % 8]) & t[(nn - 1) / 8]);
  for (i = nn - 3; i >= 0; i--)
    t[(i) / 8] =
        (((cs == sizeof(int) ? ((int *)s)[i] : ((unsigned char *)s)[i]) <
              (cs == sizeof(int) ? ((int *)s)[i + 1]
                                 : ((unsigned char *)s)[i + 1]) ||
          ((cs == sizeof(int) ? ((int *)s)[i] : ((unsigned char *)s)[i]) ==
               (cs == sizeof(int) ? ((int *)s)[i + 1]
                                  : ((unsigned char *)s)[i + 1]) &&
           ((t[(i + 1) / 8] & mask[(i + 1) % 8]) ? 1 : 0) == 1))
             ? 1
             : 0)
            ? (mask[(i) % 8] | t[(i) / 8])
            : ((~mask[(i) % 8]) & t[(i) / 8]);
  int *bkt = (int *)malloc(sizeof(int) * (K + 1));
  getBuckets(s, bkt, nn, K, cs, true);
  for (i = 0; i < nn; i++) SA[i] = -1;
  for (i = 1; i < nn; i++)
    if ((i > 0 && ((t[(i) / 8] & mask[(i) % 8]) ? 1 : 0) &&
         !((t[(i - 1) / 8] & mask[(i - 1) % 8]) ? 1 : 0)))
      SA[--bkt[(cs == sizeof(int) ? ((int *)s)[i] : ((unsigned char *)s)[i])]] =
          i;
  induceSAl(t, SA, s, bkt, nn, K, cs, false);
  induceSAs(t, SA, s, bkt, nn, K, cs, true);
  free(bkt);
  int nn1 = 0;
  for (i = 0; i < nn; i++)
    if ((SA[i] > 0 && ((t[(SA[i]) / 8] & mask[(SA[i]) % 8]) ? 1 : 0) &&
         !((t[(SA[i] - 1) / 8] & mask[(SA[i] - 1) % 8]) ? 1 : 0)))
      SA[nn1++] = SA[i];
  for (i = nn1; i < nn; i++) SA[i] = -1;
  int nname = 0, prev = -1;
  for (i = 0; i < nn1; i++) {
    int pos = SA[i];
    bool diff = false;
    for (int d = 0; d < nn; d++)
      if (prev == -1 ||
          (cs == sizeof(int) ? ((int *)s)[pos + d]
                             : ((unsigned char *)s)[pos + d]) !=
              (cs == sizeof(int) ? ((int *)s)[prev + d]
                                 : ((unsigned char *)s)[prev + d]) ||
          ((t[(pos + d) / 8] & mask[(pos + d) % 8]) ? 1 : 0) !=
              ((t[(prev + d) / 8] & mask[(prev + d) % 8]) ? 1 : 0)) {
        diff = true;
        break;
      } else if (d > 0 &&
                 ((pos + d > 0 &&
                   ((t[(pos + d) / 8] & mask[(pos + d) % 8]) ? 1 : 0) &&
                   !((t[(pos + d - 1) / 8] & mask[(pos + d - 1) % 8]) ? 1
                                                                      : 0)) ||
                  (prev + d > 0 &&
                   ((t[(prev + d) / 8] & mask[(prev + d) % 8]) ? 1 : 0) &&
                   !((t[(prev + d - 1) / 8] & mask[(prev + d - 1) % 8]) ? 1
                                                                        : 0))))
        break;
    if (diff) {
      nname++;
      prev = pos;
    }
    pos = (pos % 2 == 0) ? pos / 2 : (pos - 1) / 2;
    SA[nn1 + pos] = nname - 1;
  }
  for (i = nn - 1, j = nn - 1; i >= nn1; i--)
    if (SA[i] >= 0) SA[j--] = SA[i];
  int *SA1 = SA, *s1 = SA + nn - nn1;
  if (nname < nn1)
    SA_IS((unsigned char *)s1, SA1, nn1, nname - 1, sizeof(int));
  else
    for (i = 0; i < nn1; i++) SA1[s1[i]] = i;
  bkt = (int *)malloc(sizeof(int) * (K + 1));
  getBuckets(s, bkt, nn, K, cs, true);
  for (i = 1, j = 0; i < nn; i++)
    if ((i > 0 && ((t[(i) / 8] & mask[(i) % 8]) ? 1 : 0) &&
         !((t[(i - 1) / 8] & mask[(i - 1) % 8]) ? 1 : 0)))
      s1[j++] = i;
  for (i = 0; i < nn1; i++) SA1[i] = s1[SA1[i]];
  for (i = nn1; i < nn; i++) SA[i] = -1;
  for (i = nn1 - 1; i >= 0; i--) {
    j = SA[i];
    SA[i] = -1;
    SA[--bkt[(cs == sizeof(int) ? ((int *)s)[j] : ((unsigned char *)s)[j])]] =
        j;
  }
  induceSAl(t, SA, s, bkt, nn, K, cs, false);
  induceSAs(t, SA, s, bkt, nn, K, cs, true);
  free(bkt);
  free(t);
}
vector<int> kasai(string txt, const vector<int> &suffixArr) {
  int n = suffixArr.size();
  vector<int> lcp(n, 0);
  vector<int> invSuff(n, 0);
  for (int i = 0; i < nn; i++) invSuff[suffixArr[i]] = i;
  int k = 0;
  for (int i = 0; i < n; i++) {
    if (invSuff[i] == n - 1) {
      k = 0;
      continue;
    }
    int j = suffixArr[invSuff[i] + 1];
    while (i + k < n && j + k < n && txt[i + k] == txt[j + k]) k++;
    lcp[invSuff[i]] = k;
    if (k > 0) k--;
  }
  return lcp;
}
vector<int> buildSA(string ss) {
  vector<int> temp;
  nn = ss.size();
  s = (unsigned char *)ss.c_str();
  SA_IS(s, sa, nn + 1, 256, 1);
  for (int i = 1; i <= nn; i++) temp.push_back(sa[i]);
  return temp;
}
struct data {
  long long mx, sum, cnt;
  data() {
    mx = 0;
    sum = 0;
    cnt = 0;
  }
};
data merge(data a, data b) {
  data ret;
  ret.mx = max(a.mx, b.mx);
  ret.sum = (a.sum + b.sum);
  if (a.mx > b.mx)
    ret.cnt = a.cnt;
  else if (a.mx < b.mx)
    ret.cnt = b.cnt;
  else
    ret.cnt = (a.cnt + b.cnt);
  return ret;
}
data segtree[4 * 300100 + 1];
void update(int node, int i, int j, int ind, long long val) {
  if (i == j) {
    segtree[node].cnt += val;
    segtree[node].sum += i * val;
    if (segtree[node].cnt)
      segtree[node].mx = i;
    else
      segtree[node].mx = 0;
    return;
  }
  int mid = (i + j) >> 1;
  if (ind <= mid)
    update(2 * node, i, mid, ind, val);
  else
    update(2 * node + 1, mid + 1, j, ind, val);
  segtree[node] = merge(segtree[2 * node], segtree[2 * node + 1]);
}
void insert(int x) { update(1, 0, 300100, x, 1); }
void take_min(int x) {
  while (true) {
    if (segtree[1].mx <= x) break;
    int ind = segtree[1].mx;
    long long val = segtree[1].cnt;
    update(1, 0, 300100, ind, -val);
    update(1, 0, 300100, x, val);
  }
}
long long sum_query() { return segtree[1].sum; }
void reset() {
  while (true) {
    if (segtree[1].mx == 0) break;
    int ind = segtree[1].mx;
    long long val = segtree[1].cnt;
    update(1, 0, 300100, ind, -val);
  }
}
vector<int> sarr, lcp;
int a[300100 + 1];
int b[300100 + 1];
int pos[300100 + 1];
int arr[300100 + 1];
int min_tree[4 * 300100 + 1];
void build(int node, int i, int j) {
  if (i == j) {
    min_tree[node] = arr[i];
    return;
  }
  int mid = (i + j) >> 1;
  build(2 * node, i, mid);
  build(2 * node + 1, mid + 1, j);
  min_tree[node] = min(min_tree[2 * node], min_tree[2 * node + 1]);
}
int min_query(int node, int i, int j, int l, int r) {
  if (i > j || i > r || j < l || l > r) return 1000000100;
  if (i >= l && j <= r) return min_tree[node];
  int mid = (i + j) >> 1;
  return min(min_query(2 * node, i, mid, l, r),
             min_query(2 * node + 1, mid + 1, j, l, r));
}
int range_query(int l, int r) {
  r--;
  return min_query(1, 1, nn, l, r);
}
int cnt[300100 + 1];
int main() {
  clock_t begin = clock();
  ;
  int n, i, j, k, q, k1, k2, ptr;
  scanf("%d", &n);
  scanf("%d", &q);
  string s;
  cin >> s;
  sarr = buildSA(s);
  lcp = kasai(s, sarr);
  for (i = 1; i <= n; i++) {
    arr[i] = lcp[i - 1];
  }
  build(1, 1, n);
  for (i = 0; i < n; i++) {
    pos[sarr[i] + 1] = i + 1;
  }
  while (q--) {
    long long answer = 0;
    scanf("%d", &k1);
    scanf("%d", &k2);
    for (i = 1; i <= k1; i++) {
      scanf("%d", &a[i]);
      cnt[a[i]]++;
    }
    for (i = 1; i <= k2; i++) {
      scanf("%d", &b[i]);
      cnt[b[i]]++;
    }
    for (i = 1; i <= k1; i++) {
      if (cnt[a[i]] > 1) answer += (nn + 1 - a[i]);
    }
    for (i = 1; i <= k1; i++) {
      cnt[a[i]]--;
      a[i] = pos[a[i]];
    }
    for (i = 1; i <= k2; i++) {
      cnt[b[i]]--;
      b[i] = pos[b[i]];
    }
    sort(a + 1, a + k1 + 1);
    sort(b + 1, b + k2 + 1);
    reset();
    ptr = k2;
    for (i = k1; i >= 1; i--) {
      if (i < k1) {
        take_min(range_query(a[i], a[i + 1]));
      }
      while (ptr && b[ptr] > a[i]) {
        insert(range_query(a[i], b[ptr]));
        ptr--;
      }
      answer += sum_query();
    }
    reset();
    ptr = k1;
    for (i = k2; i >= 1; i--) {
      if (i < k2) {
        take_min(range_query(b[i], b[i + 1]));
      }
      while (ptr && a[ptr] > b[i]) {
        insert(range_query(b[i], a[ptr]));
        ptr--;
      }
      answer += sum_query();
    }
    printf("%lld\n", answer);
  }
  clock_t end = clock();
  double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
  fprintf(stderr, "\nTime elapsed : %.3f seconds\n", elapsed_secs);
  return 0;
  ;
}