Philipp loves string problems. He has already solved all the problems he knows, but that was not enough for him. Therefore, Philipp decided to come up with his own problem.

For this, he took a string $t$ and a set of $n$ strings $s_1, s_2, s_3, \dots, s_n$. Philipp has $m$ queries. In the $i$-th query, Philipp wants to take the substring of $t$ from the $l_i$-th to the $r_i$-th character and count the number of its substrings that match some string from the set. More formally, Philipp wants to count the number of pairs of positions $a, b$ such that $l_i \le a \le b \le r_i$, and the substring of $t$ from the $a$-th to the $b$-th character matches some string $s_j$ from the set.

A substring of $t$ from the $a$-th to the $b$-th character is defined as the string obtained from $t$ by removing the first $a-1$ characters and the last $|t|-b$ characters, where $|t|$ denotes the length of string $t$.

Philipp has already solved this problem, but can you?

Input

The first line contains two positive integers $n$ and $m$ ($1 \le n, m \le 500\,000$) — the number of strings in the set and the number of queries.

The second line contains a single string $t$ consisting of lowercase English letters ($1 \le |t| \le 5 \cdot 10^6$).

The next $n$ lines describe the strings in the set. The $i$-th of these lines contains a single string $s_i$ consisting of lowercase English letters. Let $S$ be the total length of all strings in the set. It is guaranteed that $S \le 10^6$, and that all strings $s_i$ are distinct.

The following lines contain the queries. The $i$-th query contains two positive integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le |t|$) — the left and right boundaries of the substring of $t$ for the $i$-th query.

Output

Output $m$ integers on a single line, where the $i$-th integer is the answer to the $i$-th query.

Examples

Input 1

3 5
abacaba
aba
a
ac
1 7
1 3
2 7
2 5
4 5

Output 1

7 3 5 3 1

Input 2

4 4
abcdca
ab
ca
bcd
openolympiad
1 5
2 2
2 6
1 6

Output 2

2 0 2 3

Note

In the first example, the first query asks to count the number of substrings of the entire string that are in the set. The substrings $[1, 3]$ and $[4, 6]$ match the string "aba". The substrings $[1, 1]$, $[3, 3]$, $[5, 5]$, and $[7, 7]$ match the string "a". The substring $[3, 4]$ matches the string "ac". In total, 7 substrings of "abacaba" match strings from the set.

In the second query, the substring from position 1 to 3 is taken, which is "aba". The string "aba" occurs 1 time, "a" occurs 2 times, and "ac" occurs 0 times as a substring.

In the third query, the substring from position 2 to 7 is taken, which is "bacaba". The string "aba" occurs 1 time, "a" occurs 3 times, and "ac" occurs 1 time as a substring.

Subtasks

The tests for this problem consist of 9 groups. Points for each group are awarded only if all tests in the group and all tests in certain previous groups are passed. "Offline-check" means that the results of testing your solution on this group will only become available after the competition ends.