310234: CF1801G. A task for substrings

G. A task for substringstime limit per test4 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output Philip is very fond of tasks on the lines. He had already solved all the problems known to him, but this was not enough for him. Therefore, Philip decided to come up with his own task.

To do this, he took the string $t$ and a set of $n$ strings $s_1$, $s_2$, $s_3$, ..., $s_n$. Philip has $m$ queries, in the $i$th of them, Philip wants to take a substring of the string $t$ from $l_i$th to $r_i$th character, and count the number of its substrings that match some string from the set. More formally, Philip 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 the string $t$ from $a$th to $b$th character coincides with some string $s_j$ from the set.

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

Philip 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 rows in the set and the number of queries.

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

The following $n$ lines describe the strings from the set. In the $i$th of them, a single string $s_i$ is given, consisting of lowercase letters of the English alphabet. Denote by $S$ the total length of all strings from the set. It is guaranteed that $S \le 10^6$, as well as that all strings of $s_i$ are different.

In the following lines, queries are entered. The $i$th of them contains two positive integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le |t|$) — the left and right border of the substring $t$ from the $i$-th query.

Output

In a single line, print $m$ integers, $i$th of them should be equal to the answers to the $i$th query.

Examples

Input

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

Output

7 3 5 3 1 

Input

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

Output

2 0 2 3 

Note

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

In the second query, a substring from position 1 to position 3 is taken from the source string, this is the string "aba". The string "aba" enters it 1 time, the string "a" enters it 2 times and the string "ac" does not enter it once as a substring. In the third query, a substring from the 2nd to the 7th position is taken from the source string, this is the string "bacaba". The string "aba" is included in it 1 time, the string "a" is included 3 times and the string "ac" is included 1 time as a substring.

题目大意：
这个题目是关于字符串的子串计数问题。给定一个字符串t和n个字符串的集合s_1, s_2, ..., s_n。有m个查询，每个查询是一对左右边界l_i和r_i，要求统计字符串t从l_i到r_i的子串中有多少个子串与集合中的某个字符串匹配。

输入输出数据格式：
输入：
- 第一行是两个正整数n和m（1 ≤ n, m ≤ 500,000），分别表示集合中字符串的个数和查询的个数。
- 第二行是一个由小写英文字母组成的字符串t（1 ≤ |t| ≤ 5 × 10^6）。
- 接下来n行，每行是一个由小写英文字母组成的字符串s_i，表示集合中的字符串。所有s_i字符串的总长度S ≤ 10^6，且所有s_i字符串互不相同。
- 最后m行，每行包含两个正整数l_i和r_i（1 ≤ l_i ≤ r_i ≤ |t|），表示每个查询的左右边界。

输出：
- 一行m个整数，第i个数表示第i个查询的答案，即t的第l_i到第r_i个子串中有多少个子串与集合中的某个字符串匹配。

示例：
输入：
```
3 5
abacaba
aba
a
ac
1 7
1 3
2 7
2 5
4 5
```
输出：
```
7 3 5 3 1
```

注意：
- 在第一个例子中，第一个查询要求计算整个字符串t中有多少个子串包含在集合中。子串[1, 3]和[4, 6]与字符串"aba"匹配，子串[1, 1]、[3, 3]、[5, 5]和[7, 7]与字符串"a"匹配，子串[3, 4]与字符串"ac"匹配。总共，字符串"abacaba"有7个子串与集合中的字符串匹配。
- 在第二个查询中，取源字符串从位置1到位置3的子串，即字符串"aba"。字符串"aba"在其中出现1次，字符串"a"出现2次，字符串"ac"没有出现。在第三个查询中，取源字符串从位置2到位置7的子串，即字符串"bacaba"。字符串"aba"在其中出现1次，字符串"a"出现3次，字符串"ac"出现1次。题目大意： 这个题目是关于字符串的子串计数问题。给定一个字符串t和n个字符串的集合s_1, s_2, ..., s_n。有m个查询，每个查询是一对左右边界l_i和r_i，要求统计字符串t从l_i到r_i的子串中有多少个子串与集合中的某个字符串匹配。 输入输出数据格式： 输入： - 第一行是两个正整数n和m（1 ≤ n, m ≤ 500,000），分别表示集合中字符串的个数和查询的个数。 - 第二行是一个由小写英文字母组成的字符串t（1 ≤ |t| ≤ 5 × 10^6）。 - 接下来n行，每行是一个由小写英文字母组成的字符串s_i，表示集合中的字符串。所有s_i字符串的总长度S ≤ 10^6，且所有s_i字符串互不相同。 - 最后m行，每行包含两个正整数l_i和r_i（1 ≤ l_i ≤ r_i ≤ |t|），表示每个查询的左右边界。 输出： - 一行m个整数，第i个数表示第i个查询的答案，即t的第l_i到第r_i个子串中有多少个子串与集合中的某个字符串匹配。 示例： 输入： ``` 3 5 abacaba aba a ac 1 7 1 3 2 7 2 5 4 5 ``` 输出： ``` 7 3 5 3 1 ``` 注意： - 在第一个例子中，第一个查询要求计算整个字符串t中有多少个子串包含在集合中。子串[1, 3]和[4, 6]与字符串"aba"匹配，子串[1, 1]、[3, 3]、[5, 5]和[7, 7]与字符串"a"匹配，子串[3, 4]与字符串"ac"匹配。总共，字符串"abacaba"有7个子串与集合中的字符串匹配。 - 在第二个查询中，取源字符串从位置1到位置3的子串，即字符串"aba"。字符串"aba"在其中出现1次，字符串"a"出现2次，字符串"ac"没有出现。在第三个查询中，取源字符串从位置2到位置7的子串，即字符串"bacaba"。字符串"aba"在其中出现1次，字符串"a"出现3次，字符串"ac"出现1次。