题目描述

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

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

1. $ |a| = |b| $；
2. 对于所有 $ a_i \neq b_i $ 以及 $ a_j \neq b_j $，满足 $ |i-j| < k $。

如果 $ |a| = |b| \le k $，那么认为 $ a = b $。

输入格式

第一行一个整数 $ k $。

第二行一个字符串 $ s $。

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

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

输出格式

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

样例

input

1
xyz
3
xz
y
xzy

output

2
3
0

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

对于 $ p_2 $，$ y = x, y = y, y = z $，同理。

对于 $ p_3 $，$ xzy \neq xyz $，最大差 $ = 1 $ 不满足 $ < k = 1 $。

数据范围与提示

对于 $ 20\% $ 的数据，$ |s|, \sum |p_i| \le 10^3 $；
对于另外 $ 20\% $ 的数据，$ n \le 100 $；
对于另外 $ 20\% $ 的数据，$ |s|, \sum |p_i| \le 5 \cdot 10^4 $；
对于 $ 100\% $ 的数据，$ |s|, \sum |p_i| \le 2 \cdot 10^5 $。