G. Очередная задача на строки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пусть $$$\text{LCP}(s, t)$$$ будет длиной наидлиннейшего общего префикса строк $$$s$$$ и $$$t$$$. Также назовем $$$s[x \dots y]$$$ подстрокой $$$s$$$ с позиции $$$x$$$ до позиции $$$y$$$ (включительно). Например, если $$$s = $$$ «abcde», то $$$s[1 \dots 3] =$$$ «abc», $$$s[2 \dots 5] =$$$ «bcde».

Задана строка $$$s$$$ длины $$$n$$$, а также $$$q$$$ запросов. Каждый запрос — это пара множеств целых чисел $$$a_1, a_2, \dots, a_k$$$ и $$$b_1, b_2, \dots, b_l$$$. Посчитайте $$$\sum\limits_{i = 1}^{i = k} \sum\limits_{j = 1}^{j = l}{\text{LCP}(s[a_i \dots n], s[b_j \dots n])}$$$ для каждого запроса.

Входные данные

В первой строке записаны два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — длина строки $$$s$$$ и количество запросов, соответственно.

Во второй строке записана строка $$$s$$$, состоящая из строчных букв латинского алфавита ($$$|s| = n$$$).

Следующие $$$3q$$$ строк содержат описания запросов — три строки на запрос. В первой строке каждого запроса записаны по два целых числа $$$k_i$$$ и $$$l_i$$$ ($$$1 \le k_i, l_i \le n$$$) — размеры множеств $$$a$$$ и $$$b$$$, соответственно.

Во второй строке каждого запроса записаны $$$k_i$$$ целых чисел $$$a_1, a_2, \dots a_{k_i}$$$ ($$$1 \le a_1 < a_2 < \dots < a_{k_i} \le n$$$) — множество $$$a$$$.

В третьей строке каждого запроса записаны $$$l_i$$$ целых чисел $$$b_1, b_2, \dots b_{l_i}$$$ ($$$1 \le b_1 < b_2 < \dots < b_{l_i} \le n$$$) — множество $$$b$$$.

Гарантируется, что $$$\sum\limits_{i = 1}^{i = q}{k_i} \le 2 \cdot 10^5$$$ и $$$\sum\limits_{i = 1}^{i = q}{l_i} \le 2 \cdot 10^5$$$.

Выходные данные

Выведите $$$q$$$ целых чисел — ответы на запросы в том же порядке, в каком запросы подавались во входных данных.

Пример
Входные данные
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
Выходные данные
13
2
12
16
Примечание

Рассмотрим запросы:

  1. В первом запросе участвуют $$$s[1 \dots 7] = \text{abacaba}$$$ и $$$s[2 \dots 7] = \text{bacaba}$$$. Ответ равен $$$\text{LCP}(\text{abacaba}, \text{abacaba}) + \text{LCP}(\text{abacaba}, \text{bacaba}) + \text{LCP}(\text{bacaba}, \text{abacaba}) + \text{LCP}(\text{bacaba}, \text{bacaba}) = 7 + 0 + 0 + 6 = 13$$$.
  2. Во втором запросе участвуют $$$s[1 \dots 7] = \text{abacaba}$$$, $$$s[2 \dots 7] = \text{bacaba}$$$, $$$s[3 \dots 7] = \text{acaba}$$$ и $$$s[7 \dots 7] = \text{a}$$$. Ответ равен $$$\text{LCP}(\text{abacaba}, \text{a}) + \text{LCP}(\text{bacaba}, \text{a}) + \text{LCP}(\text{acaba}, \text{a}) = 1 + 0 + 1 = 2$$$.
  3. В третьем запросе $$$s[1 \dots 7] = \text{abacaba}$$$ сравнивается со всеми суффиксами. Ответ состоит из следующих ненулевых значений: $$$\text{LCP}(\text{abacaba}, \text{abacaba}) + \text{LCP}(\text{abacaba}, \text{acaba}) + \text{LCP}(\text{abacaba}, \text{aba}) + \text{LCP}(\text{abacaba}, \text{a}) = 7 + 1 + 3 + 1 = 12$$$.
  4. В четвертом запросе участвуют $$$s[1 \dots 7] = \text{abacaba}$$$ и $$$s[5 \dots 7] = \text{aba}$$$. Ответ равен $$$\text{LCP}(\text{abacaba}, \text{abacaba}) + \text{LCP}(\text{abacaba}, \text{aba}) + \text{LCP}(\text{aba}, \text{abacaba}) + \text{LCP}(\text{aba}, \text{aba}) = 7 + 3 + 3 + 3 = 16$$$.