Background

You need to compare some serial numbers.

Problem Description

There are $M$ short serial numbers consisting of digits $0$ to $9$, and one long serial number of length $N$.

The process of checking whether serial number $A$ contains a serial number $B$ of length $L$ is as follows:

• Compare $A$ with $B$ digit by digit from positions $1$ to $L$. Once a mismatch is found, shift the whole search window one position to the right. If they are confirmed equal, stop comparing.

• Shifting the search window means moving the search range from $x$ to $y$ to $x+1$ and $y+1$.

• If the remaining digits are not enough for comparison, pad the end of the string with #. For example, for the string 563232, padding from position $4$ to $10$ becomes 232####.

• If all windows have been tried and none matches, stop comparing.

For each short serial number, output the number of comparisons made before the comparison process stops.

Input Format

The first line contains a positive integer $N$.

The second line contains a long serial number of length $N$.

The third line contains a positive integer $M$.

The next $M$ lines each contain a short serial number of length at most $10^5$.

The total length of all short serial numbers does not exceed $3\times 10^6$.

Output Format

Output $M$ integers. The $i$-th integer is the number of comparisons needed for the $i$-th short serial number.

7
1090901
4
87650
0901
109
090 

7
10
3
4

10
5821052680
4
210526
2105
582
105268

8
6
3
9

3
001
1
11

4

Hint

Constraints

• For $20\%$ of the testdata, $1\le N\le 10^3$, $1\le M\le 500$, and the length of every short serial number is at most $10^3$.
• For $100\%$ of the testdata, $1\le N\le 10^5$ and $1\le M\le 5\times 10^4$.
• For any character $c$ in any serial number, $c\in\{0,1,2,3,4,5,6,7,8,9 \}$.

Sample Explanation

Sample 1 Explanation

The first serial number:

• The robot looks for the first different digit in each window, making a total of $7$ comparisons.

The second serial number:

• Try the first position, immediately finds a mismatch: $1$ comparison.
• Try the second position, finds a mismatch at the fourth digit: $4$ comparisons.
• Try the third position, immediately finds a mismatch: $1$ comparison.
• Try the fourth position, finds a match: $4$ comparisons.
• Total: $10$ comparisons.

The third serial number:

• Immediately finds a match, total $3$ comparisons.

The fourth serial number:

• Finds a match at the second position, total $1+3=4$ comparisons.

Sample 3 Explanation

Compare serial number 11 with window 00 in order: $1$ comparison, then 01: $1$ comparison, and 1#: $2$ comparisons, for a total of $4$ comparisons.

Notes

This problem is translated from COCI2013-2014 CONTEST #1 T6 SLASTIČAR.

Translated by ChatGPT 5