Bessie aiuta Elsie a preparare la prossima verifica di vocabolario. Le parole provengono da una raccolta di $M$ parole distinte, nessuna prefisso di un'altra della raccolta.

Finché la raccolta non è vuota, Bessie sceglie una parola, la rimuove e la legge carattere per carattere da sinistra a destra. Elsie avvisa appena può identificarla univocamente; allora Bessie smette.

L'ordine è già $w_1,w_2,\dots,w_M$. Se Elsie risponde il prima possibile, quanti caratteri di ogni parola leggerà Bessie?

Le parole sono date in forma compressa. Prima definiamo $N+1$ ($1\le N\le 10^6$) parole distinte; la raccolta contiene tutte quelle che non sono prefisso di un'altra. Si definiscono così:

• Inizialmente, la parola $0$ è la stringa vuota.
• Per ogni $1\le i\le N$, la parola $i$ è la parola $p_i$ con un carattere aggiunto alla fine ($0\le p_i<i$). I caratteri sono scelti perché tutte le $N+1$ parole siano distinte.

Input

La prima riga contiene $N$, dove $N+1$ è il numero di parole compresse.

La successiva contiene $p_1,p_2,\dots,p_N$; $p_i$ indica che la parola $i$ si ottiene aggiungendo un carattere alla fine della parola $p_i$.

Sia $M$ il numero di parole che non sono prefisso di un'altra. Le successive $M$ righe contengono $w_1,w_2,\dots,w_M$: la parola $w_i$ sarà la $i$-esima letta. L'ordine è una permutazione delle parole della raccolta.

Output

Stampa $M$ righe; la riga $i$ contiene il numero di caratteri letti della parola $i$ nell'ordine di lettura.

Esempi

Input 1

5
0 1 2 3 4
5

Output 1

0

Spiegazione

Ci sono $6$ parole numerate $0\dots 5$. Solo $5$ non è prefisso di un'altra, quindi è l'unica nella raccolta. In generale, quando rimane una sola parola, Elsie non necessita di caratteri per identificarla.

Input 2

4
0 0 1 1
4
3
2

Output 2

2
1
0

Spiegazione

La raccolta contiene le parole $2$, $3$ e $4$.

Elsie necessita di due caratteri per identificare $4$, perché $3$ e $4$ condividono il primo.

Quando Bessie legge il primo carattere di $3$, Elsie può identificarla, dato che $4$ è già stata letta.

Input 3

4
0 0 1 1
2
3
4

Output 3

1
2
0

Sottoproblemi

• Input da quattro a cinque: nessuna parola supera la lunghezza $20$.
• Input da sei a dieci: la somma delle lunghezze delle parole della raccolta non supera $10^7$.
• Input da undici a diciotto: nessun vincolo aggiuntivo.

Autore del problema: Benjamin Qi