SOLVE
LATER
Given a string s and a set of n strings \(p_i\).
For each i find the number of occurrences of \(p_i\) in s with at most one k-length gap.
The string s occurs in string t at position p with at most one k-length gap if strings s and \(t_pt_{p+1}\ldots t_{p+|s|-1}\) are equal with at most one k-length gap.
Strings s and r are equal with at most one k-length gap if:
Input format
First line of input contains single integer k (\(1 \leq k \leq 2 \cdot 10^5\)).
Second line of input contains string s (\(1 \leq |s| \leq 2 \cdot 10^5\)).
Third line contains an integer n (\(1 \leq n \leq 2 \cdot 10^5\)).
Then follow n lines. The i-th of them contains string \(p_i\) (\(\sum\limits_{i=1}^{n} |p_{i}| \leq 2 \cdot 10^5\)).
s and \(p_i\) can contain characters with codes from \(33\) to \(126\), inclusive.
Output format
Print n lines. The i-th of them should contain the number of occurrences \(p_i\) in s with at most one k-length gap.