부분 문자열 문제

필립은 문자열 문제를 아주 좋아한다. 그는 이미 알고 있던 문제를 모두 풀었지만 그것으로는 부족해서 직접 문제를 만들기로 했다.

그는 문자열 $t$와 $n$개의 문자열 $s_1$, $s_2$, $s_3$, $\ldots$, $s_n$으로 이루어진 집합을 골랐다. 필립에게는 $m$개의 쿼리가 있다. $i$번째 쿼리에서 필립은 $t$의 $l_i$번째 문자부터 $r_i$번째 문자까지의 부분 문자열을 잡고, 그 안에서 집합의 어떤 문자열과 일치하는 부분 문자열의 개수를 세고 싶어 한다. 정확히는 $l_i \le a \le b \le r_i$를 만족하고, $t$의 $a$번째 문자부터 $b$번째 문자까지의 부분 문자열이 집합의 어떤 $s_j$와 같은 위치 쌍 $(a, b)$의 개수를 구하는 것이다.

$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$개 줄에는 각각 하나의 문자열 $s_i$가 주어진다. 각 $s_i$는 소문자 영어 알파벳으로만 이루어져 있다. 집합에 있는 모든 문자열 길이의 합을 $S$라고 하면 $S \le 10^6$이다. 또한 모든 $s_i$는 서로 다르다.

다음 $m$개 줄에는 쿼리가 주어진다. $i$번째 쿼리는 양의 정수 $l_i$, $r_i$로 이루어지며 ($1 \le l_i \le r_i \le |t|$), $t$에서 잘라낼 부분 문자열의 왼쪽 경계와 오른쪽 경계를 뜻한다.

한 줄에 $m$개의 정수를 출력한다. $i$번째 정수는 $i$번째 쿼리의 답이다.

첫 번째 예제의 첫 번째 쿼리에서는 전체 문자열 안에서 집합에 속하는 부분 문자열을 센다. aba는 $[1, 3]$, $[4, 6]$과 일치한다. a는 $[1, 1]$, $[3, 3]$, $[5, 5]$, $[7, 7]$과 일치한다. ac는 $[3, 4]$와만 일치한다. 따라서 abacaba에서 집합의 문자열과 일치하는 부분 문자열은 모두 7개이다.

두 번째 쿼리에서 1번째부터 3번째 문자까지의 부분 문자열은 aba이다. 여기에는 aba가 1번, a가 2번 나타나고, ac는 전혀 나타나지 않는다.

세 번째 쿼리에서 2번째부터 7번째 문자까지의 부분 문자열은 bacaba이다. 여기에는 aba가 1번, a가 3번, ac가 1번 나타난다.