문자열과 쿼리

시간 제한2초메모리 제한512 MB

요약

문자열 S에서 F(i)를 S의 접미사이자 S의 i번째 문자까지의 접두사인 가장 긴 문자열의 길이로 정의하고, M개의 질의에 답한다.

문제

길이가 $N$ 인 문자열 $S = S_1 S_2 \cdots S_N$ 이 주어진다. 함수 $F(i)$ 는 $S$ 와 접두사 $S_1 S_2 \cdots S_i$ 의 가장 긴 공통 접미사의 길이다.

예를 들어 $S$ 가 zaaxbaacbaa이면 $F(1) = 0$ , $F(2) = 1$ , $F(3) = 2$ 이다.

문자열 $S$ 와 쿼리 $M$ 개가 주어졌을 때, 각 쿼리 $i$ 에 대해 $F(i)$ 를 구하는 프로그램을 작성한다.

첫째 줄에 문자열 $S$ 가 공백 없이 한 줄로 주어진다. $S$ 의 길이 $N$ 은 $1 \le N \le 10^6$ 이다.

둘째 줄에 쿼리의 개수 $M$ 이 주어진다. ( $1 \le M \le 10^5$ )

셋째 줄부터 $M$ 개의 줄에 각 쿼리의 정수 $i$ 가 한 줄에 하나씩 주어진다. ( $1 \le i \le N$ )

각 쿼리 $i$ 에 대해 $F(i)$ 를 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.

예제 1

입력

zaaxbaacbaa
11
1
2
3
4
5
6
7
8
9
10
11

예상 출력

예제 3

입력

aaaaaaaa
8
1
2
3
4
5
6
7
8

예상 출력

예제 4

입력

abcdefghij
10
1
2
3
4
5
6
7
8
9
10

예상 출력

예제 5

입력

abababababab
12
1
2
3
4
5
6
7
8
9
10
11
12

예상 출력

예제 6

입력

aabaabaabaa
10
11
1
7
7
2
5
5
11
3
8

예상 출력

예제 7

입력

mississippi
11
1
2
3
4
5
6
7
8
9
10
11

예상 출력