我们来写封信吧 允许 如果它是小写字母并且是拉丁字母表的前 $$$k$$$ 字母之一。
给您一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅包含允许的字母。
让我们调用一个字符串 $$$t$$$ 令人愉快 如果 $$$t$$$ 是 $$$s$$$ 的子序列。
给你 $$$q$$$ 字符串 $$$t_1, t_2, \dots, t_q$$$。所有这些都仅包含允许的字母。对于每个字符串 $$$t_i$$$,计算需要在右侧附加的允许字母的最小数量,以便它 停止 令人愉快。
序列 $$$t$$$ 是序列 $$$s$$$ 的子序列,如果 $$$t$$$ 可以通过从任意位置删除几个(可能是零个或全部)元素从 $$$s$$$ 获得。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 10^6$$$; $$$1 \le k \le 26$$$) — 字符串 $$$s$$$ 的长度和允许的字母数量。
第二行包含字符串 $$$s$$$,由 $$$n$$$ 小写拉丁字母组成。字符串的每个字符都是拉丁字母表中前 $$$k$$$ 字母之一。
第三行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 查询数。
接下来的 $$$q$$$ 行包含查询:每行一个查询。第 $$$i$$$ 行包含字符串 $$$t_i$$$,仅包含允许的字母。
对输入的附加限制:所有 $$$t_i$$$ 的总长度不超过 $$$10^6$$$。
输出
对于每个查询,输出一个整数——需要附加到右侧字符串中的允许字母的最小数量,这样它就不再令人愉快了。
示例
输入复制
7 3abacaba3ccbcbb
输出复制
0 1 2
输入复制
5 1aaaaa6aaaaaaaaaaaaaaaaaaaaa
输出复制
5 4 3 2 1 0
注意
在第一个示例中:
- 字符串 cc 已经令人不快了,所以不需要添加任何内容;
- BCB 令人愉快,因此至少需要在右侧添加一个字母: BCBA 不起作用,但是 bcbb 和 bcbc 令人不愉快。
- To b,至少需要附加两个字母,因为 ba, bb,和 bc 令人愉快。例如,我们可以获得一个令人不愉快的字符串 bbb.