A93255.「HAOI2017」字符串

给出一个字符串 $ 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 $ 中出现的次数。

对于 $ 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 $。