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;
class SegmentTree {
 public:
  SegmentTree(int _n) : n(_n), N(_n << 1), data(N, INT_MAX) {
    h = 0;
    while (1 << h <= N) {
      ++h;
    }
  }
  void build(vector<int>& nums) {
    copy(nums.begin(), nums.end(), data.begin() + n);
    for (int i = n - 1; i > 0; --i) {
      data[i] = min(data[i << 1], data[i << 1 | 1]);
    }
  }
  int get(int l, int r) {
    l += n;
    r += n;
    int res = INT_MAX;
    while (l <= r) {
      if (l & 0x1) {
        res = min(res, data[l++]);
      }
      if (!(r & 0x1)) {
        res = min(res, data[r--]);
      }
      l >>= 1;
      r >>= 1;
    }
    return res;
  }

 private:
  int N;
  int n;
  int h;
  vector<int> data;
};
class SuffixArray {
 public:
  SuffixArray(const string& s) : N(s.length()), st(N + 100) { build(s); }
  const vector<int>& getSuffixArray() { return sa; }
  const vector<int>& getIndexArray() { return indices; }
  const vector<int>& getLcpArray() { return lcp; }
  long long lcpOf(int l, int r) {
    if (l == r) {
      return N - l;
    }
    l = indices[l];
    r = indices[r];
    if (l > r) {
      swap(l, r);
    }
    return st.get(l + 1, r);
  }

 private:
  int N;
  vector<int> sa;
  vector<int> indices;
  vector<int> lcp;
  SegmentTree st;
  struct Datum {
   public:
    Datum(int i = -1, int k0 = -1, int k1 = -1)
        : index(i), key0(k0), key1(k1) {}
    bool operator<(const Datum& other) const {
      return key0 == other.key0 ? key1 < other.key1 : key0 < other.key0;
    }
    int index;
    int key0;
    int key1;
  };
  void build(const string& s) {
    N = s.length();
    sa.clear();
    sa.resize(N, -1);
    indices.clear();
    indices.resize(N, -1);
    vector<Datum> data(N);
    for (int i = 0; i < N; ++i) {
      data[i].index = i;
      data[i].key0 = s[i];
    }
    auto update = [&](int gap) {
      int idx = -1, preKey0 = -1, preKey1 = -1;
      for (int i = 0; i < N; ++i) {
        int key0 = data[i].key0, key1 = data[i].key1;
        if (key0 != preKey0 || key1 != preKey1) {
          data[i].key0 = ++idx;
          preKey0 = key0;
          preKey1 = key1;
        } else {
          data[i].key0 = idx;
        }
        indices[data[i].index] = i;
      }
      for (int i = 0; i < N; ++i) {
        int j = data[i].index + gap;
        if (j < N) {
          data[i].key1 = data[indices[j]].key0;
        } else {
          data[i].key1 = -1;
        }
      }
    };
    sort(data.begin(), data.end());
    int gap = 1;
    update(gap);
    while (gap <= N) {
      sort(data.begin(), data.end());
      update(gap <<= 1);
    }
    for (int i = 0; i < N; ++i) {
      sa[i] = data[i].index;
      indices[sa[i]] = i;
    }
    buildLcp(s);
  }
  void buildLcp(const string& s) {
    lcp.clear();
    lcp.resize(N, 0);
    int len = 0;
    for (int i = 0; i < N; ++i) {
      int idx = indices[i];
      if (idx == 0) {
        lcp[idx] = 0;
        len = 0;
        continue;
      }
      int j = sa[idx - 1];
      while (i + len < N && j + len < N && s[i + len] == s[j + len]) {
        ++len;
      }
      lcp[idx] = len;
      if (len > 0) {
        --len;
      }
    }
    st.build(lcp);
  }
};
class Solution {
 public:
  Solution(const string& s)
      : N(s.length()),
        sfxArr(s),
        lcp(N + 1000, make_pair(-1, -1)),
        cnts(N + 1000, 0),
        sums(N + 1000, 0LL),
        S(s) {}
  long long query(vector<int>& A, int n, vector<int>& B, int m) {
    const auto& indices = sfxArr.getIndexArray();
    auto cmp = [&](int l, int r) { return indices[l] < indices[r]; };
    sort(A.begin(), A.begin() + n, cmp);
    sort(B.begin(), B.begin() + m, cmp);
    if (n > m) {
      swap(A, B);
      swap(n, m);
    }
    long long res = 0;
    int size = 0;
    long long sum = 0;
    for (int i = 0, j = 0; i < n || j < m;) {
      if (j == m) {
        break;
      }
      if (i < n && indices[A[i]] <= indices[B[j]]) {
        int len = 0;
        int cnt = 0;
        if (i == 0) {
          len = N - A[i];
          cnt = 0;
        } else {
          len = sfxArr.lcpOf(A[i - 1], A[i]);
          cnt = 0;
          while (size > 0) {
            if (lcp[size - 1].first >= len) {
              sum -= 1LL * lcp[size - 1].first * lcp[size - 1].second;
              cnt += lcp[size - 1].second;
              --size;
            } else {
              break;
            }
          }
        }
        if (cnt > 0) {
          lcp[size].first = len;
          lcp[size].second = cnt;
          sum += 1LL * len * cnt;
          cnts[size + 1] = cnts[size] + cnt;
          sums[size + 1] = sum;
          ++size;
        }
        lcp[size].first = N - A[i];
        lcp[size].second = 1;
        sum += N - A[i];
        cnts[size + 1] = cnts[size] + 1;
        sums[size + 1] = sum;
        assert(cnts[size + 1] == i + 1);
        ++size;
        ++i;
      } else {
        if (i - 1 >= 0) {
          int len = sfxArr.lcpOf(A[i - 1], B[j]);
          auto it =
              lower_bound(lcp.begin(), lcp.begin() + size, make_pair(len, 0));
          int idx = it - lcp.begin() - 1;
          if (idx < 0) {
            res += 1LL * len * i;
          } else {
            res += sums[idx + 1] + 1LL * len * (i - cnts[idx + 1]);
          }
        }
        ++j;
      }
    }
    size = 0;
    sum = 0;
    for (int i = n - 1, j = m - 1; i >= 0 || j >= 0;) {
      if (j < 0) {
        break;
      }
      if (i >= 0 && indices[A[i]] > indices[B[j]]) {
        int len = 0;
        int cnt = 0;
        if (i == n - 1) {
          len = N - A[i];
          cnt = 0;
        } else {
          len = sfxArr.lcpOf(A[i + 1], A[i]);
          cnt = 0;
          while (size > 0) {
            if (lcp[size - 1].first >= len) {
              sum -= 1LL * lcp[size - 1].first * lcp[size - 1].second;
              cnt += lcp[size - 1].second;
              --size;
            } else {
              break;
            }
          }
        }
        if (cnt > 0) {
          lcp[size].first = len;
          lcp[size].second = cnt;
          sum += 1LL * len * cnt;
          cnts[size + 1] = cnts[size] + cnt;
          sums[size + 1] = sum;
          ++size;
        }
        lcp[size].first = N - A[i];
        lcp[size].second = 1;
        sum += N - A[i];
        cnts[size + 1] = cnts[size] + 1;
        sums[size + 1] = sum;
        assert(cnts[size + 1] == n - i);
        ++size;
        --i;
      } else {
        if (i + 1 < n) {
          int len = sfxArr.lcpOf(A[i + 1], B[j]);
          auto it =
              lower_bound(lcp.begin(), lcp.begin() + size, make_pair(len, 0));
          int idx = it - lcp.begin() - 1;
          if (idx < 0) {
            res += 1LL * len * (n - i - 1);
          } else {
            res += sums[idx + 1] + 1LL * len * (n - i - 1 - cnts[idx + 1]);
          }
        }
        --j;
      }
    }
    return res;
  }

 private:
  int N;
  string S;
  SuffixArray sfxArr;
  vector<pair<int, int>> lcp;
  vector<int> cnts;
  vector<long long> sums;
  void check(vector<int>& A, int n, vector<int>& B, int m, long long res) {
    long long ans = 0;
    int N = S.length();
    auto LCP = [&](int x, int y) {
      int res = 0;
      for (int i = x, j = y; i < N && j < N; ++i, ++j) {
        if (S[i] == S[j]) {
          ++res;
        } else {
          break;
        }
      }
      return res;
    };
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        int a = A[i], b = B[j];
        ans += LCP(a, b);
      }
    }
    if (ans != res) {
      cout << "ERROR: WA "
           << " got " << res << " but expected " << ans << endl;
    }
  }
};
void test() {
  vector<string> ts = {{"adsfadfqiewruypzdjfquwieroyzsdf",
                        "zduoifyqewrjhlzjkdhfvuioqerwy",
                        "adsfuiaednbklzjdrfyquioerwyhadnfb", "aaaaaaaaaaaaaaa",
                        "axaaxadaxaacaaxxaad"}};
  cout << "test " << endl;
  for (auto s : ts) {
    Solution sol(s);
    int n = s.length();
    vector<int> A(n);
    iota(A.begin(), A.end(), 0);
    vector<int> B(n);
    iota(B.begin(), B.end(), 0);
    sol.query(A, n, B, n);
  }
}
int main(int argc, char** argv) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  Solution sol(s);
  vector<int> A(n + 100);
  vector<int> B(n + 100);
  int k, l;
  while (q-- > 0) {
    cin >> k >> l;
    for (int i = 0; i < k; ++i) {
      cin >> A[i];
      --A[i];
    }
    for (int j = 0; j < l; ++j) {
      cin >> B[j];
      --B[j];
    }
    cout << sol.query(A, k, B, l) << endl;
  }
  return 0;
}