[HAOI2017] 字符串

给出一个字符串 $ s $ 和 $ n $ 个字符串 $ p_i $，求每个字符串 $ p_i $ 在 $ s $ 中出现的次数。注意这里两个字符串相等的定义稍作改变。 给定一个常数 $ k $，对于两个字符串 $ a, b $，如果 $ a = b $，那么满足： 一、$ |a| = |b| $ 二、对于所有 $ 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 $ 中出现的次数。

1
xyz
3
xz
y
xzy

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|, \Sigma |p_i| \le 10^3 $ 对于另外 $ 20\% $ 的数据，满足：$ n \le 100 $ 对于另外 $ 20\% $ 的数据，满足：$ |s|, \Sigma |p_i| \le 5 \cdot 10^4 $ 对于 $ 100\% $ 的数据，满足：$ |s|, \Sigma |p_i| \le 2 \cdot 10^5 $