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 <typename T>
void cetak(T t) {
  cout << t << ')' << endl;
}
template <typename T, typename... V>
void cetak(T t, V... v) {
  cout << t;
  if (sizeof...(v)) cerr << ", ";
  cetak(v...);
}
const int MOD = 1e9 + 7;
const int mx = 2e5 + 10;
class Element_suffix {
 public:
  int rank_now, rank_pref, pos;
};
class Suffix {
 private:
  inline bool same_rank(Element_suffix a, Element_suffix b) {
    return a.rank_now == b.rank_now && a.rank_pref == b.rank_pref;
  }
  inline void reset_freq(bool is_sort_now) {
    for (int i = 0; i <= end; i++) freq[i] = 0;
    for (int i = 0; i < n; i++)
      freq[is_sort_now ? suf[i].rank_now + 1 : suf[i].rank_pref + 1]++;
    start[0] = 0;
    for (int i = 1; i <= end; i++) {
      start[i] = freq[i - 1];
      freq[i] += freq[i - 1];
    }
  }

 public:
  int sorted[20][mx], freq[mx], start[mx], SA[mx], end, n;
  Element_suffix suf[mx], tmp[mx];
  string second;
  void build_suffix(string ss) {
    second = ss;
    n = (int)(second.size());
    if (n == 1) {
      SA[0] = 0;
      return;
    }
    end = max(n, 1 << 8);
    for (int i = 0; i < n; i++) sorted[0][i] = (int)second[i];
    int step = 1;
    for (int cnt = 1; cnt < n; step++, cnt *= 2) {
      for (int i = 0; i < n; i++) {
        suf[i].rank_pref = sorted[step - 1][i];
        suf[i].rank_now = (i + cnt < n) ? sorted[step - 1][i + cnt] : -1;
        suf[i].pos = i;
      }
      reset_freq(1);
      for (int i = 0; i < n; i++) tmp[start[suf[i].rank_now + 1]++] = suf[i];
      reset_freq(0);
      for (int i = 0; i < n; i++) suf[start[tmp[i].rank_pref + 1]++] = tmp[i];
      for (int i = 0; i < n; i++) {
        sorted[step][suf[i].pos] = (i && same_rank(suf[i], suf[i - 1]))
                                       ? sorted[step][suf[i - 1].pos]
                                       : i;
      }
    }
    step--;
    for (int i = 0; i < n; i++) SA[sorted[step][i]] = i;
  }
  int compute_lcp(int x, int y) {
    int ans = 0;
    for (int k = 20; k >= 0; k--) {
      int second = (1 << k);
      if (x + second - 1 < n && y + second - 1 < n &&
          sorted[k][x] == sorted[k][y]) {
        ans += second;
        x += second;
        y += second;
      }
    }
    return ans;
  }
} ini;
int n, q, di[mx];
string ss;
long long hitung(vector<int> a) {
  sort(a.begin(), a.end(), [&](int i, int j) { return di[i] < di[j]; });
  vector<int> lcp;
  for (int i = 1; i < (int)(a.size()); i++)
    lcp.push_back(ini.compute_lcp(a[i - 1], a[i]));
  vector<int> ve((int)(lcp.size()));
  iota(ve.begin(), ve.end(), 0);
  sort(ve.begin(), ve.end(), [&](int i, int j) { return lcp[i] < lcp[j]; });
  set<int> ini;
  ini.insert(-1);
  ini.insert((int)(ve.size()));
  long long ret = 0;
  for (int i : ve) {
    auto it = ini.upper_bound(i);
    int kanan = *it;
    it--;
    int kiri = *it;
    int tadi = 0;
    if (kanan < (int)(ve.size())) tadi = max(tadi, lcp[kanan]);
    if (kiri >= 0) tadi = max(tadi, lcp[kiri]);
    int banyak = kanan - kiri;
    ret += 1LL * banyak * (banyak - 1) / 2 * (lcp[i] - tadi);
    ini.insert(i);
  }
  return ret;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> q >> ss;
  ini.build_suffix(ss);
  for (int i = 0; i < n; i++) di[ini.SA[i]] = i;
  while (q--) {
    int A, B;
    cin >> A >> B;
    vector<int> a(A), b(B), c(A + B);
    for (int i = 0; i < A; i++) cin >> a[i], a[i] -= 1;
    for (int i = 0; i < B; i++) cin >> b[i], b[i] -= 1;
    for (int i = 0; i < A; i++) c[i] = a[i];
    for (int i = 0; i < B; i++) c[A + i] = b[i];
    cout << hitung(c) - hitung(a) - hitung(b) << '\n';
  }
}