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 long long Mod = 1e9 + 7;
const long long INF = 1e9 + 1;
const long long N = 3e5 + 5, M = 26;
struct SuffixArray {
  int n;
  vector<int> SA, RSA, LCP;
  vector<vector<int>> ST;
  vector<int> MSB;
  SuffixArray() {}
  SuffixArray(string& s, int alpha = 256) {
    n = s.size();
    vector<int> v(s.begin(), s.end());
    SA = buildSA(v);
    LCP = buildLCP(v, SA);
    RSA.resize(n);
    MSB.resize(n + 1);
    int step = 2, bit = 0;
    for (int i = 0; i < n; i++) {
      RSA[SA[i]] = i;
      if (i + 1 == step) step *= 2, bit++;
      MSB[i + 1] = bit;
    }
    bit++;
    ST = vector<vector<int>>(n - 1, vector<int>(bit));
    for (int i = 0; i < n - 1; i++) ST[i][0] = LCP[i];
    for (int j = 1; j < bit; j++)
      for (int i = 0; i < n - 1; i++)
        if (i + (1 << j) < n)
          ST[i][j] = min(ST[i][j - 1], ST[i + (1 << j - 1)][j - 1]);
  }
  vector<int> buildSA(vector<int>& s, int alphabet_size = 256) {
    s.push_back(0);
    int n = s.size();
    int m = max(n, alphabet_size);
    vector<int> p(n), c(n), pn(n), cn(n), cnt(m);
    for (int i = 0; i < n; i++) cnt[s[i]]++;
    for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
    for (int i = 0; i < n; i++) p[--cnt[s[i]]] = i;
    c[p[0]] = 0;
    m = 1;
    for (int i = 1; i < n; i++)
      if (s[p[i]] != s[p[i - 1]])
        c[p[i]] = m++;
      else
        c[p[i]] = m - 1;
    for (int j = 0; 1 << j < n; j++) {
      fill(cnt.begin(), cnt.begin() + m, 0);
      for (int i = 0; i < n; i++)
        pn[i] = p[i] - (1 << j) + (1 << j > p[i] ? n : 0);
      for (int i = 0; i < n; i++) cnt[c[pn[i]]]++;
      for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
      for (int i = n; i--;) p[--cnt[c[pn[i]]]] = pn[i];
      cn[p[0]] = 0;
      m = 1;
      for (int i = 1; i < n; i++)
        if (c[p[i]] != c[p[i - 1]] ||
            c[(p[i] + (1 << j)) % n] != c[(p[i - 1] + (1 << j)) % n])
          cn[p[i]] = m++;
        else
          cn[p[i]] = m - 1;
      swap(c, cn);
    }
    p.erase(p.begin());
    s.pop_back();
    return p;
  }
  vector<int> buildLCP(vector<int>& str, vector<int>& suf) {
    int n = suf.size();
    vector<int> rnk(n), lcp(n);
    int k = 0;
    for (int i = 0; i < n; i++) rnk[suf[i]] = i;
    for (int i = 0; i < n; i++)
      if (rnk[i] == n - 1)
        k = 0;
      else {
        int j = suf[rnk[i] + 1];
        while (i + k < n && j + k < n && str[i + k] == str[j + k]) k++;
        lcp[rnk[i]] = k;
        if (k) k--;
      }
    return lcp;
  }
  int getLCP(int i, int j) {
    if (i == j) return n - i;
    i = RSA[i];
    j = RSA[j];
    if (i > j) swap(i, j);
    j--;
    int bit = MSB[j - i + 1];
    return min(ST[i][bit], ST[j - (1 << bit) + 1][bit]);
  }
} SA;
void print(stack<tuple<int, int, int>> s) {
  while (s.size()) {
    auto [i, j, k] = s.top();
    cout << i << ' ' << j << ' ' << k << endl;
    s.pop();
  }
  cout << "_ \n";
}
long long solve(vector<int>& G1, vector<int>& G2) {
  vector<pair<long long, long long>> a;
  for (int& i : G1) a.push_back({i, 0});
  for (int& i : G2) a.push_back({i, 1});
  sort(a.begin(), a.end(),
       [&](pair<long long, long long>& i, pair<long long, long long>& j) {
         return i.first != j.first ? SA.RSA[i.first] < SA.RSA[j.first]
                                   : i.second < j.second;
       });
  stack<tuple<int, int, int>> stk;
  long long sum = 0;
  long long ans = 0;
  for (auto [i, t] : a) {
    int new_f = i;
    int new_cnt = 0;
    while (stk.size()) {
      auto [l, r, cnt] = stk.top();
      int val = SA.getLCP(l, r);
      new_f = r;
      if (val < SA.getLCP(i, new_f)) break;
      stk.pop();
      new_cnt += cnt;
      new_f = l;
      sum -= (long long)cnt * val;
    }
    int new_val = SA.getLCP(i, new_f);
    if (new_val || new_cnt) {
      stk.push({new_f, i, new_cnt});
      sum += (long long)new_cnt * new_val;
    }
    if (t)
      ans += sum;
    else {
      stk.push({i, i, 1});
      sum += SA.getLCP(i, i);
    }
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  SA = s;
  while (q--) {
    int k1, k2;
    cin >> k1 >> k2;
    int k = k1 + k2;
    vector<int> a(k1), b(k2);
    set<int> s;
    for (int& i : a) {
      cin >> i;
      i--;
      s.insert(i);
    }
    long long ans = 0;
    for (int& i : b) {
      cin >> i;
      i--;
      ans += (s.count(i) ? n - i : 0);
    }
    long long ans1 = solve(a, b);
    long long ans2 = solve(b, a);
    cout << ans1 + ans2 - ans << '\n';
  }
  return 0;
}