Bessie ayuda a Elsie a preparar su examen de vocabulario. Las palabras vienen de un banco de $M$ palabras distintas, ninguna de las cuales es prefijo de otra palabra del banco.

Mientras el banco no esté vacío, Bessie elige una palabra, la elimina y la lee carácter por carácter de izquierda a derecha. Elsie debe avisar en cuanto pueda identificarla de forma única, y Bessie deja de leer.

Ya ha decidido el orden $w_1,w_2,\dots,w_M$. Si Elsie responde lo más rápido posible, ¿cuántos caracteres de cada palabra leerá Bessie?

Las palabras se dan comprimidas. Primero se definen $N+1$ ($1\le N\le 10^6$) palabras distintas; el banco contiene todas las que no son prefijo de otra. Se definen así:

• Inicialmente, la palabra $0$ es la cadena vacía.
• Para cada $1\le i\le N$, la palabra $i$ es la palabra $p_i$ con un carácter añadido al final ($0\le p_i<i$). Los caracteres hacen que las $N+1$ palabras sean distintas.

Entrada

La primera línea contiene $N$, donde $N+1$ es el número de palabras comprimidas.

La siguiente contiene $p_1,p_2,\dots,p_N$; $p_i$ indica que la palabra $i$ se obtiene añadiendo un carácter al final de la palabra $p_i$.

Sea $M$ el número de palabras que no son prefijo de otra. Las siguientes $M$ líneas contienen $w_1,w_2,\dots,w_M$: la palabra $w_i$ se lee en el lugar $i$. Se garantiza que el orden es una permutación de las palabras del banco.

Salida

Imprime $M$ líneas; la línea $i$ contiene el número de caracteres leídos de la palabra $i$ en el orden de lectura.

Ejemplos

Entrada 1

5
0 1 2 3 4
5

Salida 1

0

Nota

Hay $6$ palabras numeradas $0\dots 5$. Solo la palabra $5$ no es prefijo de otra, por lo que es la única del banco. En general, cuando queda una sola palabra, Elsie no necesita ningún carácter para identificarla.

Entrada 2

4
0 0 1 1
4
3
2

Salida 2

2
1
0

Nota

El banco contiene las palabras $2$, $3$ y $4$.

Para identificar $4$ hacen falta dos caracteres, porque $3$ y $4$ comparten el primero.

El primer carácter de $3$ basta para identificarla, pues $4$ ya fue leída.

Entrada 3

4
0 0 1 1
2
3
4

Salida 3

1
2
0

Subtareas

• Entradas cuatro a cinco: ninguna palabra mide más de $20$ caracteres.
• Entradas seis a diez: la suma de longitudes del banco no supera $10^7$.
• Entradas once a dieciocho: sin restricciones adicionales.

Autor del problema: Benjamin Qi