30636번 - Задачечка на подстрочечки 서브태스크다국어

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

Для этого он взял строку $t$ и набор из $n$ строк $s_1$, $s_2$, $s_3$, \ldots, $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$-й запрос.

В первом примере в первом запросе требуется у всей строки посчитать число подстрок, которые входят в набор. Со строкой <<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 раз как подстрока.