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;
inline long long mod(long long n, long long m) {
  long long ret = n % m;
  if (ret < 0) ret += m;
  return ret;
}
long long gcd(long long a, long long b) {
  return (b == 0LL ? a : gcd(b, a % b));
}
long long exp(long long a, long long b, long long m) {
  if (b == 0LL) return 1LL;
  if (b == 1LL) return mod(a, m);
  long long k = mod(exp(a, b / 2, m), m);
  if (b & 1LL) {
    return mod(a * mod(k * k, m), m);
  } else
    return mod(k * k, m);
}
struct SuffixArray {
  vector<int> sa, lcp;
  SuffixArray() {}
  SuffixArray(string& s, int lim = 256) {
    int n = ((int)s.size()) + 1, k = 0, a, b;
    vector<int> x(s.begin(), s.end() + 1), y(n), ws(max(n, lim)), rank(n);
    sa = lcp = y, iota(sa.begin(), sa.end(), 0);
    for (int j = 0, p = 0; p < n; j = max(1, j * 2), lim = p) {
      p = j, iota(y.begin(), y.end(), n - j);
      for (int i = 0; i < (n); ++i)
        if (sa[i] >= j) y[p++] = sa[i] - j;
      fill(ws.begin(), ws.end(), 0);
      for (int i = 0; i < (n); ++i) ws[x[i]]++;
      for (int i = 1; i < (lim); ++i) ws[i] += ws[i - 1];
      for (int i = n; i--;) sa[--ws[x[y[i]]]] = y[i];
      swap(x, y), p = 1, x[sa[0]] = 0;
      for (int i = 1; i < (n); ++i)
        a = sa[i - 1], b = sa[i],
        x[b] = (y[a] == y[b] && y[a + j] == y[b + j]) ? p - 1 : p++;
    }
    for (int i = 1; i < (n); ++i) rank[sa[i]] = i;
    for (int i = 0, j; i < n - 1; lcp[rank[i++]] = k)
      for (k &&k--, j = sa[rank[i] - 1]; s[i + k] == s[j + k]; k++)
        ;
  }
};
const int N = 400100;
struct RMQ {
  vector<int> rmq[22], jump[22];
  void build(vector<int> v) {
    int n = v.size();
    for (int i = 0; i < (22); ++i) {
      rmq[i].resize(n + 100, 0);
      jump[i].resize(n + 100, 0);
    }
    for (int i = 0; i < n; i++) {
      rmq[0][i] = v[i];
      jump[0][i] = min(i + 1, n - 1);
    }
    for (int j = 1; j < 22; j++) {
      for (int i = 0; i < n; i++) jump[j][i] = jump[j - 1][jump[j - 1][i]];
    }
    for (int j = 1; j < 22; j++)
      for (int i = 0; i < n; i++) {
        rmq[j][i] = min(rmq[j - 1][i], rmq[j - 1][jump[j - 1][i]]);
      }
  }
  int query(int l, int r) {
    if (l > r) swap(l, r);
    l++;
    assert(l <= r);
    int sz = r - l + 1;
    int pot = 31 - __builtin_clz(sz);
    return min(rmq[pot][l], rmq[pot][r - (1 << pot) + 1]);
  }
};
int rev[N];
RMQ rmq;
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  SuffixArray sa(s);
  rmq.build(sa.lcp);
  for (int i = 0; i < (((int)sa.sa.size())); ++i) rev[sa.sa[i]] = i;
  while (q--) {
    vector<pair<int, int> > c;
    int k, l;
    cin >> k >> l;
    for (int i = 0; i < (k); ++i) {
      int a;
      cin >> a;
      a--;
      c.push_back(pair<int, int>(a, 0));
    }
    for (int i = 0; i < (l); ++i) {
      int b;
      cin >> b;
      b--;
      c.push_back(pair<int, int>(b, 1));
    }
    sort(c.begin(), c.end(), [&](pair<int, int> a, pair<int, int> b) {
      return rev[a.first] < rev[b.first];
    });
    long long res = 0;
    for (int iter = 0; iter < (2); ++iter) {
      map<int, int> mp;
      long long tot = 0;
      for (int i = 0; i < (((int)c.size())); ++i) {
        if (c[i].second) {
          res += tot;
        } else {
          tot += n - c[i].first;
          mp[n - c[i].first]++;
        }
        if (i + 1 != ((int)c.size()) and c[i].first != c[i + 1].first) {
          int lcp = rmq.query(rev[c[i].first], rev[c[i + 1].first]);
          if (lcp == 0) {
            mp.clear();
            tot = 0;
          }
          while (((int)mp.size()) > 0) {
            pair<int, int> cur = *mp.rbegin();
            if (cur.first <= lcp) break;
            tot -= cur.first * (long long)cur.second;
            mp.erase(cur.first);
            tot += lcp * (long long)cur.second;
            mp[lcp] += cur.second;
          }
        }
      }
      reverse(c.begin(), c.end());
    }
    cout << res << "\n";
  }
}