Bessie ajuda Elsie a preparar seu teste de vocabulário. As palavras vêm de um banco de $M$ palavras distintas, nenhuma sendo prefixo de outra palavra do banco.

Enquanto o banco não estiver vazio, Bessie escolhe uma palavra, remove-a e a lê caractere por caractere da esquerda para a direita. Elsie avisa assim que puder identificá-la unicamente, e Bessie para de ler.

A ordem já é $w_1,w_2,\dots,w_M$. Se Elsie responder o mais rápido possível, quantos caracteres de cada palavra Bessie lerá?

As palavras são dadas em formato comprimido. Definimos primeiro $N+1$ ($1\le N\le 10^6$) palavras distintas; o banco contém todas as que não são prefixo de outra. A definição é:

• Inicialmente, a palavra $0$ é a string vazia.
• Para cada $1\le i\le N$, a palavra $i$ é a palavra $p_i$ com um caractere acrescentado ao final ($0\le p_i<i$). Os caracteres são escolhidos para que todas as $N+1$ palavras sejam distintas.

Entrada

A primeira linha contém $N$, onde $N+1$ é a quantidade de palavras comprimidas.

A próxima contém $p_1,p_2,\dots,p_N$; $p_i$ indica que a palavra $i$ é formada acrescentando um caractere ao final da palavra $p_i$.

Seja $M$ a quantidade de palavras que não são prefixo de outra. As próximas $M$ linhas contêm $w_1,w_2,\dots,w_M$: a palavra $w_i$ é a $i$-ésima a ser lida. A ordem forma uma permutação das palavras do banco.

Saída

Imprima $M$ linhas; a linha $i$ contém a quantidade de caracteres lidos da palavra $i$ na ordem de leitura.

Exemplos

Entrada 1

5
0 1 2 3 4
5

Saída 1

0

Nota

Há $6$ palavras numeradas $0\dots 5$. Apenas $5$ não é prefixo de outra, então é a única no banco. Em geral, quando só resta uma palavra, Elsie não precisa de caracteres para identificá-la.

Entrada 2

4
0 0 1 1
4
3
2

Saída 2

2
1
0

Nota

O banco contém as palavras $2$, $3$ e $4$.

Elsie precisa de dois caracteres para identificar $4$, pois $3$ e $4$ compartilham o primeiro.

Quando Bessie lê o primeiro caractere de $3$, Elsie já a identifica, pois $4$ já foi lida.

Entrada 3

4
0 0 1 1
2
3
4

Saída 3

1
2
0

Subtarefas

• Entradas quatro a cinco: nenhuma palavra tem comprimento maior que $20$.
• Entradas seis a dez: a soma dos comprimentos das palavras do banco não ultrapassa $10^7$.
• Entradas onze a dezoito: sem restrições adicionais.

Autor do problema: Benjamin Qi