题目描述

焚书——销毁被当时统治集团视为不受欢迎的书籍——直到近代仍是捷克地区某些学识不高的学者喜爱的活动。那时微积分已经出现，牛顿万有引力定律已经建立，地球的大部分区域也已经被绘制在地图上。

我们发现的史料表明，为了让焚书仪式更加富有戏剧效果，有时会由多名焚书者共同完成：其中一人是资深焚书者，其余几人是初级焚书者。

资深焚书者先把所有书排成一行，并在每本书上标记一个小写拉丁字母。随后，每名初级焚书者都会得到一句所谓的“神圣咒语”——一个拉丁单词，或者更常见地说，一小段连续的小写拉丁字母。

每名初级焚书者轮到时，会从书列开头到末尾进行恰好一次扫描。

当他遇到若干本连续的书，其字母序列与自己的咒语完全相同时，他会：

1. 念出一次咒语；
2. 将这些书从书列中抽出并扔进火堆；
3. 继续向书列后方扫描。

在同一轮扫描中，他不能向后退，也不能在没有移除书籍时念出咒语。因此，对于相互重叠的多个出现位置，只会按照从左到右的扫描过程删除能够实际遇到的那些出现。

当这一名焚书者的回合结束后，剩余书籍会保持原相对顺序并向中间合拢，使书列中不再存在空隙。

随着书籍逐渐减少，某名焚书者可能一次也找不到自己的咒语；这不会影响仪式继续进行。

我们已知：

• 最初书列上的字母串；
• 每名初级焚书者的咒语；
• 这些焚书者依次行动的顺序。

请计算每名初级焚书者在自己的回合中一共念出了多少次咒语。

输入格式

第一行包含两个整数 $N,Q$（$1\le N\le 10^5$，$1\le Q\le 4\times 10^5$），分别表示初始书籍数量和初级焚书者数量。

第二行包含一个长度为 $N$ 的小写字母串 $s$，表示从左到右每本书上的字母。

接下来共有 $2Q$ 行，依次描述 $Q$ 次询问。第 $i$ 次询问占两行：

• 第一行包含整数 $N_i$（$1\le N_i\le 5$），表示第 $i$ 名焚书者的咒语长度；
• 第二行包含一个长度为 $N_i$ 的小写字母串 $s_i$，表示他的咒语。

焚书者严格按照输入顺序行动；前一人的删除结果会影响后一人看到的书列。

输出格式

输出 $Q$ 行。

第 $i$ 行输出第 $i$ 名初级焚书者在自己的回合中念出咒语的次数。

样例 1

输入

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

输出

1
0
1
1
0

样例 2

输入

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

输出

1
1
1
1
0