题目描述

神说，要有字符串，于是便有了一个小写字母串 $s$，$s_i$ 表示 $s$ 的第 $i$ 个字符。

神说，要有匹配，于是定义字符串 $a$，$b$ 是匹配的当且仅当 $|a| = |b|$ 且对于任意 $1 \leq i \leq |a|$，有 $a_i = b_i$。

神说，要宽容，于是有了一个参数 $k$，并定义字符串 $a$，$b$ 是模糊匹配的当且仅当 $|a| = |b|$ 且对于任意 $1 \leq i$，$j \leq |a|$，$a_i \neq b_i$ 均有 $|i−j|< k$。

神说，要善于观察，于是提出了询问：给定小写字母串 $p$，求 $s$ 有多少个连续子串和 $p$ 是模糊匹配的。

神说，要经得起考验，于是提出了 $q$ 个询问。

这个神圣的任务就交给你了。

输入格式

第一行输入正整数 $k$，第二行输入字符串 $s$，第三行输入非负整数 $q$。

接下来 $q$ 行每行一个字符串 $p_i$。

保证字符串只包含小写字母。

输出格式

输出 $q$ 行，每行一个非负整数，表示该次询问的答案。

样例输入 1

2
baccbcbabc
7
a
abc
aaa
bbb
abbb
acbbc
iamasuperlongstring

样例输出 1

10
4
3
4
1
1
0

样例 2，3

大样例

测试点约束

设 $u =\sum_{i=1}^n|p_i|$。 对于所有测试点，$1 ≤ |s|$, $u$, $n$, $k \leq 2 \times 10^5$。

本题采 用捆绑评测 ，你只有通过一个子任务中所有测试点才能得到该子任务的分数。

每个子任务的具体限制见下表：