Пусть $$$\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
Рассмотрим запросы:
Название |
---|