焚书——即毁灭被当时统治集团视为不良的书籍——在捷克地区，直到现代仍然是一些受过部分教育的学者的最爱消遣。而那时微积分已经为人所知，牛顿的万有引力定律已经确立，地球的大部分也已被绘制成地图。

我们发现了一些记录，表明为了获得更大的戏剧效果，这种焚烧有时由几位焚书者共同进行——一位资深焚书者和几位初级焚书者。资深焚书者将书排成一排，并在每本书上标记一个拉丁小写字母。然后，每位初级焚书者都会收到一个所谓的“神圣咒语”——一个拉丁单词，或者更常见的是一串连续写下的简短拉丁字母序列。

然后，每位初级焚书者从头到尾对这排书进行一次扫描。每当他遇到连续的几本书，其上的标记与他的咒语相匹配时，他就大声念一次咒语，将这些书从这排书中抽出来，扔进熊熊燃烧的篝火中。书上的字母序列必须与焚书者咒语中的字母顺序完全一致。在移除了这样一组书之后，焚书者继续沿着这排书往前走，以同样的方式移除并焚烧他的咒语的每一次后续出现。

在扫描过程中，焚书者不允许后退，也不允许在移除书籍以外的时刻念出咒语。当他的轮次结束时，这排书中剩余的书会被合拢，从而保持它们的顺序，但不留空隙。

随着书籍逐渐消失，可能会出现某个焚书者根本找不到与他的咒语匹配的序列的情况——然而，这并不影响仪式的进行。

最重要的是每位初级焚书者念了多少次咒语，这取决于初级焚书者在准备好的书排前轮流进行的顺序。

历史记录为我们提供了排好准备焚烧的书籍上的字母序列、初级焚书者的咒语，以及他们接近这排书的顺序。为了重现当时的气氛，我们希望确定每位初级焚书者念了多少次他的咒语。

输入格式

第一行输入包含两个整数 $N, Q$ ($1 \le N \le 10^5, 1 \le Q \le 4 \cdot 10^5$)，表示书排中的书籍数量和初级焚书者的数量。

第二行包含一个由 $N$ 个小写字母组成的字符串 $s$，表示书排中书籍上的标记，按它们在书排中出现的顺序给出。

接下来的 $2Q$ 行包含 $Q$ 个询问。每个询问占用两行。

询问的第一行包含一个整数 $N_i$ ($1 \le N_i \le 5$)，表示第 $i$ 个初级焚书者咒语的字母数量。

询问的第二行包含一个由 $N_i$ 个小写字母组成的字符串 $s_i$，即第 $i$ 个初级焚书者的咒语。

输出格式

输出 $Q$ 行，每行回答对应的询问——第 $i$ 行指定第 $i$ 个初级焚书者念了多少次咒语。

样例

输入样例 1

6 5
banana
3
ana
3
ban
2
na
1
b
5
apple

输出样例 1

1
0
1
1
0

输入样例 2

12 5
ccccatatatat
3
cat
3
cat
3
cat
3
cat
3
cat

输出样例 2

1
1
1
1
0