Problem Background

You need to compare some serial numbers.

Problem Description

Given \( M \) short serial numbers consisting of digits from \( 0 \) to \( 9 \), and a long serial number of length \( N \).

The process to check if a serial number \( A \) contains a serial number \( B \) of length \( L \) is as follows:

• Compare \( A \) from position \( 1 \) to \( L \) with \( B \) bit by bit. If a difference is found, shift the search segment as a whole. If it is determined to be equal, stop the comparison.
• Shifting the search segment means moving the search area from \( x \) to \( y \) to \( x+1 \) and \( y+1 \).
• If there are not enough digits left for comparison, fill the string with # at the end. For example, for the string 563232, filling from position \( 4 \) to \( 10 \) results in 232####.
• If no segments match after all attempts, stop the comparison.

For each short serial number, output the number of comparisons made before stopping.

Input Format

The first line of input is a positive integer \( N \).

The second line is 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 with a length not exceeding \( 10^5 \).

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

Output Format

Output \( M \) integers, representing the number of comparisons required for each short serial number.

Sample Input and Output

Sample Input #1

7
1090901
4
87650
0901
109
090

Sample Output #1

7
10
3
4

Sample Input #2

10
5821052680
4
210526
2105
582
105268

Sample Output #2

8
6
3
9

Sample Input #3

3
001
1
11

Sample Output #3

4

Notes

Data Range and Constraints

• For \( 20\% \) of the data, \( 1 \le N \le 10^3 \), \( 1 \le M \le 500 \), and the length of any short serial number does not exceed \( 10^3 \).
• For \( 100\% \) of the data, \( 1 \le N \le 10^5 \), \( 1 \le M \le 5 \times 10^4 \).
• For any character \( c \) in the serial numbers, \( c \in \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\} \).

Sample Explanation

Sample 1 Explanation

First serial number:
- The robot finds the first different digit for each segment, totaling \( 7 \) comparisons.

Second serial number:
- Attempt at the first position, immediately finds a difference, \( 1 \) comparison.
- Attempt at the second position, finds a difference at the fourth digit, \( 4 \) comparisons.
- Attempt at the third position, immediately finds a difference, \( 1 \) comparison.
- Attempt at the fourth position, finds a match, \( 4 \) comparisons.
- Total \( 10 \) comparisons.

Third serial number:
- Immediately finds a match, totaling \( 3 \) comparisons.

Fourth serial number:
- Finds a match at the second position, totaling \( 1 + 3 = 4 \) comparisons.

Sample 3 Explanation

Sequentially compare the serial number 11 with segments 00, \( 1 \) comparison, 01, \( 1 \) comparison, and 1#, \( 2 \) comparisons, totaling \( 4 \) comparisons.

见题面 Input 部分

见题面 Output 部分