恭喜你！你被霍格沃茨录取了！作为新生的标准配置，你配备了一本包含所有基础咒语的词典。

实际上，所有基础咒语的词典 $S$ 是一个长度为 $n$ 的由小写拉丁字母组成的字符串。现在我们定义一个由 $m$ 个小写拉丁字母组成的咒语 $A$ 的魔力值如下：

$$\sum_{i=1}^{n} \text{lcp}(\text{suf}_i(S), A)$$

其中 $\text{suf}_i(S)$ 表示 $S$ 长度为 $i$ 的后缀，$\text{lcp}(X, Y)$ 表示 $X$ 和 $Y$ 的最长公共前缀的长度。

今天，菲利乌斯·弗立维教授（Professor Filius Flitwick）将对你进行一次快速测试。他会问你 $q$ 个问题。在第 $i$ 个问题中，你会得到一个咒语 $T_i$，你只需要回答 $T_i$ 的魔力值。现在，是时候迈出成为最伟大巫师的第一步了！

输入格式

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 3 \times 10^5$），分别表示 $S$ 的长度和问题数量。

第二行包含一个字符串 $S$。

接下来的 $q$ 行，每行包含一个字符串 $T_i$。保证 $\sum_{i=1}^{q} |T_i| \le 3 \times 10^5$。

输出格式

对于每个问题，输出一行，包含该问题的答案。

样例

输入样例 1

13 2
magicialspell
magic
magician

输出样例 1

5
7