题目描述

给定一个长度为 $n$ 的字符串 $S$，你需要回答 $q$ 个查询。

对于每个查询，给定一个字符串 $T$ 和一个整数 $a (1 \leq a \leq n - |T| + 1)$，你需要计算有多少个区间 $[u, v]$ ($1 \leq u \leq v \leq |T|$) 满足 $S_{a+x-1} = T_x$ 对每个 $x \in [u, v]$ 都成立，这些区间被称为对称区间。注意 $|T|$ 是字符串 $T$ 的长度。

输入格式

第一行包含两个整数 $n$ 和 $q (1 \leq n, q \leq 10^5)$，表示给定字符串 $S$ 的长度和查询的数量。

第二行包含长度为 $n$ 的给定字符串 $S$。

接下来的 $q$ 行每行包含一个字符串 $T (1 \leq |T| \leq n)$ 和一个整数 $a (1 \leq a \leq n - |T| + 1)$，表示一个查询。

保证 $|T|$ 的总和不超过 $10^6$，并且所有输入的字符串仅包含小写英文字母。

输出格式

对于每个查询，输出一行包含一个整数，表示对称区间的数量。

10 3
helloworld
follow 1
echo 2
nowgold 4

10
2
6

解释 #1

对于第一个查询，10 个对称区间是 $[3, 3] 、 [3, 4] 、 [3, 5] 、 [3, 6] 、 [4, 4] 、 [4, 5] 、 [4, 6] 、 [5, 5] 、 [5, 6]$ 和 $[6, 6]$。

对于第二个查询，2 个对称区间是 $[1, 1]$ 和 $[4, 4]$。

对于第三个查询，6 个对称区间是 $[2, 2] 、 [2, 3] 、 [3, 3] 、 [6, 6] 、 [6, 7]$ 和 $[7, 7]$。