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 mxN = 2e5, mxlgN = 17;
int n, q, sa[mxN], sa2[mxN], r[2 * mxN - 1], r2[mxN],
    rs = 26, cnt[mxN + 2], lcp[mxlgN + 1][mxN], a, b, ai, m, d[2 * mxN + 2],
    p[2 * mxN + 2];
long long c[2 * mxN + 2][2];
string s;
vector<array<int, 2>> v;
int lcpq(int l, int r) {
  int k = 31 - __builtin_clz(r - l + 1);
  return min(lcp[k][l], lcp[k][r - (1 << k) + 1]);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> q >> s;
  for (int i = 0; i < n; ++i) r[i] = s[i] - 'a' + 1;
  for (int l = 1; l < n; l *= 2) {
    for (int i = 0; i < n; ++i) ++cnt[r[i + l] + 1];
    for (int i = 0; i < rs; ++i) cnt[i + 1] += cnt[i];
    for (int i = 0; i < n; ++i) sa2[cnt[r[i + l]]++] = i;
    memset(cnt, 0, 4 * (rs + 2));
    for (int i = 0; i < n; ++i) ++cnt[r[i] + 1];
    for (int i = 0; i < rs; ++i) cnt[i + 1] += cnt[i];
    for (int i = 0; i < n; ++i) sa[cnt[r[sa2[i]]]++] = sa2[i];
    memset(cnt, 0, 4 * (rs + 2));
    rs = 0;
    for (int i = 0; i < n; ++i) {
      if (!i || r[sa[i]] != r[sa[i - 1]] || r[sa[i] + l] != r[sa[i - 1] + l])
        ++rs;
      r2[sa[i]] = rs;
    }
    memcpy(r, r2, 4 * n);
  }
  s += '$';
  for (int i = 0, k = 0; i<n; ++i, k -= k> 0) {
    if (r[i] >= n) continue;
    for (; s[i + k] == s[sa[r[i]] + k]; ++k)
      ;
    lcp[0][r[i]] = k;
  }
  for (int k = 1; k <= mxlgN; ++k)
    for (int i = 0; i <= n - (1 << k); ++i)
      lcp[k][i] = min(lcp[k - 1][i], lcp[k - 1][i + (1 << (k - 1))]);
  while (q--) {
    cin >> a >> b;
    for (int i = 0; i < a; ++i) cin >> ai, v.push_back({ai - 1, 0});
    for (int i = 0; i < b; ++i) cin >> ai, v.push_back({ai - 1, 1});
    sort(v.begin(), v.end(),
         [&](const array<int, 2> &a, const array<int, 2> &b) {
           return r[a[0]] < r[b[0]];
         });
    m = 2;
    long long ans = 0;
    int u = 1;
    for (int i = 0; i < a + b; ++i) {
      int td =
          i ? (v[i - 1][0] == v[i][0] ? n - v[i][0]
                                      : lcpq(r[v[i - 1][0]], r[v[i][0]] - 1))
            : n - v[i][0];
      while (u > 1 && d[p[u]] >= td) {
        ans += c[u][0] * c[u][1] * (d[u] - d[p[u]]);
        c[p[u]][0] += c[u][0];
        c[p[u]][1] += c[u][1];
        u = p[u];
      }
      if (d[u] > td) {
        ans += c[u][0] * c[u][1] * (d[u] - td);
        d[u] = td;
      }
      d[m] = n - v[i][0];
      ++c[m][v[i][1]];
      p[m] = u;
      u = m++;
    }
    while (u > 1) {
      ans += c[u][0] * c[u][1] * (d[u] - d[p[u]]);
      c[p[u]][0] += c[u][0];
      c[p[u]][1] += c[u][1];
      u = p[u];
    }
    v.clear();
    memset(c, 0, sizeof(c[0]) * m);
    cout << ans << "\n";
  }
}