当前没有测试数据。

【题目描述】

给出一个字符串 s 和 n 个字符串 pi，求每个字符串 pi 在 s 中出现的次数。注意这里两个字符串相等的定义稍作改变。

给定一个常数 k，对于两个字符串 a,b，如果 a=b，那么满足：

一、|a|=|b|

二、对于所有 ai≠bi 以及 aj≠bj，满足 |i−j|<k

如果|a|=|b|≤k，那么认为 a=b。

【输入格式】

第一行一个整数 k。

第二行一个字符串 s。

第三行一个整数 n，接下来 n 行每行一个字符串表示 pi。

所有的字符 ASCII 码在 33 至 126 之间。

【输出格式】

输出 n 行，表示每个 pi 在 s 中出现的次数。

【样例输入】

1
xyz
3
xz
y
xzy

【样例输出】

2
3
0

【样例解释】

对于 p1，xz=xy,xz=yz，因为都只有一个位置差异。

对于 p2，y=x,y=y,y=z，同理。

对于 p3，xzy≠xyz，最大差 =1 不满足 <k=1。

【提示】

对于 20% 的数据，满足：|s|,∑|pi|≤10^3

对于另外 20% 的数据，满足：n≤100

对于另外 20% 的数据，满足：|s|,∑|pi|≤ 5×10^4

对于 100% 的数据，满足：|s|,∑|pi|≤2×10^5