题目描述

菲利普非常喜欢解决与字符串相关的问题。他已经解决了所有他知道的字符串问题，但仍觉得不够。于是，菲利普决定自己设计一个新的字符串问题。

为此，他选取了一个字符串 $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$ 的位置对 $(a, b)$ 数量，其中 $t$ 从第 $a$ 个到第 $b$ 个字符的子串与集合中的某个字符串 $s_j$ 完全一致。

字符串 $t$ 从第 $a$ 个到第 $b$ 个字符的子串是指通过删除 $t$ 的前 $a-1$ 个字符和后 $|t|-b$ 个字符得到的字符串，其中 $|t|$ 表示字符串 $t$ 的长度。

菲利普已经解决了这个问题，你能解决吗？

输入格式

第一行包含两个正整数 $n$ 和 $m$ $(1 \le n, m \le 500000)$，分别表示集合中的字符串数量和查询数量。

第二行包含一个字符串 $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$ 个查询的答案。

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

7 3 5 3 1

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

2 0 2 3

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。