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;
namespace IO {
char buf[1 << 21], *p1 = buf, *p2 = buf, buf1[1 << 21];
inline char gc() {
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
template <class I>
inline void read(I &x) {
  x = 0;
  I f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  x *= f;
}
template <class I>
inline void write(I x) {
  if (x == 0) {
    putchar('0');
    return;
  }
  I tmp = x > 0 ? x : -x;
  if (x < 0) putchar('-');
  long long cnt = 0;
  while (tmp > 0) {
    buf1[cnt++] = tmp % 10 + '0';
    tmp /= 10;
  }
  while (cnt > 0) putchar(buf1[--cnt]);
}
}  // namespace IO
using namespace IO;
long long n, q;
char s[500010];
long long Matrix[500010][50];
namespace DS {
class Suf_arr {
 private:
  long long x[500010], y[500010];
  long long bu[500010];

 public:
  long long sa[500010], rk[500010];
  long long ht[500010];
  void debug() {
    for (long long i = 1; i <= n; i++) {
      write(sa[i]), putchar(' ');
    }
    puts("");
    for (long long i = 1; i <= n; i++) {
      write(rk[i]), putchar(' ');
    }
    puts("");
    for (long long i = 1; i <= n; i++) {
      write(ht[i]), putchar(' ');
    }
    puts("");
  }
  void get_sa(char *s) {
    long long m = (1 << 7) + 1;
    for (long long i = 1; i <= n; i++) {
      x[i] = s[i - 1];
      ++bu[x[i]];
    }
    for (long long i = 1; i <= m; i++) {
      bu[i] += bu[i - 1];
    }
    for (long long i = n; i >= 1; i--) {
      sa[bu[x[i]]--] = i;
    }
    for (long long k = 1; k <= n; k <<= 1) {
      long long num_cnt = 0;
      for (long long i = n - k + 1; i <= n; i++) {
        y[++num_cnt] = i;
      }
      for (long long i = 1; i <= n; i++) {
        if (sa[i] > k) {
          y[++num_cnt] = sa[i] - k;
        }
      }
      for (long long i = 1; i <= m; i++) {
        bu[i] = 0;
      }
      for (long long i = 1; i <= n; i++) {
        ++bu[x[i]];
      }
      for (long long i = 1; i <= m; i++) {
        bu[i] += bu[i - 1];
      }
      for (long long i = n; i >= 1; i--) {
        sa[bu[x[y[i]]]--] = y[i];
        y[i] = 0;
      }
      std::swap(x, y);
      num_cnt = 1;
      x[sa[1]] = 1;
      for (long long i = 2; i <= n; i++) {
        if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) {
          x[sa[i]] = num_cnt;
        } else {
          x[sa[i]] = ++num_cnt;
        }
      }
      if (num_cnt == n) {
        break;
      }
      m = num_cnt;
    }
  }
  void get_ht(char *s) {
    long long len = strlen(s), k = 0;
    for (long long i = 1; i <= len; i++) {
      rk[sa[i]] = i;
    }
    for (long long i = 1; i <= len; i++) {
      if (rk[i] == 1) {
        continue;
      }
      if (k) {
        --k;
      }
      long long pos = sa[rk[i] - 1];
      while (pos + k <= len && i + k <= len && s[pos + k - 1] == s[i + k - 1]) {
        ++k;
      }
      ht[rk[i]] = k;
    }
  }
} sa;
}  // namespace DS
using namespace DS;
long long lg[500010];
void init() {
  read(n), read(q);
  std::cin >> s;
  long long len = strlen(s);
  sa.get_sa(s);
  sa.get_ht(s);
  lg[0] = 0;
  for (long long i = 1; i <= n; i++) {
    lg[i] = lg[i - 1] + (1 << lg[i - 1] + 1 == i);
  }
  for (long long i = 1; i <= len; i++) {
    Matrix[i][0] = sa.ht[i];
  }
  for (long long j = 1; 1 << j <= len; j++) {
    for (long long i = 1; i + (1 << j) - 1 <= n; i++) {
      Matrix[i][j] =
          std::min(Matrix[i][j - 1], Matrix[i + (1 << (j - 1))][j - 1]);
    }
  }
}
long long rmq(long long l, long long r) {
  long long k = lg[r - l + 1];
  return std::min(Matrix[l][k], Matrix[r - (1 << k) + 1][k]);
}
long long lcp(long long l, long long r) {
  if (l == r) {
    return n - l + 1;
  }
  if (sa.rk[l] > sa.rk[r]) {
    std::swap(l, r);
  }
  return rmq(sa.rk[l] + 1, sa.rk[r]);
}
long long len_1, len_2;
long long a[500010], b[500010], c[500010];
long long key[500010];
long long sum[500010];
struct sta {
  long long first;
  long long second;
} Sta[500010];
void update(long long &ans, long long i, long long top) {
  ans += (1ll * (sum[Sta[top].first - 1] - sum[Sta[top].second - 2]) *
              ((i - Sta[top].first) - (sum[i - 1] - sum[Sta[top].first - 1])) +
          1ll *
              ((Sta[top].first - Sta[top].second + 1) -
               (sum[Sta[top].first - 1] - sum[Sta[top].second - 2])) *
              (sum[i - 1] - sum[Sta[top].first - 1])) *
         lcp(c[Sta[top].first], c[Sta[top].first - 1]);
  return;
  ans += (1ll * (sum[Sta[top].first - 1] - sum[Sta[top].second - 2]) *
              ((i - Sta[top].first) - (sum[i - 1] - sum[Sta[top].first - 1])) +
          1ll *
              ((Sta[top].first - Sta[top].second + 1) -
               (sum[Sta[top].first - 1] - sum[Sta[top].second - 2])) *
              (sum[i - 1] - sum[Sta[top].first - 1])) *
         lcp(c[Sta[top].first], c[Sta[top].first - 1]);
}
void tab() {
  long long times = 5;
  while (times--) {
    printf("\t");
  }
}
bool cmp(long long a, long long b) { return sa.rk[a] < sa.rk[b]; }
signed main() {
  init();
  while (q--) {
    read(len_1), read(len_2);
    for (long long i = 1; i <= len_1; i++) {
      read(a[i]);
    }
    for (long long i = 1; i <= len_2; i++) {
      read(b[i]);
    }
    std::sort(a + 1, a + len_1 + 1,
              [&](long long a, long long b) { return sa.rk[a] < sa.rk[b]; });
    std::sort(b + 1, b + len_2 + 1,
              [&](long long a, long long b) { return sa.rk[a] < sa.rk[b]; });
    for (long long i = 1, j = 1, t = 1; i <= len_1 || j <= len_2; t++) {
      if (i <= len_1 && (j > len_2 || sa.rk[a[i]] <= sa.rk[b[j]])) {
        c[t] = a[i++];
        key[t] = 0;
      } else if (j <= len_2 && (i > len_1 || sa.rk[a[i]] > sa.rk[b[j]])) {
        c[t] = b[j++];
        key[t] = 1;
      }
    }
    long long ans = 0;
    sum[0] = 0;
    long long top = 0;
    for (long long i = 1; i <= len_1 + len_2; i++) {
      sum[i] = sum[i - 1] + key[i];
    }
    for (long long i = 1; i <= len_1 + len_2; i++) {
      long long now = i;
      while (top > 0 && lcp(c[i], c[i - 1]) < lcp(c[Sta[top - 1].first],
                                                  c[Sta[top - 1].first - 1])) {
        now = std::min(now, Sta[--top].second);
        update(ans, i, top);
      }
      Sta[top++] = (sta){i, now};
    }
    while (top > 0) {
      --top;
      update(ans, len_1 + len_2 + 1, top);
    }
    write(ans), putchar('\n');
  }
  return 0;
}