Modified String Pattern Matching

Given a string \( s \) and \( n \) pattern strings \( p_i \), count the number of occurrences of each \( p_i \) in \( s \) based on a modified equality definition.

For two strings \( a \) and \( b \), and a given integer constant \( k \), we define \( a = b \) if the following conditions hold:

1. \( |a| = |b| \).
2. If \( |a| \le k \), then \( a \) and \( b \) are always considered equal. Otherwise, if \( |a| > k \), let \( D = \{ i \mid a_i \neq b_i \} \). If \( |D| \le 1 \) then \( a \) is considered equal to \( b \); if \(|D| \ge 2\), then \( a = b \) if and only if for every two indices \( i, j \) in \( D \) (with \( i \neq j \)), it holds that \( |i - j| < k \).

For each pattern string \( p_i \), count its occurrences as a substring in \( s \) where the equality of strings is determined by the above rules.

inputFormat

The input consists of the following lines:

• The first line contains the string \( s \).
• The second line contains an integer \( k \) – the constant used in the modified equality rule.
• The third line contains an integer \( n \) representing the number of pattern strings.
• Each of the next \( n \) lines contains a pattern string \( p_i \).

outputFormat

Output \( n \) lines, each line containing a single integer that is the number of occurrences of the corresponding pattern string \( p_i \) in \( s \) according to the modified equality definition.

sample

abcabc
2
2
abc
acb

2
2