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>
struct RMQ {
  int n, levels;
  vector<vector<T>> range_min;
  RMQ(const vector<T> &values = {}) {
    if (!values.empty()) build(values);
  }
  void build(const vector<T> &values) {
    n = values.size();
    levels = 32 - __builtin_clz(n);
    range_min.resize(levels);
    for (int k = 0; k < levels; k++) range_min[k].resize(n - (1 << k) + 1);
    for (int i = 0; i < n; i++) range_min[0][i] = values[i];
    for (int k = 1; k < levels; k++)
      for (int i = 0; i <= n - (1 << k); i++)
        range_min[k][i] =
            min(range_min[k - 1][i], range_min[k - 1][i + (1 << k - 1)]);
  }
  T query(int a, int b) const {
    assert(a < b);
    int level = 31 - __builtin_clz(b - a);
    return min(range_min[level][a], range_min[level][b - (1 << level)]);
  }
};
struct suffix_array {
  int n;
  vector<int> suffix;
  vector<int> rank;
  vector<int> lcp;
  RMQ<int> rmq;
  suffix_array() {}
  template <typename T_string>
  suffix_array(const T_string &str, bool build_rmq = true) : n(0) {
    if (!str.empty()) build(str, build_rmq);
  }
  template <typename T_string>
  void build(const T_string &str, bool build_rmq = true) {
    n = str.size();
    suffix.resize(n);
    for (int i = 0; i < n; i++) suffix[i] = i;
    bool large_alphabet = false;
    for (int i = 0; i < n; i++)
      if (str[i] < 0 || str[i] >= 128) large_alphabet = true;
    if (large_alphabet) {
      sort(suffix.begin(), suffix.end(),
           [&](int a, int b) { return str[a] < str[b]; });
    } else {
      vector<int> freq(128, 0);
      for (int i = 0; i < n; i++) freq[str[i]]++;
      for (int c = 1; c < 128; c++) freq[c] += freq[c - 1];
      for (int i = 0; i < n; i++) suffix[--freq[str[i]]] = i;
    }
    rank.resize(n);
    rank[suffix[0]] = 0;
    for (int i = 1; i < n; i++)
      rank[suffix[i]] =
          str[suffix[i]] == str[suffix[i - 1]] ? rank[suffix[i - 1]] : i;
    vector<int> next_index(n);
    vector<int> values(n);
    bool done = false;
    for (int len = 1; len < n && !done; len *= 2) {
      for (int i = 0; i < n; i++) next_index[i] = i;
      for (int i = n - len; i < n; i++) values[next_index[rank[i]]++] = i;
      for (int i = 0; i < n; i++) {
        int prev = suffix[i] - len;
        if (prev >= 0) values[next_index[rank[prev]]++] = prev;
      }
      swap(suffix, values);
      values[suffix[0]] = 0;
      done = true;
      for (int i = 1; i < n; i++) {
        int s = suffix[i], prev = suffix[i - 1];
        if (s + len < n && prev + len < n && rank[s] == rank[prev] &&
            rank[s + len] == rank[prev + len]) {
          values[s] = values[prev];
          done = false;
        } else {
          values[s] = i;
        }
      }
      swap(rank, values);
    }
    compute_lcp(str);
    if (build_rmq) rmq.build(lcp);
  }
  template <typename T_string>
  void compute_lcp(const T_string &str) {
    lcp.assign(n, 0);
    int match = 0;
    for (int i = 0; i < n; i++) {
      if (rank[i] == 0) continue;
      int a = suffix[rank[i]] + match, b = suffix[rank[i] - 1] + match;
      while (a < n && b < n && str[a++] == str[b++]) match++;
      lcp[rank[i]] = match;
      match = max(match - 1, 0);
    }
  }
  int get_lcp(int a, int b) {
    if (a == b) return n - a;
    if (a >= n || b >= n) return 0;
    a = rank[a];
    b = rank[b];
    if (a > b) swap(a, b);
    return rmq.query(a + 1, b + 1);
  }
};
suffix_array SA;
long long solve_all_pairs(vector<int> &vec) {
  int n = vec.size();
  vector<int> ranks(n);
  for (int i = 0; i < n; i++) ranks[i] = SA.rank[vec[i]];
  sort(ranks.begin(), ranks.end());
  long long total = 0;
  vector<pair<int, int>> stack;
  long long stack_sum = 0;
  for (int i = 0; i < n; i++) {
    int lcp =
        i == 0 ? 0 : SA.get_lcp(SA.suffix[ranks[i - 1]], SA.suffix[ranks[i]]);
    int count = 1;
    while (!stack.empty() && lcp <= stack.back().first) {
      stack_sum -= (long long)stack.back().second * stack.back().first;
      count += stack.back().second;
      stack.pop_back();
    }
    stack.emplace_back(lcp, count);
    stack_sum += (long long)lcp * count;
    total += stack_sum;
  }
  return total;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N, Q;
  string str;
  cin >> N >> Q >> str;
  SA.build(str);
  for (int q = 0; q < Q; q++) {
    int K, L;
    cin >> K >> L;
    vector<int> A(K), B(L);
    for (int &a : A) {
      cin >> a;
      a--;
    }
    for (int &b : B) {
      cin >> b;
      b--;
    }
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    vector<int> combined(A.size() + B.size());
    merge(A.begin(), A.end(), B.begin(), B.end(), combined.begin());
    cout << solve_all_pairs(combined) - solve_all_pairs(A) - solve_all_pairs(B)
         << '\n';
  }
}