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;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int power(int x, int p, int MOD) {
  if (p == 0) return 1 % MOD;
  if (p == 1) return x % MOD;
  int res = power(x, p / 2, MOD);
  res = (long long)res * res % MOD;
  if (p & 1) res = (long long)res * x % MOD;
  return res;
}
struct SA {
  string s;
  int n, block;
  vector<int> sa, rnk, tmp, aux, lcp;
  vector<vector<int> > T;
  void init() {
    int n = max(this->n, 256);
    sa = vector<int>(n + 3), rnk = vector<int>(n + 3), tmp = vector<int>(n + 3),
    aux = vector<int>(n + 3), lcp = vector<int>(n + 3);
  }
  SA(string second) : s(second), n(second.size()) { init(); }
  bool suffixCmp(int i, int j) {
    if (rnk[i] != rnk[j]) return rnk[i] < rnk[j];
    i += block, j += block;
    if (i >= n) i -= n;
    if (j >= n) j -= n;
    return rnk[i] < rnk[j];
  }
  void suffixSort(int h) {
    for (int i = 0; i < n; i++) {
      aux[i] = sa[i] - block;
      if (aux[i] < 0) aux[i] += n;
    }
    for (int i = 0; i < h; i++) tmp[i] = 0;
    for (int i = 0; i < n; i++) tmp[rnk[aux[i]]]++;
    for (int i = 0; i < h - 1; i++) tmp[i + 1] += tmp[i];
    for (int i = n - 1; i >= 0; i--) sa[--tmp[rnk[aux[i]]]] = aux[i];
    tmp[0] = 0;
    for (int i = 0; i < n - 1; i++)
      tmp[i + 1] = tmp[i] + suffixCmp(sa[i], sa[i + 1]);
    for (int i = 0; i < n; i++) rnk[sa[i]] = tmp[i];
  }
  void build() {
    n++;
    for (int i = 0; i < n; i++) sa[i] = i, rnk[i] = s[i], tmp[i] = 0;
    block = 0;
    suffixSort(256);
    for (block = 1; tmp[n - 1] != n - 1; block *= 2) suffixSort(tmp[n - 1] + 1);
    n--;
    sa.erase(sa.begin());
  }
  void buildLCP() {
    for (int i = 0; i < n; i++) rnk[sa[i]] = i, lcp[i] = 0;
    int last = 0;
    for (int i = 0; i < n; i++, last = max(lcp[rnk[i - 1]] - 1, 0)) {
      if (rnk[i] == n - 1) continue;
      int j = sa[rnk[i] + 1];
      while (i + last < n && j + last < n && s[i + last] == s[j + last]) last++;
      lcp[rnk[i]] = last;
    }
    T = vector<vector<int> >(n, vector<int>(20));
    for (int i = 0; i < n; i++) T[i][0] = lcp[i];
    for (int j = 1; j < 20; j++) {
      for (int i = 0; i + (1 << j) <= n; i++) {
        T[i][j] = min(T[i][j - 1], T[i + (1 << (j - 1))][j - 1]);
      }
    }
  }
  int rangeLCP(int i, int j) {
    if (i > j) swap(i, j);
    if (i == j) return n - sa[i];
    j--;
    int k = __builtin_clz(1) - __builtin_clz(j - i + 1);
    return min(T[i][k], T[j - (1 << k) + 1][k]);
  }
  pair<int, int> getRange(int i, int sz) {
    pair<int, int> res;
    {
      int l = 0, r = i + 1;
      while (l < r) {
        int mid = (l + r) / 2;
        if (rangeLCP(mid, i) >= sz)
          r = mid;
        else
          l = mid + 1;
      }
      res.first = l;
    }
    {
      int l = i, r = n - 1;
      while (l < r) {
        int mid = (l + r + 1) / 2;
        if (rangeLCP(mid, i) >= sz)
          l = mid;
        else
          r = mid - 1;
      }
      res.second = l;
    }
    return res;
  }
};
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, Q;
  cin >> n >> Q;
  string s;
  cin >> s;
  SA sa(s);
  sa.build();
  sa.buildLCP();
  while (Q--) {
    int k, l;
    cin >> k >> l;
    vector<int> a(k), b(l);
    for (int i = 0; i < k; i++) {
      cin >> a[i];
      --a[i];
      a[i] = sa.rnk[a[i]];
    }
    for (int i = 0; i < l; i++) {
      cin >> b[i];
      --b[i];
      b[i] = sa.rnk[b[i]];
    }
    sort((a).begin(), (a).end());
    sort((b).begin(), (b).end());
    long long ans = 0;
    long long acc = 0;
    priority_queue<pair<int, int> > pq;
    auto append = [&](int lcp) {
      int popped = 0;
      while (!pq.empty() && pq.top().first > lcp) {
        acc -= pq.top().first * pq.top().second;
        popped += pq.top().second;
        pq.pop();
      }
      acc += lcp * popped;
      pq.push({lcp, popped});
    };
    int ptr = 0;
    int mx = -1;
    for (int i = 0; i < l; i++) {
      while (ptr < k && a[ptr] < b[i]) {
        if (mx != -1 && a[ptr] > mx) {
          int lcp = sa.rangeLCP(a[ptr], mx);
          append(lcp);
        }
        mx = max(mx, a[ptr]);
        int sz = n - sa.sa[a[ptr]];
        pq.push({sz, 1});
        acc += sz;
        ptr++;
      }
      if (mx != -1 && b[i] > mx) {
        append(sa.rangeLCP(b[i], mx));
      }
      mx = max(mx, b[i]);
      ans += acc;
      if (ptr < k && a[ptr] == b[i]) {
        ans += n - sa.sa[a[ptr]];
      }
    }
    reverse((a).begin(), (a).end());
    reverse((b).begin(), (b).end());
    ptr = 0;
    int mn = n;
    pq = priority_queue<pair<int, int> >();
    acc = 0;
    for (int i = 0; i < l; i++) {
      while (ptr < k && a[ptr] > b[i]) {
        if (mx != n && a[ptr] < mn) {
          int lcp = sa.rangeLCP(a[ptr], mn);
          append(lcp);
        }
        mn = min(mn, a[ptr]);
        int sz = n - sa.sa[a[ptr]];
        pq.push({sz, 1});
        acc += sz;
        ptr++;
      }
      if (mn != n && b[i] < mn) {
        append(sa.rangeLCP(b[i], mn));
      }
      mn = min(mn, b[i]);
      ans += acc;
    }
    cout << ans << endl;
  }
}