我们定义字符串 $t$ 在字符串 $s$ 中的一个“相容出现集合”为 $t$ 在 $s$ 中出现位置的一个集合，使得其中任意两个出现位置互不重叠（换句话说，$s$ 中的任何一个字符位置不能同时属于两个不同的出现位置）。

给定一个由 $n$ 个小写英文字母组成的字符串 $s$ 以及 $m$ 次查询。每次查询包含一个字符串 $t_i$。

对于每次查询，请输出 $t_i$ 在 $s$ 中的相容出现集合的最大大小。

输入格式

第一行包含两个由空格分隔的整数 $n$ 和 $m$：字符串 $s$ 的长度和查询次数（$1 \le n \le 10^5, 1 \le m \le 10^5$）。

第二行包含字符串 $s$，由 $n$ 个小写英文字母组成。

接下来的 $m$ 行，每行包含一个由小写英文字母组成的字符串 $t_i$：第 $i$ 次查询（$1 \le |t_i| \le n$，其中 $|t_i|$ 是字符串 $t_i$ 的长度）。

保证所有 $t_i$ 的长度之和不超过 $10^5$。

输出格式

对于每次查询 $i$，在单独的一行中输出一个整数：$t_i$ 在 $s$ 中的相容出现集合的最大大小。

样例

样例输入 1

6 4
aaaaaa
a
aa
aaa
aaaa

样例输出 1

6
3
2
1