菲利普非常喜欢关于字符串的小问题。他已经解决了所有他知道的相关问题，但这对他来说还不够。因此，菲利普决定自己出一道题。

为此，他准备了一个字符串 $t$ 和一个包含 $n$ 个字符串的集合 $s_1, s_2, s_3, \dots, 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$ 互不相同。

接下来的 $m$ 行描述查询。第 $i$ 行包含两个正整数 $l_i$ 和 $r_i$ ($1 \le l_i \le r_i \le |t|$) —— 第 $i$ 次查询中 $t$ 的子串的左边界和右边界。

输出格式

输出一行，包含 $m$ 个整数，第 $i$ 个整数表示第 $i$ 次查询的答案。

样例

输入 1

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

输出 1

7 3 5 3 1

输入 2

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

输出 2

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 出现 0 次。

在第三个查询中，取原字符串中第 2 到第 7 个位置的子串，即字符串 bacaba。其中字符串 aba 出现 1 次，字符串 a 出现 3 次，字符串 ac 出现 1 次。

子任务

本题测试点共分为 9 个子任务。每个子任务的分数仅在通过该子任务的所有测试点以及某些指定的前置子任务的所有测试点后才能获得。Offline 测试意味着该子任务的测试结果将在比赛结束后公布。