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>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("-ffloat-store")
using namespace std;
clock_t time_p = clock();
void aryanc403() {}
const long long int INF = 0xFFFFFFFFFFFFFFFL;
long long int seed;
mt19937 rng(seed = chrono::steady_clock::now().time_since_epoch().count());
inline long long int rnd(long long int l = 0, long long int r = INF) {
  return uniform_int_distribution<long long int>(l, r)(rng);
}
class CMP {
 public:
  bool operator()(pair<long long int, long long int> a,
                  pair<long long int, long long int> b) {
    return !(a.first < b.first || (a.first == b.first && a.second <= b.second));
  }
};
void add(map<long long int, long long int> &m, long long int x,
         long long int cnt = 1) {
  auto jt = m.find(x);
  if (jt == m.end())
    m.insert({x, cnt});
  else
    jt->second += cnt;
}
void del(map<long long int, long long int> &m, long long int x,
         long long int cnt = 1) {
  auto jt = m.find(x);
  if (jt->second <= cnt)
    m.erase(jt);
  else
    jt->second -= cnt;
}
bool cmp(const pair<long long int, long long int> &a,
         const pair<long long int, long long int> &b) {
  return a.first < b.first || (a.first == b.first && a.second < b.second);
}
const long long int mod = 1000000007L;
template <class T>
struct RMQ {
  vector<vector<T>> jmp;
  RMQ(const vector<T> &V) : jmp(1, V) {
    for (int pw = 1, k = 1; pw * 2 <= ((long long int)(V).size());
         pw *= 2, ++k) {
      jmp.emplace_back(((long long int)(V).size()) - pw * 2 + 1);
      for (int j = 0; j < (((long long int)(jmp[k]).size())); ++j)
        jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
    }
  }
  T query(int a, int b) {
    assert(a < b);
    int dep = 31 - __builtin_clz(b - a);
    return min(jmp[dep][a], jmp[dep][b - (1 << dep)]);
  }
};
struct SuffixArray {
  vector<long long int> sa, lcp;
  SuffixArray(string &s, int lim = 256) {
    int n = ((long long int)(s).size()) + 1, k = 0, a, b;
    vector<long long int> x(begin(s), end(s) + 1), y(n), ws(max(n, lim)),
        rank(n);
    sa = lcp = y, iota(begin(sa), end(sa), 0);
    for (int j = 0, p = 0; p < n; j = max(1, j * 2), lim = p) {
      p = j, iota(begin(y), end(y), n - j);
      for (int i = 0; i < (n); ++i)
        if (sa[i] >= j) y[p++] = sa[i] - j;
      fill(begin(ws), end(ws), 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++)
        ;
  }
};
struct UF {
  vector<long long int> e;
  vector<pair<long long int, long long int>> aa;
  UF(int n, const vector<long long int> &_a) : e(n, -1) {
    aa.clear();
    for (auto x : _a) {
      if (x & 1)
        aa.push_back({0, 1});
      else
        aa.push_back({1, 0});
    }
  }
  bool same_set(int a, int b) { return find(a) == find(b); }
  int size(int x) { return -e[find(x)]; }
  int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
  long long int join(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return 0;
    if (e[a] > e[b]) swap(a, b);
    e[a] += e[b];
    e[b] = a;
    long long int cnt = aa[a].first * aa[b].second + aa[a].second * aa[b].first;
    aa[a].first += aa[b].first;
    aa[a].second += aa[b].second;
    ;
    return cnt;
  }
};
long long int T, n, i, j, k, in, cnt, l, r, u, v, x, y;
long long int m;
string s;
vector<long long int> id;
int main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  {
    long long int q;
    cin >> n >> q;
    cin >> s;
    SuffixArray ss(s);
    RMQ<long long int> rmq(ss.lcp);
    id.clear();
    id.resize(n + 2);
    ;
    ;
    for (i = (0); i <= (n); ++i) id[ss.sa[i] + 1] = i;
    auto query = [&](long long int l, long long int r) {
      if (l == r) return n - ss.sa[l];
      return rmq.query(l + 1, r + 1);
    };
    while (q--) {
      cin >> k >> l;
      vector<long long int> a;
      for (i = 0; i < (k); ++i) {
        cin >> in;
        in = id[in];
        a.push_back(2 * in);
      }
      for (i = 0; i < (l); ++i) {
        cin >> in;
        in = id[in];
        a.push_back(2 * in + 1);
      }
      sort(begin(a), end(a));
      const long long int m = ((long long int)(a).size());
      vector<pair<long long int, pair<long long int, long long int>>> ed;
      for (i = 0; i < (m - 1); ++i)
        ed.push_back({-query(a[i] / 2, a[i + 1] / 2), {i, i + 1}});
      sort(begin(ed), end(ed));
      ;
      UF uf(m, a);
      long long int ans = 0;
      for (auto x : ed)
        ans += (-x.first) * uf.join(x.second.first, x.second.second);
      cout << ans << "\n";
    }
  }
  aryanc403();
  return 0;
}