문자열과 쿼리

길이가 $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)$를 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.