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>
clock_t t = clock();
namespace my_std {
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
inline T rnd(T l, T r) {
  return uniform_int_distribution<T>(l, r)(rng);
}
template <typename T>
inline bool chkmax(T &x, T y) {
  return x < y ? x = y, 1 : 0;
}
template <typename T>
inline bool chkmin(T &x, T y) {
  return x > y ? x = y, 1 : 0;
}
template <typename T>
inline void read(T &t) {
  t = 0;
  char f = 0, ch = getchar();
  double d = 0.1;
  while (ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
  while (ch <= '9' && ch >= '0') t = t * 10 + ch - 48, ch = getchar();
  if (ch == '.') {
    ch = getchar();
    while (ch <= '9' && ch >= '0') t += d * (ch ^ 48), d *= 0.1, ch = getchar();
  }
  t = (f ? -t : t);
}
template <typename T, typename... Args>
inline void read(T &t, Args &...args) {
  read(t);
  read(args...);
}
char __sr[1 << 21], __z[20];
int __C = -1, __zz = 0;
inline void Ot() { fwrite(__sr, 1, __C + 1, stdout), __C = -1; }
template <typename T>
inline void print(T x) {
  if (__C > 1 << 20) Ot();
  if (x < 0) __sr[++__C] = '-', x = -x;
  while (__z[++__zz] = x % 10 + 48, x /= 10)
    ;
  while (__sr[++__C] = __z[__zz], --__zz)
    ;
  __sr[++__C] = '\n';
}
void file() {}
inline void chktime() {}
long long ksm(long long x, int y) {
  long long ret = 1;
  for (; y; y >>= 1, x = x * x)
    if (y & 1) ret = ret * x;
  return ret;
}
}  // namespace my_std
using namespace my_std;
int n, Q;
int a[220020];
char s[220020];
int h[220020];
int st[220020][30], lg2[220020];
void init() {
  lg2[1] = 0;
  for (int i = (2); i <= (n); i++) lg2[i] = lg2[i >> 1] + 1;
  for (int i = (1); i <= (n); i++) st[i][0] = h[i];
  for (int j = (1); j <= (20); j++)
    for (int i = (1); i <= (n - (1 << j) + 1); i++)
      st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
inline int query(register int l, register int r) {
  if (l > r) return 1e9;
  int len = lg2[r - l + 1];
  return min(st[l][len], st[r - (1 << len) + 1][len]);
}
namespace SA {
int cnt[220020], sa[220020], tp[220020], rnk[220020], _rnk[220020];
void Sort(int m) {
  for (int i = (1); i <= (m); i++) cnt[i] = 0;
  for (int i = (1); i <= (n); i++) ++cnt[rnk[i]];
  for (int i = (1); i <= (m); i++) cnt[i] += cnt[i - 1];
  for (int i = (n); i >= (1); i--) sa[cnt[rnk[tp[i]]]--] = tp[i];
}
void init() {
  for (int i = (1); i <= (n); i++) rnk[i] = a[i], tp[i] = i;
  Sort(27);
  for (int w = 1, p = 0, m = 27; p < n; w <<= 1, m = p) {
    p = 0;
    for (int i = (n - w + 1); i <= (n); i++) tp[++p] = i;
    for (int i = (1); i <= (n); i++)
      if (sa[i] > w) tp[++p] = sa[i] - w;
    Sort(m);
    memcpy(_rnk, rnk, sizeof(rnk));
    rnk[sa[p = 1]] = 1;
    for (int i = (2); i <= (n); i++)
      rnk[sa[i]] = (_rnk[sa[i]] == _rnk[sa[i - 1]] &&
                    _rnk[sa[i] + w] == _rnk[sa[i - 1] + w])
                       ? p
                       : ++p;
  }
  for (int i = 1, j, k = 0; i <= n; i++) {
    if (k) k--;
    j = sa[rnk[i] - 1];
    while (a[i + k] == a[j + k]) ++k;
    h[rnk[i]] = k;
  }
}
}  // namespace SA
int q1[220020], q2[220020];
struct hh {
  long long sum, S;
  int mn;
};
struct hhh {
  int id, type;
} q[220020 << 1];
inline bool cmp(const hhh &x, const hhh &y) {
  return x.id == y.id ? x.type > y.type : x.id < y.id;
}
long long solve(int *q1, int *q2, int n, int m) {
  stack<hh> s;
  for (int i = (1); i <= (n); i++) q[i] = (hhh){q1[i] + 1, 1};
  for (int i = (1); i <= (m); i++) q[i + n] = (hhh){q2[i], 0};
  sort(q + 1, q + n + m + 1, cmp);
  int lst = -1;
  long long ret = 0;
  for (int i = (1); i <= (n + m); i++) {
    if (lst != -1) {
      int x = query(lst + 1, q[i].id);
      long long SS = 0;
      while (!s.empty() && s.top().mn >= x) SS += s.top().S, s.pop();
      long long sum = SS * x;
      if (!s.empty()) sum += s.top().sum;
      s.push((hh){sum, SS, x});
    }
    if (q[i].type) {
      long long S = h[q[i].id], sum = S + (s.empty() ? 0 : s.top().sum);
      s.push((hh){sum, 1, h[q[i].id]});
    } else if (!s.empty())
      ret += s.top().sum;
    lst = q[i].id;
  }
  return ret;
}
int main() {
  file();
  read(n, Q);
  cin >> (s + 1);
  for (int i = (1); i <= (n); i++) a[i] = s[i] - 'a' + 1;
  SA::init();
  init();
  while (Q--) {
    int x, y, z;
    long long ans = 0;
    read(x, y);
    for (int i = (1); i <= (x); i++) read(z), q1[i] = SA::rnk[z];
    for (int i = (1); i <= (y); i++) read(z), q2[i] = SA::rnk[z];
    sort(q1 + 1, q1 + x + 1);
    sort(q2 + 1, q2 + y + 1);
    ans += solve(q1, q2, x, y);
    ans += solve(q2, q1, y, x);
    int t1 = 1, t2 = 1;
    while (t1 <= x && t2 <= y) {
      if (q1[t1] == q2[t2])
        ans += n - SA::sa[q1[t1]] + 1, ++t1, ++t2;
      else if (q1[t1] < q2[t2])
        ++t1;
      else
        ++t2;
    }
    print(ans);
  }
  Ot();
  return 0;
}