Bessie aide Elsie à préparer son contrôle de vocabulaire. Les mots viennent d'une banque de $M$ mots distincts, dont aucun n'est préfixe d'un autre mot de la banque.

Tant que la banque n'est pas vide, Bessie choisit un mot, le retire et le lit caractère par caractère de gauche à droite. Elsie doit prévenir dès qu'elle peut l'identifier de manière unique ; Bessie cesse alors de lire.

L'ordre de lecture est déjà fixé à $w_1,w_2,\dots,w_M$. Si Elsie répond au plus vite, combien de caractères de chaque mot seront lus ?

Les mots sont donnés sous forme compressée. On définit d'abord $N+1$ ($1\le N\le 10^6$) mots distincts ; la banque contient tous ceux qui ne sont préfixes d'aucun autre. Voici leur définition :

• Au départ, le mot $0$ est la chaîne vide.
• Pour chaque $1\le i\le N$, le mot $i$ est le mot $p_i$ suivi d'un caractère supplémentaire ($0\le p_i<i$). Ces caractères garantissent que les $N+1$ mots sont distincts.

Entrée

La première ligne contient $N$, où $N+1$ est le nombre de mots compressés.

La suivante contient $p_1,p_2,\dots,p_N$ ; $p_i$ signifie que le mot $i$ est obtenu en ajoutant un caractère à la fin du mot $p_i$.

Soit $M$ le nombre de mots qui ne sont préfixes d'aucun autre. Les $M$ lignes suivantes contiennent $w_1,w_2,\dots,w_M$, indiquant que le mot $w_i$ sera lu en $i$-ème. Les mots à lire forment une permutation de la banque.

Sortie

Affichez $M$ lignes ; la $i$-ème donne le nombre de caractères lus du $i$-ème mot dans l'ordre de lecture.

Exemples

Entrée 1

5
0 1 2 3 4
5

Sortie 1

0

Remarque

Il y a $6$ mots numérotés $0\dots 5$. Seul le mot $5$ n'est préfixe d'aucun autre ; il est donc seul dans la banque. En général, quand un seul mot reste, aucun caractère n'est nécessaire pour l'identifier.

Entrée 2

4
0 0 1 1
4
3
2

Sortie 2

2
1
0

Remarque

La banque contient les mots $2$, $3$ et $4$.

Deux caractères sont nécessaires pour identifier le mot $4$, car $3$ et $4$ ont le même premier caractère.

Le premier caractère du mot $3$ suffit à l'identifier, puisque le mot $4$ a déjà été lu.

Entrée 3

4
0 0 1 1
2
3
4

Sortie 3

1
2
0

Sous-tâches

• Entrées quatre à cinq : aucun mot ne dépasse $20$ caractères.
• Entrées six à dix : la somme des longueurs des mots de la banque ne dépasse pas $10^7$.
• Entrées onze à dix-huit : aucune contrainte supplémentaire.

Auteur du problème : Benjamin Qi