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;
static mt19937 __gen(chrono::steady_clock::now().time_since_epoch().count());
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
constexpr int inf = 0x3f3f3f3f;
constexpr ll lnf = 0x3f3f3f3f3f3f3f3f;
static const int Maxn = 400005;
int n, q, sza, szb, sz;
int a[Maxn], b[Maxn], c[Maxn];
char str[Maxn];
int wa[Maxn], wb[Maxn], wc[Maxn], _s[Maxn];
int sa[Maxn], rnk[Maxn], height[Maxn];
template <typename T>
void build_SA(T *ss, int n, int m) {
  register int *x = wa, *y = wb, *tmp;
  register int i, j, w;
  for (i = 1; i <= n; ++i) _s[i] = ss[i];
  for (i = 1; i <= n; ++i) x[i] = _s[i], y[i] = i;
  for (i = 1; i <= m; ++i) wc[i] = 0;
  for (i = 1; i <= n; ++i) wc[x[i]]++;
  for (i = 2; i <= m; ++i) wc[i] += wc[i - 1];
  for (i = n; i >= 1; --i) sa[wc[x[y[i]]]--] = y[i];
  for (w = 1; w <= n; w <<= 1) {
    register int tot = 0;
    for (i = n - w + 1; i <= n; ++i) y[++tot] = i;
    for (i = 1; i <= n; ++i)
      if (sa[i] > w) y[++tot] = sa[i] - w;
    for (i = 1; i <= m; ++i) wc[i] = 0;
    for (i = 1; i <= n; ++i) wc[x[i]]++;
    for (i = 2; i <= m; ++i) wc[i] += wc[i - 1];
    for (i = n; i >= 1; --i) sa[wc[x[y[i]]]--] = y[i];
    tmp = x, x = y, y = tmp, x[sa[1]] = 1, tot = 1;
    for (i = 2; i <= n; ++i)
      x[sa[i]] = ((y[sa[i]] == y[sa[i - 1]] && y[sa[i] + w] == y[sa[i - 1] + w])
                      ? tot
                      : ++tot);
    if (tot == n) break;
    m = tot;
  }
  for (i = 1; i <= n; ++i) rnk[sa[i]] = i;
  for (i = 1, w = 0; i <= n; ++i) {
    if (rnk[i] == 1) continue;
    if (w) --w;
    int j = sa[rnk[i] - 1];
    while (i + w <= n && j + w <= n && _s[i + w] == _s[j + w]) w++;
    height[rnk[i]] = w;
  }
}
template <class T, class Compare = std::less<T>>
class RMQ {
 public:
  RMQ() = default;
  void build(const std::vector<T> &a) { build(a.data(), a.size()); }
  void build(const T *a, int n) {
    beg = a;
    std::vector<int> left(n, -1), right(n, -1);
    std::vector<int> stk(n);
    for (int i = 0, top = 0; i < n; ++i) {
      int last = -1;
      while (top && compare(a[i], a[stk[top - 1]])) {
        last = stk[--top];
      }
      if (top) right[stk[top - 1]] = i;
      left[i] = last;
      stk[top++] = i;
    }
    int root = stk[0];
    std::vector<int> parents(n, -1), order;
    indices.resize(n), inlabel.resize(n);
    for (int top = 1; top;) {
      int u = stk[--top];
      order.push_back(u);
      indices[u] = inlabel[u] = order.size();
      if (left[u] != -1) {
        stk[top++] = left[u];
        parents[left[u]] = u;
      }
      if (right[u] != -1) {
        stk[top++] = right[u];
        parents[right[u]] = u;
      }
    }
    ascendant.resize(n), head.resize(n);
    for (int i = n - 1; i > 0; --i) {
      int v = order[i], p = parents[v];
      if (lowbit(inlabel[p]) < lowbit(inlabel[v])) {
        inlabel[p] = inlabel[v];
      }
    }
    ascendant[root] = 0;
    for (int i = 1; i < n; ++i) {
      int v = order[i], p = parents[v];
      ascendant[v] = ascendant[p] | lowbit(inlabel[v]);
    }
    head[0] = root;
    for (int i = 1; i < n; ++i) {
      int v = order[i], p = parents[v];
      if (inlabel[v] != inlabel[p])
        head[indices[v] - 1] = p;
      else
        head[indices[v] - 1] = head[indices[p] - 1];
    }
  }
  const T query(int u, int v) const {
    if (u > v) swap(u, v);
    ++u;
    if (u == v) return height[u];
    uint Iv = inlabel[v], Iu = inlabel[u];
    uint hIv = lowbit(Iv), hIu = lowbit(Iu);
    uint mask = highbit((Iv ^ Iu) | hIv | hIu) - 1;
    uint j = lowbit(ascendant[v] & ascendant[u] & ~mask);
    int x, y;
    if (j == hIv)
      x = v;
    else {
      mask = highbit(ascendant[v] & (j - 1)) - 1;
      x = head[(indices[v] & ~mask | (mask + 1)) - 1];
    }
    if (j == hIu)
      y = u;
    else {
      mask = highbit(ascendant[u] & (j - 1)) - 1;
      y = head[(indices[u] & ~mask | (mask + 1)) - 1];
    }
    return *(beg + (indices[x] < indices[y] ? x : y));
  }

 private:
  static unsigned int lowbit(unsigned int x) { return x & ~x + 1; }
  static unsigned int highbit(unsigned int x) {
    return 1u << (31 - __builtin_clz(x));
  }
  Compare compare;
  const T *beg;
  std::vector<unsigned int> indices;
  std::vector<unsigned int> inlabel;
  std::vector<unsigned int> ascendant;
  std::vector<int> head;
};
RMQ<int> rmq;
struct Node {
  int val, cnt;
  long long sum;
} stk[Maxn];
int top;
ll get_min_sum(const vector<int> &arr) {
  top = 0;
  ll ans = 0;
  for (const auto &x : arr) {
    int cnt = 1;
    while (top && stk[top].val >= x) cnt += stk[top].cnt, --top;
    ans += 1LL * cnt * x + stk[top].sum;
    long long nowsum = 1LL * cnt * x + stk[top].sum;
    stk[++top] = (Node){x, cnt, nowsum};
  }
  return ans;
}
inline ll solve(int sz, int *arr) {
  vector<int> vec;
  for (int i = 1; i < sz; ++i) {
    if (arr[i] == arr[i + 1])
      vec.push_back(n - arr[i] + 1);
    else
      vec.push_back(rmq.query(rnk[arr[i]], rnk[arr[i + 1]]));
  }
  ll ans = get_min_sum(vec);
  return ans;
}
signed main() {
  scanf("%d%d", &n, &q);
  scanf("%s", str + 1);
  build_SA<char>(str, n, 128);
  rmq.build(height, n + 2);
  auto rankcmp = [&](int x, int y) -> bool { return rnk[x] < rnk[y]; };
  while (q--) {
    scanf("%d%d", &sza, &szb);
    for (int i = 1; i <= sza; ++i) scanf("%d", a + i);
    for (int i = 1; i <= szb; ++i) scanf("%d", b + i);
    sort(a + 1, a + sza + 1, rankcmp);
    sort(b + 1, b + szb + 1, rankcmp);
    sz = sza + szb;
    merge(a + 1, a + sza + 1, b + 1, b + szb + 1, c + 1, rankcmp);
    printf("%lld\n", solve(sz, c) - solve(sza, a) - solve(szb, b));
  }
  return 0;
}