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>
int debugnum = 0;
using namespace std;
const int MAXN = 4e5 + 50;
class StrAlgorithm {
 public:
  static const int MAXT = 1e6 + 50;
  vector<int> str;
  int sa[MAXN];
  int rank[MAXN * 2];
  int height[MAXN];
  int T[MAXT];
  void Rsort(const int key[], int MAXVAL) {
    int *tmpsa = height, N = str.size();
    memset(T, 0, sizeof(int) * (5 + MAXVAL));
    for (int i = (int)(1); i < (int)(N + 1); i++) T[key[i]]++;
    for (int i = (int)(1); i < (int)(MAXVAL + 1); i++) T[i] += T[i - 1];
    for (int i = N; i >= 1; i--) tmpsa[T[key[sa[i]]]--] = sa[i];
    copy(tmpsa + 1, tmpsa + 1 + N, sa + 1);
  }
  bool cmp(int i, int slen) {
    return rank[sa[i]] == rank[sa[i - 1]] &&
           rank[sa[i] + slen] == rank[sa[i - 1] + slen];
  }
  void Cal() {
    const int N = str.size();
    memset(rank, 0, sizeof(int) * (5 + N));
    memset(sa, 0, sizeof(int) * (5 + N));
    for (int i = (int)(1); i < (int)(N + 1); i++) rank[i] = str[i - 1];
    for (int i = (int)(0); i < (int)(N + 1); i++) sa[i] = i;
    Rsort(rank, MAXT - 1);
    for (int slen = 1; slen <= N; slen <<= 1) {
      int MaxVal = *max_element(rank + 1, rank + 1 + N), p = 1, *tmpsa = height;
      memset(height, 0, sizeof(int) * (5 + N));
      for (int i = (int)(N + 1 - slen); i < (int)(N + 1); i++) tmpsa[p++] = i;
      for (int i = (int)(1); i < (int)(1 + N); i++)
        if (sa[i] > slen) tmpsa[p++] = sa[i] - slen;
      copy(tmpsa + 1, tmpsa + 1 + N, sa + 1);
      Rsort(rank, MaxVal);
      T[sa[1]] = 1;
      for (int i = (int)(2); i < (int)(N + 1); i++)
        T[sa[i]] = T[sa[i - 1]] + !cmp(i, slen);
      memset(rank, 0, sizeof(int) * (5 + N));
      copy(T + 1, T + 1 + N, rank + 1);
    }
    int j = 0, k = 0;
    memset(height, 0, sizeof(int) * (5 + N));
    for (int i = (int)(1); i < (int)(1 + N); i++) {
      k = max(0, k - 1), j = sa[rank[i] - 1];
      for (; j > 0 && max(i, j) - 1 + k < N && str[i - 1 + k] == str[j - 1 + k];
           k++)
        ;
      height[rank[i]] = k;
    }
  }
} SA;
struct RMQ {
  const static int RMQLen = MAXN, RMQPow = 20;
  int DP[RMQPow][RMQLen], len;
  void init(int *begin, int *end) {
    fill(DP[0], DP[0] + RMQLen, INT_MAX / 3);
    memset(DP, (0), sizeof(DP));
    copy(begin, end, DP[0] + 1);
    len = end - begin;
    for (int j = (int)(0); j < (int)(RMQPow - 1); j++)
      for (int i = (int)(1); i < (int)(1 + len); i++)
        DP[j + 1][i] = min(DP[j][i], DP[j][i + (1 << j)]);
  }
  int enquiry(int begin, int end) {
    int k = (int)(log((double)end - begin) / log(2.0));
    return min(DP[k][begin], DP[k][end - (1 << k)]);
  }
} rmq;
struct MSG {
  int order, tag;
  bool operator<(const MSG &other) const {
    return (order != other.order) ? (order < other.order) : (tag < other.tag);
  }
  MSG() { ; }
  MSG(int order, int tag) : order(order), tag(tag) { ; }
} msg[MAXN];
int msgcnt;
struct stkmsg {
  int height, weight;
  stkmsg() { ; }
  stkmsg(int height, int weight) : height(height), weight(weight) { ; }
};
struct STK : public stack<stkmsg> {
  long long ans;
  void pop() {
    stkmsg tmp = top();
    ans -= 1LL * tmp.height * tmp.weight;
    stack<stkmsg>::pop();
  }
  void push(int height, int weight) {
    stkmsg tmp(height, weight);
    while (top().height >= tmp.height) {
      tmp.weight += top().weight;
      pop();
    }
    ans += 1LL * tmp.height * tmp.weight;
    stack<stkmsg>::push(tmp);
  }
  STK() {
    stack<stkmsg>::push(stkmsg(INT_MIN, 0));
    ans = 0;
  }
};
long long solve(const vector<int> &a, const vector<int> &b, int tag) {
  msgcnt = 0;
  for (int i = (int)(0); i < (int)(a.size()); i++) msg[msgcnt++] = MSG(a[i], 0);
  for (int i = (int)(0); i < (int)(b.size()); i++) msg[msgcnt++] = MSG(b[i], 1);
  for (int i = (int)(0); i < (int)(msgcnt); i++) msg[i].tag ^= tag;
  sort(msg, msg + msgcnt);
  for (int i = (int)(0); i < (int)(msgcnt); i++) msg[i].tag ^= tag;
  STK stk;
  stk.push(SA.str.size() - SA.sa[msg[0].order] + 1, msg[0].tag ? 0 : 1);
  long long ans = 0;
  for (int i = (int)(1); i < (int)(msgcnt); i++) {
    int a = msg[i - 1].order, b = msg[i].order;
    int minH = INT_MAX;
    if (a != b) {
      minH = rmq.enquiry(a + 1, b + 1);
      stk.push(minH, 0);
    }
    if (!msg[i].tag)
      stk.push(SA.str.size() - SA.sa[msg[i].order] + 1, 1);
    else {
      ans += stk.ans;
    }
  }
  return ans;
}
vector<int> a, b;
int main() {
  int N, Q;
  string buf;
  while (cin >> N >> Q >> buf) {
    SA.str.resize(N);
    for (int i = (int)(0); i < (int)(N); i++) SA.str[i] = buf[i];
    SA.Cal();
    rmq.init(SA.height + 1, SA.height + 1 + N);
    while (Q--) {
      a.clear();
      b.clear();
      int n, m;
      cin >> n >> m;
      for (int i = (int)(0); i < (int)(n); i++) {
        int tmp;
        cin >> tmp;
        a.push_back(SA.rank[tmp]);
      }
      for (int i = (int)(0); i < (int)(m); i++) {
        int tmp;
        cin >> tmp;
        b.push_back(SA.rank[tmp]);
      }
      long long ans = solve(a, b, 0) + solve(b, a, 1);
      cout << ans << endl;
    }
  }
  return 0;
}