Vocabulary Quiz

문제

Bessie is helping Elsie with her upcoming vocabulary quiz. The words to be tested will be drawn from a bank of $MM$ distinct words, where no word in the bank is a prefix of another word in the bank.

While the bank is nonempty, Bessie will select a word from the bank, remove it from the bank, and read it to Elsie one character at a time from left to right. Elsie's task is to tell Bessie once she can uniquely identify it, after which Bessie will stop reading.

Bessie has already decided to read the words from the word bank in the order $w_1,w_2,\dots ,w_{M}w\_1,w\_2,\backslash dots,w\_M$. If Elsie answers as quickly as possible, how many characters of each word will Bessie read?

The words are given in a compressed format. We will first define $N+1N+1$ ($1\le N\le {10}^{6}1\backslash le\; N\backslash le\; 10^6$) distinct words, and then the word bank will consist of all those words that are not a prefix of another word. The words are defined as follows:

• Initially, the $00$th word will be the empty string.
• Then for each $1\le i\le N1\backslash le\; i\backslash le\; N$, the $ii$th word will be equal to the $p_{i}p\_i$th word plus an additional character at the end (). The characters are chosen such that all $N+1N+1$ words are distinct.

입력

The first line contains $NN$, where $N+1N+1$ is the number of words given in the compressed format.

The next line contains $p_1,p_2,\dots ,p_{N}p\_1,p\_2,\backslash dots,p\_N$ where $p_{i}p\_i$ represents that the $ii$-th word is formed by taking the $p_{i}p\_i$-th word and adding a single character to the end.

Let $MM$ be the number of words that are not a prefix of some other word. The next $MM$ lines will contain $w_1,w_2,\dots ,w_{M}w\_1,w\_2,\backslash dots,w\_M$, meaning that the $w_{i}w\_i$th word will be the $ii$th to be read. It is guaranteed that the words to be read form a permutation of the words in the word bank.

출력

Output $MM$ lines, where the $ii$th line contains the number of characters of the $ii$th word that Bessie reads.

5
0 1 2 3 4
5

0

4
0 0 1 1
4
3
2

2
1
0

4
0 0 1 1
2
3
4

1
2
0