0~9까지의 숫자로 이루어진 암호 A, B가 있다. 태민이는 암호 A에 암호 B가 포함되어 있는지 구하는 프로그램을 만들었다. 태민이의 프로그램이 답을 구하는 방식은 다음과 같다.

1) A의 길이 N, B의 길이 L을 구한다.
2) A의 1~L번째 수와 B의 1~L번째 수를 순서대로 비교한다. 만약 틀린 곳이 있다면 비교를 멈추고 다음 단계로 넘어간다.
3) 마찬가지로 A의 2~L+1번째, 3~L+2번째, …, N~N+L-1번째 수와 B를 비교한다. 이 때, A의 N+1번째 수부터는 편의상 -1이라고 하자.
4) 만약 비교하다가 틀린 곳이 없다면 프로그램을 끝낸다.

당신은 태민이의 프로그램이 비효율적이라는 것을 알려주기 위해 각 A, B에 대해 비교 횟수를 구해서 알려주려고 한다. 비교 횟수를 구하는 프로그램을 작성하여라.

입력 형식

• 첫 번째 줄에는 A의 길이 N이 주어진다. (1 ≤ N ≤ 100,000)
• 두 번째 줄에는 A가 주어진다.
• 세 번째 줄에는 테스트 케이스의 수 M이 주어진다. (1 ≤ M ≤ 50,000)
• 네 번째 줄부터 M개의 줄에는 B가 주어진다. B의 길이는 100,000 이하이며, B의 길이의 합은 3,000,000을 넘지 않는다.

출력 형식

입출력 예

입력 예 1

7
1090901
4
87650
0901
109
090

출력 예 1

7
10
3
4

입력 예 2

10
5821052680
4
210526
2105
582
105268

출력 예 2

8
6
3
9

입력 예 3

3
001
1
11

출력 예 3

4

A new directive specifies M banned ingredients which cannot appear in food even in trace amounts. Each ingredient has a serial number consisting of digits 0 through 9. The declaration on each food package lists all the serial numbers of ingredients contained in the respective food item.

Mirko must check whether any of his products has a banned ingredient serial number listed on its declaration. However, Mirko, being inept and reckless as always, decided to concatenate all the serial numbers into one long number with length N believing that it will make his job easier. He has borrowed a robot from his friend Slavko. The robot is programmed to check whether a serial number A contains another serial number B as a substring. Let us denote the length of B by L. The robot carries out search as follows:

• First, it compares the segment of A from position 1 to position L, digit by digit, with the digits in B. Comparison is stopped when a differing digit is found or when the segments are determined to be equal. If the segments are equal, the search is stopped and the match reported.
• If the segments are not equal, the procedure above is repeated with the segment from 2 to L+1. If those segments aren't equal either, the search continues with segments 3 to L+2, 4 to L+3 etc.
• If the robot doesn't have a sufficient number of digits to obtain a full segment of length L (for example, starting at character 5 in a serial number with length 8, a segment with length 6 is needed), it will pad the number with '#' signs. For example, the segment of "563232" from position 4 to position 10 is "232####".
• If the robot reaches the end of the serial number (having tried out all N segments) without having found B, the absence of match is reported.

Help Mirko determine how much money he'll have to pay Slavko for pattern matching!

입력

• The first line of input contains the positive integer N (1 ≤ N ≤ 100 000), the length of the long serial number.
• The second line of input contains N digits from 0 to 9, the long serial number.
• The third line of input contains the positive integer M (1 ≤ M ≤ 50 000), the number of banned ingeredients.
• Each of the following M rows contains a single banned serial number, A banned serial number will not exceed 100 000 digits in length. The total length of all banned serial numbers will not exceed 3 000 000 digits.

출력

입출력 예

input

7 
1090901 
4 
87650 
0901 
109 
090 

output

7 
10 
3 
4

input

10 
5821052680 
4 
210526 
2105 
582 
105268

output

8 
6 
3 
9

input

3 
001 
1 
11 

output

4 

Clarification of the first example:

First serial number: the robot finds differing first digits for every segment ? a total of 7 comparisons. 
Second serial number: tries first position, finding difference immediately (1 comparison). Tries second 
position, finding difference on the fourth digit (4 comparisons). Tries third position, finding difference 
immediately (1 comparison).Tries fourth position, finding a match (4 comparisons). Total: 10 
comparisons. 
Third serial number: finds match immediately (3 comparisons). 
Fourth serial number: finds match at second position (1 + 3 = 4 comparisons).
Clarification of the third example:
The robot compares the serial number '11' in order with segments '00' (1 comparison), '01' (1 
comparison) and '1#' (2 comparisons). Total: 4 comparisons. 

출처:coci/2013-2014/contest1
번역:functional