Suffix Matching Length Queries

Given two strings \(A\) and \(B\), consider all suffixes of \(A\). For each suffix, define its matching length as the length of the longest common prefix with \(B\). You are then given \(Q\) queries. In each query, an integer \(X\) is provided. Your task is to count how many suffixes of \(A\) have a matching length exactly equal to \(X\).

Note: For each suffix starting at position \(i\) in \(A\) (1-indexed), let \(L_i\) be the largest integer (possibly 0) such that \(A[i,i+L_i-1] = B[1,L_i]\) (if \(L_i > |B|\), consider \(L_i = |B|\)).

Example: Suppose \(A = \texttt{aabcde}\) and \(B = \texttt{ab}\). The suffixes of \(A\) are:

• \(aabcde\): matching length = 1
• \(abcde\): matching length = 2
• \(bcde\): matching length = 0
• \(cde\): matching length = 0
• \(de\): matching length = 0
• \(e\): matching length = 0

Thus, there are 4 suffixes with matching length 0, 1 suffix with matching length 1, and 1 suffix with matching length 2.

inputFormat

The input consists of multiple lines:

1. The first line contains a non-empty string \(A\).
2. The second line contains a non-empty string \(B\).
3. The third line contains an integer \(Q\) representing the number of queries.
4. Each of the next \(Q\) lines contains an integer \(X\) representing a query.

Both \(A\) and \(B\) consist of lowercase English letters.

outputFormat

For each query, output a single integer representing the number of suffixes of \(A\) whose matching length with \(B\) is exactly \(X\). Each answer should be printed on a new line.

sample

aabcde
ab
3
0
1
2

4
1
1