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 {
const int BUFFER_SIZE = 1 << 15;
FILE *input_stream = stdin;
FILE *output_stream = stdout;
char input_buffer[BUFFER_SIZE];
int input_pos = 0, input_len = 0;
char output_buffer[BUFFER_SIZE];
int output_pos = 0;
char number_buffer[100];
uint8_t lookup[100];
void redirect(const char *input_file, const char *output_file) {
  input_stream = fopen(input_file, "r");
  output_stream = fopen(output_file, "w");
}
void _update_input_buffer() {
  input_len = fread(input_buffer, sizeof(char), BUFFER_SIZE, input_stream);
  input_pos = 0;
}
inline char next_char(bool advance = true) {
  if (input_pos >= input_len) _update_input_buffer();
  return input_buffer[advance ? input_pos++ : input_pos];
}
inline bool isspace(char c) {
  return (unsigned char)(c - '\t') < 5 || c == ' ';
}
inline bool on_whitespace() { return isspace(next_char(false)); }
inline bool on_digit() { return isdigit(next_char(false)); }
inline void skip_whitespace() {
  while (on_whitespace()) next_char();
}
inline bool input_finished() {
  while (on_whitespace() && input_len > 0) next_char();
  return input_len < BUFFER_SIZE && input_pos >= input_len;
}
template <typename T>
inline void read_int(T &number) {
  skip_whitespace();
  bool negative = next_char(false) == '-';
  if (negative) next_char();
  number = 0;
  while (on_digit()) number = 10 * number + (next_char() - '0');
  if (negative) number = -number;
}
inline void read_double(double &number) {
  skip_whitespace();
  bool negative = next_char(false) == '-';
  if (negative) next_char();
  number = 0;
  while (on_digit()) number = 10 * number + (next_char() - '0');
  if (next_char(false) == '.') {
    next_char();
    for (double multiplier = 0.1; on_digit(); multiplier *= 0.1)
      number += multiplier * (next_char() - '0');
  }
  if (negative) number = -number;
}
inline void read_char(char &c) {
  skip_whitespace();
  c = next_char();
}
inline void read_str(char *str) {
  skip_whitespace();
  while (!on_whitespace()) *str++ = next_char();
  *str = '\0';
}
inline void read_str(string &str) {
  str.clear();
  skip_whitespace();
  while (!on_whitespace()) str += next_char();
}
inline void read_line(char *str) {
  while (next_char(false) == '\n') next_char();
  while (next_char(false) != '\n') *str++ = next_char();
  *str = '\0';
}
void flush_output() {
  fwrite(output_buffer, sizeof(char), output_pos, output_stream);
  output_pos = 0;
}
inline void write_char(char c) {
  if (output_pos == BUFFER_SIZE) flush_output();
  output_buffer[output_pos++] = c;
}
template <typename T>
inline void write_int(T number, char after = '\0') {
  if (number < 0) {
    write_char('-');
    number = -number;
  }
  int length = 0;
  do {
    if (number < 10) {
      number_buffer[length++] = number + '0';
      number = 0;
    } else {
      uint8_t lookup_value = lookup[number % 100];
      number /= 100;
      number_buffer[length++] = (lookup_value & 15) + '0';
      number_buffer[length++] = (lookup_value >> 4) + '0';
    }
  } while (number != 0);
  for (int i = length - 1; i >= 0; i--) write_char(number_buffer[i]);
  if (after) write_char(after);
}
inline void write_str(const char *str, char after = '\0') {
  while (*str) write_char(*str++);
  if (after) write_char(after);
}
inline void write_str(const string &str, char after = '\0') {
  for (char c : str) write_char(c);
  if (after) write_char(after);
}
inline void write_double(double number, char after = '\0', int places = 6) {
  if (number < 0) {
    write_char('-');
    number = -number;
  }
  assert(number <= 9e18);
  number += 0.5 * pow(0.1, places);
  long long floored = (long long)number;
  write_int(floored);
  if (places > 0) {
    write_char('.');
    number = (number - floored) * pow(10.0, places);
    floored = (long long)number;
    int length = 0;
    for (int i = 0; i < places / 2; i++) {
      uint8_t lookup_value = lookup[floored % 100];
      floored /= 100;
      number_buffer[length++] = (lookup_value & 15) + '0';
      number_buffer[length++] = (lookup_value >> 4) + '0';
    }
    if (places % 2) number_buffer[length++] = floored + '0';
    assert(length == places);
    for (int i = places - 1; i >= 0; i--) write_char(number_buffer[i]);
  }
  if (after) write_char(after);
}
void init() {
  bool exit_success = atexit(flush_output) == 0;
  assert(exit_success);
  for (int i = 0; i < 100; i++) lookup[i] = (i / 10 << 4) + i % 10;
}
}  // namespace IO
template <typename T>
struct RMQ {
  int n, levels;
  vector<vector<T>> range_min;
  RMQ(const vector<T> &values = {}) {
    if (!values.empty()) build(values);
  }
  void build(const vector<T> &values) {
    n = values.size();
    levels = 32 - __builtin_clz(n);
    range_min.resize(levels);
    for (int k = 0; k < levels; k++) range_min[k].resize(n - (1 << k) + 1);
    for (int i = 0; i < n; i++) range_min[0][i] = values[i];
    for (int k = 1; k < levels; k++)
      for (int i = 0; i <= n - (1 << k); i++)
        range_min[k][i] =
            min(range_min[k - 1][i], range_min[k - 1][i + (1 << k - 1)]);
  }
  T query(int a, int b) const {
    assert(a < b);
    int level = 31 - __builtin_clz(b - a);
    return min(range_min[level][a], range_min[level][b - (1 << level)]);
  }
};
struct suffix_array {
  int n;
  vector<int> suffix;
  vector<int> rank;
  vector<int> lcp;
  RMQ<int> rmq;
  suffix_array() {}
  template <typename T_string>
  suffix_array(const T_string &str, bool build_rmq = true) : n(0) {
    if (!str.empty()) build(str, build_rmq);
  }
  template <typename T_string>
  void build(const T_string &str, bool build_rmq = true) {
    n = str.size();
    suffix.resize(n);
    for (int i = 0; i < n; i++) suffix[i] = i;
    bool large_alphabet = false;
    for (int i = 0; i < n; i++)
      if (str[i] < 0 || str[i] >= 128) large_alphabet = true;
    if (large_alphabet) {
      sort(suffix.begin(), suffix.end(),
           [&](int a, int b) { return str[a] < str[b]; });
    } else {
      vector<int> freq(128, 0);
      for (int i = 0; i < n; i++) freq[str[i]]++;
      for (int c = 1; c < 128; c++) freq[c] += freq[c - 1];
      for (int i = 0; i < n; i++) suffix[--freq[str[i]]] = i;
    }
    rank.resize(n);
    rank[suffix[0]] = 0;
    for (int i = 1; i < n; i++)
      rank[suffix[i]] =
          str[suffix[i]] == str[suffix[i - 1]] ? rank[suffix[i - 1]] : i;
    vector<int> next_index(n);
    vector<int> values(n);
    bool done = false;
    for (int len = 1; len < n && !done; len *= 2) {
      for (int i = 0; i < n; i++) next_index[i] = i;
      for (int i = n - len; i < n; i++) values[next_index[rank[i]]++] = i;
      for (int i = 0; i < n; i++) {
        int prev = suffix[i] - len;
        if (prev >= 0) values[next_index[rank[prev]]++] = prev;
      }
      swap(suffix, values);
      values[suffix[0]] = 0;
      done = true;
      for (int i = 1; i < n; i++) {
        int s = suffix[i], prev = suffix[i - 1];
        if (s + len < n && prev + len < n && rank[s] == rank[prev] &&
            rank[s + len] == rank[prev + len]) {
          values[s] = values[prev];
          done = false;
        } else {
          values[s] = i;
        }
      }
      swap(rank, values);
    }
    compute_lcp(str);
    if (build_rmq) rmq.build(lcp);
  }
  template <typename T_string>
  void compute_lcp(const T_string &str) {
    lcp.assign(n, 0);
    int match = 0;
    for (int i = 0; i < n; i++) {
      if (rank[i] == 0) continue;
      int a = suffix[rank[i]] + match, b = suffix[rank[i] - 1] + match;
      while (a < n && b < n && str[a++] == str[b++]) match++;
      lcp[rank[i]] = match;
      match = max(match - 1, 0);
    }
  }
  int get_lcp(int a, int b) {
    if (a == b) return n - a;
    if (a >= n || b >= n) return 0;
    a = rank[a];
    b = rank[b];
    if (a > b) swap(a, b);
    return rmq.query(a + 1, b + 1);
  }
};
suffix_array SA;
long long solve_all_pairs(const vector<int> &ranks) {
  int n = ranks.size();
  long long total = 0;
  vector<pair<int, int>> stack;
  long long stack_sum = 0;
  for (int i = 0; i < n; i++) {
    int lcp =
        i == 0 ? 0 : SA.get_lcp(SA.suffix[ranks[i - 1]], SA.suffix[ranks[i]]);
    int count = 1;
    while (!stack.empty() && lcp <= stack.back().first) {
      stack_sum -= (long long)stack.back().second * stack.back().first;
      count += stack.back().second;
      stack.pop_back();
    }
    stack.emplace_back(lcp, count);
    stack_sum += (long long)lcp * count;
    total += stack_sum;
  }
  return total;
}
int main() {
  IO::init();
  int N, Q;
  string str;
  IO::read_int(N);
  IO::read_int(Q);
  IO::read_str(str);
  SA.build(str);
  for (int q = 0; q < Q; q++) {
    int K, L;
    IO::read_int(K);
    IO::read_int(L);
    vector<int> A(K), B(L);
    for (int &a : A) {
      IO::read_int(a);
      a--;
      a = SA.rank[a];
    }
    for (int &b : B) {
      IO::read_int(b);
      b--;
      b = SA.rank[b];
    }
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    vector<int> combined(A.size() + B.size());
    merge(A.begin(), A.end(), B.begin(), B.end(), combined.begin());
    IO::write_int(
        solve_all_pairs(combined) - solve_all_pairs(A) - solve_all_pairs(B),
        '\n');
  }
}