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;
class suffix_sorter {
  int **rank;
  int *sorted;
  int size, steps;
  void init_fields(const int s) {
    size = s;
    steps = 31 - __builtin_clz(size) + 2;
    rank = new int *[steps];
    sorted = new int[size];
    for (int i = 0; i < steps; i++) {
      rank[i] = new int[size];
    }
  }
  template <class type>
  void init_rank(type *input, const bool compress = false) {
    if (!compress) {
      for (int i = 0; i < size; i++) {
        rank[0][i] = int(input[i]);
      }
      return;
    }
    set<int> uniq;
    map<int, int> compressed;
    for (int i = 0; i < size; i++) {
      uniq.insert(int(input[i]));
    }
    int id = 1;
    for (auto &e : uniq) {
      compressed[e] = id++;
    }
    for (int i = 0; i < size; i++) {
      rank[0][i] = compressed[int(input[i])];
    }
  }
  void sort() {
    pair<pair<int, int>, int> *tmp = new pair<pair<int, int>, int>[size];
    for (int step = 1; step < steps; step++) {
      int len = 1 << (step - 1);
      for (int i = 0; i < size; i++) {
        if (len + i < size)
          tmp[i] = {{rank[step - 1][i], rank[step - 1][i + len]}, i};
        else
          tmp[i] = {{rank[step - 1][i], 0}, i};
      }
      stable_sort(
          tmp, tmp + size,
          [](const pair<pair<int, int>, int> &a,
             const pair<pair<int, int>, int> &b) { return a.first < b.first; });
      for (int i = 0, r = 1; i < size; i++) {
        if (i > 0 && tmp[i].first != tmp[i - 1].first) r++;
        rank[step][tmp[i].second] = r;
      }
    }
    for (int i = 0; i < size; i++) {
      sorted[rank[steps - 1][i] - 1] = i;
    }
  }

 public:
  suffix_sorter(const string &input) {
    init_fields(input.size());
    init_rank(input.c_str(), true);
    sort();
  }
  template <class type>
  suffix_sorter(type *const input, const int n) {
    init_fields(n);
    init_rank(input);
    sort();
  }
  int *lcp() const {
    int *lcp = new int[size];
    for (int i = 0, k = 0; i < size; i++) {
      if (rank[steps - 1][i] == size) {
        k = 0;
        continue;
      }
      int j = sorted[rank[steps - 1][i]];
      while (i + k < size && j + k < size && rank[0][i + k] == rank[0][j + k]) {
        k++;
      }
      lcp[rank[steps - 1][i] - 1] = k;
      if (k > 0) k--;
    }
    return lcp;
  }
  inline int *get_last_rank() {
    int *ans = new int[size];
    memcpy(ans, rank[steps - 1], size * sizeof(int));
    return ans;
  }
  int lcp(int x, int y) {
    int ret = 0, n = size;
    for (int k = steps - 1; k >= 0 && x < n && y < n; k--) {
      if (rank[k][x] == rank[k][y]) {
        ret += (1 << k);
        x += (1 << k);
        y += (1 << k);
      }
    }
    return ret;
  }
};
class rolling_sum {
  map<int, int> cnt;
  long long sum;

 public:
  rolling_sum() : sum(0) { cnt[0] = 0; }
  inline long long getsum() { return sum; }
  void update(const int e) {
    int cur = 0;
    auto it = prev(cnt.end());
    while (it->first > e) {
      cur += it->second;
      sum -= 1ll * it->first * it->second;
      cnt.erase(it);
      it = prev(cnt.end());
    }
    if (e > 0 && cur > 0) {
      cnt[e] += cur;
      sum += 1ll * cur * e;
    }
  }
  void insert(const int e) {
    if (e == 0) return;
    sum += e;
    cnt[e]++;
  }
  void debug() {
    cerr << "sum: " << sum << endl;
    cerr << "map:";
    for (auto &e : cnt) {
      cerr << " (" << e.first << ", " << e.second << ")";
    }
    cerr << endl;
  }
};
class solver {
  int *rank;
  int size;
  suffix_sorter *sorter;
  long long calc(pair<int, int> *const c, int n) const {
    long long ans = 0;
    rolling_sum s;
    for (int i = 0; i < n; i++) {
      if (c[i].second == 1)
        ans += s.getsum();
      else
        s.insert(size - c[i].first);
      if (i < n - 1) s.update(sorter->lcp(c[i].first, c[i + 1].first));
    }
    return ans;
  }

 public:
  solver(const string &text) : size(text.size()) {
    sorter = new suffix_sorter(text);
    rank = sorter->get_last_rank();
  }
  long long query(const int m, int *const a, const int n, int *const b) const {
    rolling_sum sa, sb;
    pair<int, int> *c = new pair<int, int>[m + n];
    for (int i = 0; i < m; i++) {
      c[i] = {a[i] - 1, 0};
    }
    for (int i = 0; i < n; i++) {
      c[i + m] = {b[i] - 1, 1};
    }
    sort(c, c + m + n, [&](pair<int, int> i, pair<int, int> j) -> bool {
      if (rank[i.first] == rank[j.first]) return i.second < j.second;
      return rank[i.first] < rank[j.first];
    });
    long long ans = calc(c, m + n);
    reverse(c, c + m + n);
    ans += calc(c, m + n);
    return ans;
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  string text;
  cin >> text;
  solver s(text);
  for (int i = 0; i < q; i++) {
    int k, l;
    cin >> k >> l;
    int *a = new int[k];
    int *b = new int[l];
    for (int i = 0; i < k; i++) cin >> a[i];
    for (int i = 0; i < l; i++) cin >> b[i];
    cout << s.query(k, a, l, b) << "\n";
  }
  return 0;
}