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 N = 200005;
unsigned char mask[] = {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01};
void getBuckets(unsigned char *second, int *bkt, int n, int K, int cs,
                bool end) {
  int i, sum = 0;
  for (i = 0; i <= K; i++) bkt[i] = 0;
  for (i = 0; i < n; i++)
    bkt[(cs == sizeof(int) ? ((int *)second)[i]
                           : ((unsigned char *)second)[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 *second, int *bkt,
               int n, int K, int cs, bool end) {
  int i, j;
  getBuckets(second, bkt, n, K, cs, end);
  for (i = 0; i < n; i++) {
    j = SA[i] - 1;
    if (j >= 0 && !((t[(j) / 8] & mask[(j) % 8]) ? 1 : 0))
      SA[bkt[(cs == sizeof(int) ? ((int *)second)[j]
                                : ((unsigned char *)second)[j])]++] = j;
  }
}
void induceSAs(unsigned char *t, int *SA, unsigned char *second, int *bkt,
               int n, int K, int cs, bool end) {
  int i, j;
  getBuckets(second, bkt, n, K, cs, end);
  for (i = n - 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 *)second)[j]
                                  : ((unsigned char *)second)[j])]] = j;
  }
}
void SA_IS(unsigned char *second, int *SA, int n, int K, int cs) {
  int i, j;
  unsigned char *t = (unsigned char *)malloc(n / 8 + 1);
  t[(n - 2) / 8] = (0) ? (mask[(n - 2) % 8] | t[(n - 2) / 8])
                       : ((~mask[(n - 2) % 8]) & t[(n - 2) / 8]);
  t[(n - 1) / 8] = (1) ? (mask[(n - 1) % 8] | t[(n - 1) / 8])
                       : ((~mask[(n - 1) % 8]) & t[(n - 1) / 8]);
  for (i = n - 3; i >= 0; i--)
    t[(i) / 8] =
        (((cs == sizeof(int) ? ((int *)second)[i]
                             : ((unsigned char *)second)[i]) <
              (cs == sizeof(int) ? ((int *)second)[i + 1]
                                 : ((unsigned char *)second)[i + 1]) ||
          ((cs == sizeof(int) ? ((int *)second)[i]
                              : ((unsigned char *)second)[i]) ==
               (cs == sizeof(int) ? ((int *)second)[i + 1]
                                  : ((unsigned char *)second)[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(second, bkt, n, K, cs, true);
  for (i = 0; i < n; i++) SA[i] = -1;
  for (i = 1; i < n; 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 *)second)[i]
                                  : ((unsigned char *)second)[i])]] = i;
  induceSAl(t, SA, second, bkt, n, K, cs, false);
  induceSAs(t, SA, second, bkt, n, K, cs, true);
  free(bkt);
  int n1 = 0;
  for (i = 0; i < n; 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[n1++] = SA[i];
  for (i = n1; i < n; i++) SA[i] = -1;
  int name = 0, prev = -1;
  for (i = 0; i < n1; i++) {
    int pos = SA[i];
    bool diff = false;
    for (int d = 0; d < n; d++)
      if (prev == -1 ||
          (cs == sizeof(int) ? ((int *)second)[pos + d]
                             : ((unsigned char *)second)[pos + d]) !=
              (cs == sizeof(int) ? ((int *)second)[prev + d]
                                 : ((unsigned char *)second)[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) {
      name++;
      prev = pos;
    }
    pos = (pos % 2 == 0) ? pos / 2 : (pos - 1) / 2;
    SA[n1 + pos] = name - 1;
  }
  for (i = n - 1, j = n - 1; i >= n1; i--)
    if (SA[i] >= 0) SA[j--] = SA[i];
  int *SA1 = SA, *s1 = SA + n - n1;
  if (name < n1)
    SA_IS((unsigned char *)s1, SA1, n1, name - 1, sizeof(int));
  else
    for (i = 0; i < n1; i++) SA1[s1[i]] = i;
  bkt = (int *)malloc(sizeof(int) * (K + 1));
  getBuckets(second, bkt, n, K, cs, true);
  for (i = 1, j = 0; i < n; 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 < n1; i++) SA1[i] = s1[SA1[i]];
  for (i = n1; i < n; i++) SA[i] = -1;
  for (i = n1 - 1; i >= 0; i--) {
    j = SA[i];
    SA[i] = -1;
    SA[--bkt[(cs == sizeof(int) ? ((int *)second)[j]
                                : ((unsigned char *)second)[j])]] = j;
  }
  induceSAl(t, SA, second, bkt, n, K, cs, false);
  induceSAs(t, SA, second, bkt, n, K, cs, true);
  free(bkt);
  free(t);
}
int sa[N];
int lcp[N];
int Rank[N];
unsigned char *second;
int n, q;
char str[N];
void calc_lcp() {
  for (int i = 0; i - 1 < 0 || second[i - 1]; i++) Rank[sa[i]] = i;
  int c = 0;
  for (int i = 0; i - 1 < 0 || second[i - 1]; i++) {
    if (Rank[i]) {
      int j = sa[Rank[i] - 1];
      while (second[i + c] == second[j + c]) c++;
    }
    lcp[Rank[i]] = c;
    if (c) c--;
  }
}
void print(string str) {
  for (int i = 0; i <= n; i++) {
    cout << str.substr(sa[i]);
    cout << " " << lcp[i];
    cout << endl;
  }
}
int table[N][20], lg[N];
void buildTable() {
  for (int i = 0; (1 << i) <= n; ++i) lg[1 << i] = i;
  for (int(i) = (1); (i) <= (int)(n); (i)++)
    if (!lg[i]) lg[i] = lg[i - 1];
  for (int(i) = (0); (i) <= (int)(n); (i)++) table[i][0] = lcp[i];
  for (int j = 1; (1 << j) <= n; ++j)
    for (int(i) = (0); (i) <= (int)(n); (i)++) {
      table[i][j] = 1000000107;
      if (i + (1 << j) - 1 <= n)
        table[i][j] = min(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]);
    }
}
int query(int l, int r) {
  if (r < l) swap(r, l);
  int shift = lg[r - l + 1];
  return min(table[l][shift], table[r - (1 << shift) + 1][shift]);
}
long long solve(vector<int> &a) {
  long long ret = 0;
  sort(a.begin(), a.end(), [](int x, int y) { return Rank[x] < Rank[y]; });
  vector<int> cur;
  for (int(i) = (1); (i) <= (int)((int)(a).size() - 1); (i)++) {
    if (a[i] == a[i - 1])
      cur.push_back(n - a[i]);
    else
      cur.push_back(query(Rank[a[i - 1]] + 1, Rank[a[i]]));
  }
  vector<int> l((int)(cur).size(), -1), r((int)(cur).size(), (int)(cur).size());
  vector<int> stk;
  for (int(i) = (0); (i) <= (int)((int)(cur).size() - 1); (i)++) {
    while (!stk.empty() && cur[stk.back()] >= cur[i]) {
      r[stk.back()] = i;
      stk.pop_back();
    }
    if (!stk.empty()) l[i] = stk.back();
    stk.push_back(i);
  }
  for (int(i) = (0); (i) <= (int)((int)(cur).size() - 1); (i)++) {
    ret += 1ll * cur[i] * (r[i] - i) * (i - l[i]);
  }
  return ret;
}
int main() {
  scanf("%d%d%s", &n, &q, str);
  n = (int)strlen(str);
  second = (unsigned char *)str;
  SA_IS(second, sa, n + 1, 256, 1);
  calc_lcp();
  buildTable();
  while (q--) {
    int k, l;
    vector<int> a, b, c;
    scanf("%d%d", &k, &l);
    while (k--) {
      int x;
      scanf("%d", &x), --x;
      a.push_back(x), c.push_back(x);
    }
    while (l--) {
      int x;
      scanf("%d", &x), --x;
      b.push_back(x), c.push_back(x);
    }
    printf("%lld\n", solve(c) - solve(a) - solve(b));
  }
}