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>
void _R(T &x) {
  cin >> x;
}
void _R(int &x) { scanf("%d", &x); }
void _R(long long &x) { scanf("%lld", &x); }
void _R(unsigned long long &x) { scanf("%llu", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template <class T, class... U>
void R(T &head, U &...tail) {
  _R(head);
  R(tail...);
}
template <class T>
void _W(const T &x) {
  cout << x;
}
void _W(const int &x) { printf("%d", x); }
void _W(const long long &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template <class T, class U>
void _W(const pair<T, U> &x) {
  _W(x.F);
  putchar(' ');
  _W(x.S);
}
template <class T>
void _W(const vector<T> &x) {
  for (auto i = x.begin(); i != x.end(); _W(*i++))
    if (i != x.cbegin()) putchar(' ');
}
void W() {}
template <class T, class... U>
void W(const T &head, const U &...tail) {
  _W(head);
  putchar(sizeof...(tail) ? ' ' : '\n');
  W(tail...);
}
const int MAXN = 1e6 + 10, MAXM = 4e6 + 10;
const int INF = INT_MAX, SINF = 0x3f3f3f3f;
const long long llINF = LLONG_MAX;
const int MOD = 1e9 + 7, mod = 998244353;
const int inv2 = 5e8 + 4;
const int Lim = 1 << 20;
namespace SA {
int sa[MAXN], h[MAXN], rk[MAXN], c[MAXN], l[MAXN], p[MAXN], s[MAXN << 1],
    t[MAXN << 1], st[MAXN][20], lg[MAXN], n;
void sais(int n, int m, int *s, int *t, int *p) {
  int n1 = t[n - 1] = 0, ch = rk[0] = -1, *s1 = s + n;
  for (int i = (n - 2), LIM = (0); i >= LIM; i--)
    t[i] = s[i] ^ s[i + 1] ? s[i] > s[i + 1] : t[i + 1];
  for (int i = (1), LIM = (n - 1); i <= LIM; i++)
    rk[i] = t[i - 1] && !t[i] ? p[n1] = i, n1++ : -1;
  fill(sa, sa + n, -1), fill(c, c + m, 0);
  for (int i = (0), LIM = (n - 1); i <= LIM; i++) c[s[i]]++;
  for (int i = (1), LIM = (m - 1); i <= LIM; i++) c[i] += c[i - 1];
  for (int i = (0), LIM = (m - 1); i <= LIM; i++) l[i] = c[i] - 1;
  for (int i = (n1 - 1), LIM = (0); i >= LIM; i--) sa[l[s[p[i]]]--] = p[i];
  for (int i = (0), LIM = (m - 1); i <= LIM; i++) l[i] = c[i - 1];
  for (int i = (0), LIM = (n - 1); i <= LIM; i++)
    if (sa[i] > 0 && t[sa[i] - 1]) sa[l[s[sa[i] - 1]]++] = sa[i] - 1;
  for (int i = (0), LIM = (m - 1); i <= LIM; i++) l[i] = c[i] - 1;
  for (int i = (n - 1), LIM = (0); i >= LIM; i--)
    if (sa[i] > 0 && !t[sa[i] - 1]) sa[l[s[sa[i] - 1]]--] = sa[i] - 1;
  ;
  for (int i = 0, x, y; i < n; i++)
    if (~(x = rk[sa[i]])) {
      if (ch < 1 || (p[x + 1] - p[x]) ^ (p[y + 1] - p[y]))
        ch++;
      else
        for (int j = p[x], k = p[y]; j <= p[x + 1]; j++, k++)
          if ((s[j] << 1 | t[j]) ^ (s[k] << 1 | t[k])) {
            ch++;
            break;
          }
      s1[y = x] = ch;
    }
  if (ch + 1 < n1)
    sais(n1, ch + 1, s1, t + n, p + n1);
  else
    for (int i = (0), LIM = (n1 - 1); i <= LIM; i++) sa[s1[i]] = i;
  for (int i = (0), LIM = (n1 - 1); i <= LIM; i++) s1[i] = p[sa[i]];
  fill(sa, sa + n, -1), fill(c, c + m, 0);
  for (int i = (0), LIM = (n - 1); i <= LIM; i++) c[s[i]]++;
  for (int i = (1), LIM = (m - 1); i <= LIM; i++) c[i] += c[i - 1];
  for (int i = (0), LIM = (m - 1); i <= LIM; i++) l[i] = c[i] - 1;
  for (int i = (n1 - 1), LIM = (0); i >= LIM; i--) sa[l[s[s1[i]]]--] = s1[i];
  for (int i = (0), LIM = (m - 1); i <= LIM; i++) l[i] = c[i - 1];
  for (int i = (0), LIM = (n - 1); i <= LIM; i++)
    if (sa[i] > 0 && t[sa[i] - 1]) sa[l[s[sa[i] - 1]]++] = sa[i] - 1;
  for (int i = (0), LIM = (m - 1); i <= LIM; i++) l[i] = c[i] - 1;
  for (int i = (n - 1), LIM = (0); i >= LIM; i--)
    if (sa[i] > 0 && !t[sa[i] - 1]) sa[l[s[sa[i] - 1]]--] = sa[i] - 1;
  ;
}
template <class T>
void SA(int n, const T &S) {
  for (int i = (0), LIM = (n - 1); i <= LIM; i++) s[i] = S[i];
  s[n++] = 0;
  sais(n, 200, s, t, p);
  for (int i = (0), LIM = (n - 1); i <= LIM; i++) rk[sa[i]] = i;
  for (int i = 0, k = 0; i < n - 1; h[rk[i++]] = k)
    for (k &&k--; i + k < n && s[i + k] == s[sa[rk[i] - 1] + k]; k++)
      ;
}
void getlcp(int sz) {
  n = sz;
  for (int i = 1; i <= n; i++) lg[i] = lg[i - 1] + (1 << lg[i - 1] + 1 == i);
  for (int i = 1; i <= n; i++) st[i][0] = h[i];
  for (int j = 1; 1 << j <= n; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
int lcp(int i, int j) {
  if (i == j) return n - i + 1;
  i = rk[i];
  j = rk[j];
  if (i > j) swap(i, j);
  i++;
  int k = lg[j - i + 1];
  return min(st[i][k], st[j - (1 << k) + 1][k]);
}
}  // namespace SA
using namespace SA;
char ss[MAXN];
int top, id[MAXN], pre[MAXN];
long long sum[MAXN];
void solve() {
  int n, q;
  R(n, q);
  scanf("%s", ss);
  SA::SA(n, ss);
  getlcp(n);
  for (int i = n; i; i--) rk[i] = rk[i - 1];
  rk[0] = 0;
  while (q--) {
    long long k, l, ans = 0;
    R(k, l);
    vector<int> v1(k), v2(l);
    for (int i = 0; i < k; i++) R(v1[i]);
    for (int i = 0; i < l; i++) R(v2[i]);
    vector<pair<int, int> > c(1);
    for (auto j : v1) c.push_back({j, 0});
    for (auto j : v2) c.push_back({j, 1});
    sort((c).begin(), (c).end(), [&](pair<int, int> a, pair<int, int> b) {
      return rk[a.first] < rk[b.first];
    });
    for (int i = 1; i <= k + l; i++) sum[i] = sum[i - 1] + c[i].second;
    for (int i = 1; i <= k + l; i++) {
      int t = i;
      while (top && lcp(c[i].first, c[i - 1].first) <
                        lcp(c[id[top]].first, c[id[top] - 1].first)) {
        t = min(t, pre[top]);
        ans += 1ll * lcp(c[id[top]].first, c[id[top] - 1].first) *
               (((id[top] - pre[top] + 1) -
                 (sum[id[top] - 1] - sum[pre[top] - 2])) *
                    (sum[i - 1] - sum[id[top] - 1]) +
                (sum[id[top] - 1] - sum[pre[top] - 2]) *
                    (i - id[top] - (sum[i - 1] - sum[id[top] - 1])));
        top--;
      }
      top++;
      id[top] = i;
      pre[top] = t;
    }
    while (top) {
      ans +=
          1ll * lcp(c[id[top]].first, c[id[top] - 1].first) *
          (((id[top] - pre[top] + 1) - (sum[id[top] - 1] - sum[pre[top] - 2])) *
               (sum[k + l] - sum[id[top] - 1]) +
           (sum[id[top] - 1] - sum[pre[top] - 2]) *
               (k + l - id[top] + 1 - (sum[k + l] - sum[id[top] - 1])));
      top--;
    }
    W(ans);
  }
}
int main() {
  int t = 1;
  while (t--) solve();
  return 0;
}