G. Задачечка на подстрочечки
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод
Филипп очень любит задачечки на строчечки. Он уже решил все известные ему задачечки, но этого ему было мало. Поэтому Филипп решил придумать свою собственную задачечку.

Для этого он взял строку $$$t$$$ и набор из $$$n$$$ строк $$$s_1$$$, $$$s_2$$$, $$$s_3$$$, ..., $$$s_n$$$. У Филиппа есть $$$m$$$ запросов, в $$$i$$$-м из них Филипп хочет взять подстроку строки $$$t$$$ с $$$l_i$$$-го по $$$r_i$$$-й символ, и посчитать число её подстрок, которые совпадают с какой-то строкой из набора. Более формально, Филипп хочет посчитать число пар позиций $$$a$$$, $$$b$$$, таких что $$$l_i \le a \le b \le r_i$$$, и подстрока строки $$$t$$$ с $$$a$$$-го по $$$b$$$-й символ совпадает с некоторой строкой $$$s_j$$$ из набора.

Подстрокой строки $$$t$$$ с $$$a$$$-го по $$$b$$$-й символ называется строка, полученная из $$$t$$$ путём удаления $$$a - 1$$$ символа из начала и $$$|t| - b$$$ символами из конца, где $$$|t|$$$ обозначает длину строки $$$t$$$.

Филипп уже решил эту задачу, а сможете ли вы?

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

В первой строке два целых положительных числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 500\,000$$$) — число строк в наборе и количество запросов.

Во второй строке дана единственная строка $$$t$$$, состоящая из строчных букв английского алфавита ($$$1 \le |t| \le 5 \cdot 10^6$$$).

В следующих $$$n$$$ строках описываются строки из набора. В $$$i$$$-й из них дана единственная строка $$$s_i$$$, состоящая из строчных букв английского алфавита. Обозначим за $$$S$$$ суммарную длину всех строк из набора. Гарантируется, что $$$S \le 10^6$$$, а так же что все строки $$$s_i$$$ различны.

В следующих строках вводятся запросы. В $$$i$$$-й из них даны два целых положительных числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le |t|$$$) — левая и правая граница подстроки $$$t$$$ из $$$i$$$-го запроса.

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

В единственной строке выведите $$$m$$$ целых чисел, $$$i$$$-е из них должно быть равно ответу на $$$i$$$-й запрос.

Примеры

Входные данные
3 5
abacaba
aba
a
ac
1 7
1 3
2 7
2 5
4 5
Выходные данные
7 3 5 3 1
Входные данные
4 4
abcdca
ab
ca
bcd
openolympiad
1 5
2 2
2 6
1 6
Выходные данные
2 0 2 3
Примечание

В первом примере в первом запросе требуется у всей строки посчитать число подстрок, которые входят в набор. Со строкой «aba» совпадают подстроки $$$[1, 3]$$$ и $$$[4, 6]$$$. Со строкой «a» совпадают подстроки $$$[1, 1]$$$, $$$[3, 3]$$$, $$$[5, 5]$$$, $$$[7, 7]$$$. Со строкой «ac» совпадает подстрока $$$[3, 4]$$$. Всего получается, что 7 подстрок строки «abacaba» совпадают со строками из набора.

Во втором запросе от исходной строки берется подстрока с 1 по 3 позицию, это строка «aba». В неё строка «aba» входит 1 раз, строка «a» входит 2 раза и строка «ac» не входит ни одного раза как подстрока. В третьем запросе от исходной строки берется подстрока с 2 по 7 позицию, это строка «bacaba». В неё строка «aba» входит 1 раз, строка «a» входит 3 раза и строка «ac» входит 1 раз как подстрока.