Description

Given a string $s$ and $n$ strings $p_i$, for each string $p_i$ count the number of its occurrences in $s$. Note that the definition of equality between two strings is slightly modified here.

Given a constant $k$, for two strings $a, b$, we define $a = b$ if the following hold:

1. $|a| = |b|$.
2. For all $a_i \ne b_i$ and $a_j \ne b_j$, it holds that $|i - j| < k$.

If $|a| = |b| \le k$, then we regard $a = b$.

Input Format

The first line contains an integer $k$.

The second line contains a string $s$.

The third line contains an integer $n$, followed by $n$ lines, each containing a string denoting $p_i$.

All characters have ASCII codes in the range $33$ to $126$.

Output Format

Output $n$ lines, where the $i$-th line is the number of occurrences of $p_i$ in $s$.

1
xyz
3
xz
y
xzy

2
3
0

Hint

For $p_1$, $xz = xy, xz = yz$, because there is only one differing position.

For $p_2$, $y = x, y = y, y = z$, similarly.

For $p_3$, $xzy \ne xyz$, the maximum difference $= 1$ does not satisfy $< k = 1$.

Constraints

• For $20\%$ of the testdata, it holds that: $|s|, \Sigma |p_i| \le 10^3$.
• For another $20\%$ of the testdata, it holds that: $n \le 100$.
• For another $20\%$ of the testdata, it holds that: $|s|, \Sigma |p_i| \le 5 \cdot 10^4$.
• For $100\%$ of the testdata, it holds that: $|s|, \Sigma |p_i| \le 2 \cdot 10^5$.

Translated by ChatGPT 5