Bessie は Elsie の語彙テストの準備を手伝っています。出題される単語は $M$ 個の異なる単語を持つ単語集から選ばれ、どの単語も単語集の別の単語の接頭辞ではありません。

単語集が空でない間、Bessie は単語を選んで削除し、左から右へ一文字ずつ読みます。Elsie は単語を一意に特定できたらすぐ伝え、Bessie は読むのをやめます。

読む順序はすでに $w_1,w_2,\dots,w_M$ と決めています。Elsie が最速で答えると、各単語を何文字読みますか？

単語は圧縮形式で与えられます。まず異なる $N+1$ 個（$1\le N\le 10^6$）の単語を定義し、他の単語の接頭辞でないものすべてを単語集に入れます。定義は次のとおりです。

• 最初に、$0$ 番目の単語は空文字列です。
• 各 $1\le i\le N$ について、$i$ 番目の単語は $p_i$ 番目の単語の末尾に一文字加えたものです（$0\le p_i<i$）。文字は $N+1$ 個すべてが異なるように選ばれます。

入力

最初の行は $N$ を含み、$N+1$ が圧縮形式の単語数です。

次の行は $p_1,p_2,\dots,p_N$ を含み、$p_i$ は $i$ 番目の単語を $p_i$ 番目の単語の末尾に一文字加えて作ることを表します。

他の単語の接頭辞でない単語数を $M$ とします。続く $M$ 行は $w_1,w_2,\dots,w_M$ を含み、$w_i$ 番目の単語を $i$ 番目に読むことを表します。読む単語は単語集の単語の順列と保証されます。

出力

$M$ 行出力し、$i$ 行目には $i$ 番目に読む単語の文字数を示してください。

入出力例

入力 1

5
0 1 2 3 4
5

出力 1

0

注記

$0\dots 5$ と番号付けされた $6$ 単語があります。単語 $5$ だけが他の接頭辞でないため、単語集にはこれだけ入ります。一般に一単語だけ残れば、Elsie は一文字も聞かずに特定できます。

入力 2

4
0 0 1 1
4
3
2

出力 2

2
1
0

注記

単語集は単語 $2$、$3$、$4$ からなります。

単語 $3$ と $4$ は最初の文字が同じなので、単語 $4$ の特定には二文字必要です。

単語 $4$ はすでに読まれたので、単語 $3$ の最初の文字を読むと一意に特定できます。

入力 3

4
0 0 1 1
2
3
4

出力 3

1
2
0

小課題

• 入力四から五：長さ $20$ を超える単語はありません。
• 入力六から十：単語集の全単語の長さの合計は $10^7$ 以下です。
• 入力十一から十八：追加の制約はありません。

問題作成者：Benjamin Qi