Bessie pomaga Elsie przygotować się do sprawdzianu słownictwa. Słowa pochodzą z banku $M$ różnych słów, z których żadne nie jest prefiksem innego słowa banku.

Dopóki bank nie jest pusty, Bessie wybiera słowo, usuwa je i czyta Elsie po jednym znaku od lewej do prawej. Elsie informuje ją, gdy tylko potrafi jednoznacznie rozpoznać słowo; wtedy Bessie przestaje.

Kolejność to już $w_1,w_2,\dots,w_M$. Jeśli Elsie odpowiada jak najszybciej, ile znaków każdego słowa przeczyta Bessie?

Słowa są podane w postaci skompresowanej. Najpierw określamy $N+1$ ($1\le N\le 10^6$) różnych słów; bank obejmuje wszystkie, które nie są prefiksem innego. Definicja jest następująca:

• Początkowo słowo $0$ jest pustym napisem.
• Dla każdego $1\le i\le N$ słowo $i$ powstaje przez dodanie znaku na końcu słowa $p_i$ ($0\le p_i<i$). Znaki dobrano tak, aby wszystkie $N+1$ słów były różne.

Wejście

Pierwszy wiersz zawiera $N$, gdzie $N+1$ jest liczbą skompresowanych słów.

Następny zawiera $p_1,p_2,\dots,p_N$; $p_i$ oznacza, że słowo $i$ powstaje przez dodanie znaku do końca słowa $p_i$.

Niech $M$ będzie liczbą słów niebędących prefiksem innych. Następne $M$ wierszy zawiera $w_1,w_2,\dots,w_M$: słowo $w_i$ zostanie przeczytane jako $i$-te. Kolejność jest permutacją słów banku.

Wyjście

Wypisz $M$ wierszy; wiersz $i$ zawiera liczbę przeczytanych znaków $i$-tego słowa w kolejności czytania.

Przykład

Wejście 1

5
0 1 2 3 4
5

Wyjście 1

0

Uwagi

Jest $6$ słów o numerach $0\dots 5$. Tylko $5$ nie jest prefiksem innego, więc tylko ono jest w banku. Gdy pozostaje jedno słowo, Elsie nie potrzebuje żadnego znaku, by je rozpoznać.

Wejście 2

4
0 0 1 1
4
3
2

Wyjście 2

2
1
0

Uwagi

Bank obejmuje słowa $2$, $3$ i $4$.

Elsie potrzebuje dwóch znaków dla $4$, ponieważ $3$ i $4$ mają wspólny pierwszy znak.

Po przeczytaniu pierwszego znaku $3$ Elsie je rozpoznaje, ponieważ $4$ już przeczytano.

Wejście 3

4
0 0 1 1
2
3
4

Wyjście 3

1
2
0

Podzadania

• Wejścia od czwartego do piątego: żadne słowo nie jest dłuższe niż $20$.
• Wejścia od szóstego do dziesiątego: suma długości słów banku nie przekracza $10^7$.
• Wejścia od jedenastego do osiemnastego: brak dodatkowych ograniczeń.

Autor zadania: Benjamin Qi