题目描述

我们称一个字母是 允许的，如果它是小写拉丁字母，并且是前 $k$ 个字母之一（即 'a' 到第 $k$ 个字母）。

现在你得到了一个字符串 $s$，它长度为 $n$，且仅由 允许的字母 组成。

如果一个字符串 $t$ 是 $s$ 的子序列，我们称它是 pleasant（令人愉快的）。

你还得到了 $q$ 个字符串 $t_1, t_2, ..., t_q$（也都只包含允许字母）。你的任务是：对每个 $t_i$，计算你最少需要往它 右边添加多少个允许字母，才能让它变成 unpleasant（不再是 s 的子序列）。

子序列指的是：可以通过删除若干个（可能是0个）元素，得到的子串。

输入格式

第一行两个整数 $n, k$（$1 \le n \le 10^6$, $1 \le k \le 26$）表示字符串 $s$ 的长度以及允许的字母数量；

第二行一个字符串 $s$，只包含前 $k$ 个小写字母；

第三行一个整数 $q$（$1 \le q \le 2 \cdot 10^5$）表示查询数；

接下来的 $q$ 行每行一个字符串 $t_i$（每个只包含允许字母）；

输入额外保证：所有 $t_i$ 总长度不超过 $10^6$。

输出格式

对每个查询输出一行，一个整数，表示要在 $t_i$ 后面最少加多少个字母才能让它变得 unpleasant。

样例

7 3
abacaba
3
cc
bcb
b

0
1
2

5 1
aaaaa
6
a
aa
aaa
aaaa
aaaaa
aaaaaa

5
4
3
2
1
0

提示

在第一个例子中

1. cc 这个字符串已经很难听了，所以不需要再添加任何内容；
2. bcb 是令人愉快的字符串，因此至少需要在右边添加一个字母：bcba 不行，但 bcbb 和 bcbc 都令人不愉快。
3. 由于 ba、bb 和 bc 都是令人愉快的字母，所以在 b 后面至少要加上两个字母。例如，我们可以得到一个令人不愉快的字符串 bbb。