Bessie는 Elsie의 다가오는 어휘 퀴즈를 돕습니다. 출제 단어는 서로 다른 $M$개 단어의 목록에서 가져오며, 어느 단어도 목록의 다른 단어의 접두사가 아닙니다.

목록이 비어 있지 않은 동안 Bessie는 단어를 골라 삭제하고 왼쪽부터 한 글자씩 읽습니다. Elsie는 단어를 유일하게 알아낼 수 있게 되면 알려야 하며, 그러면 Bessie는 읽기를 멈춥니다.

읽는 순서는 이미 $w_1,w_2,\dots,w_M$입니다. Elsie가 최대한 빨리 답하면 Bessie는 각 단어의 몇 글자를 읽습니까?

단어는 압축 형식으로 주어집니다. 먼저 서로 다른 $N+1$개($1\le N\le 10^6$) 단어를 정의하고, 다른 단어의 접두사가 아닌 모든 단어가 목록을 구성합니다. 정의는 다음과 같습니다.

• 처음에 $0$번째 단어는 빈 문자열입니다.
• 각 $1\le i\le N$에 대해 $i$번째 단어는 $p_i$번째 단어 끝에 한 글자를 붙인 것입니다($0\le p_i<i$). 모든 $N+1$개 단어가 서로 다르도록 글자를 고릅니다.

입력

첫 줄은 $N$이며 $N+1$이 압축 형식의 단어 수입니다.

다음 줄은 $p_1,p_2,\dots,p_N$입니다. $p_i$는 $i$번째 단어를 $p_i$번째 단어 끝에 한 글자를 붙여 만든다는 뜻입니다.

다른 단어의 접두사가 아닌 단어 수를 $M$이라 합니다. 다음 $M$개 줄은 $w_1,w_2,\dots,w_M$이며 $w_i$번째 단어를 $i$번째로 읽는다는 뜻입니다. 읽는 순서는 목록 단어들의 순열이라고 보장됩니다.

출력

$M$개의 줄을 출력하세요. $i$번째 줄은 읽는 순서의 $i$번째 단어에서 읽는 글자 수입니다.

예제

입력 1

5
0 1 2 3 4
5

출력 1

0

참고

$0\dots 5$로 번호 매겨진 $6$개 단어가 있습니다. $5$만 다른 단어의 접두사가 아니어서 목록에 혼자 있습니다. 일반적으로 단어가 하나만 남으면 Elsie는 글자를 듣지 않아도 알아냅니다.

입력 2

4
0 0 1 1
4
3
2

출력 2

2
1
0

참고

목록은 단어 $2$, $3$, $4$입니다.

$3$과 $4$의 첫 글자가 같아서 $4$를 알아내려면 두 글자가 필요합니다.

$4$는 이미 읽었으므로 Bessie가 $3$의 첫 글자를 읽으면 Elsie는 유일하게 알아냅니다.

입력 3

4
0 0 1 1
2
3
4

출력 3

1
2
0

서브태스크

• 입력 넷부터 다섯까지: 길이가 $20$보다 큰 단어가 없습니다.
• 입력 여섯부터 열까지: 목록의 모든 단어 길이의 합은 $10^7$ 이하입니다.
• 입력 열하나부터 열여덟까지: 추가 제약 없음.

문제 작성자: Benjamin Qi