Bessie 正在幫助 Elsie 準備即將到來的詞彙測驗。測驗的單字來自包含 $M$ 個不同單字的詞庫，其中沒有任何單字是另一個詞庫單字的前綴。

只要詞庫非空，Bessie 就從中選擇一個單字，將其刪除，然後由左至右逐字元讀給 Elsie。一旦 Elsie 能唯一確定這個字，就告訴 Bessie，Bessie 隨即停止朗讀。

Bessie 已決定按 $w_1,w_2,\dots,w_M$ 的順序朗讀。如果 Elsie 儘快回答，Bessie 會讀出每個字的多少個字元？

單字以壓縮格式給出。先定義 $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$ 行包含 Bessie 朗讀第 $i$ 個字時讀出的字元數。

範例

輸入格式 1

5
0 1 2 3 4
5

輸出格式 1

0

說明

共有 $6$ 個單字，編號為 $0\dots 5$。單字 $5$ 是唯一不是其他單字前綴的字，所以詞庫只有它。一般來說，詞庫只剩一個字時，Elsie 不需要任何字元就能確定它。

輸入格式 2

4
0 0 1 1
4
3
2

輸出格式 2

2
1
0

說明

詞庫包含單字 $2$、$3$ 和 $4$。

Elsie 需要兩個字元才能確定單字 $4$，因為單字 $3$ 和 $4$ 的首字元相同。

Bessie 讀出單字 $3$ 的第一個字元後，Elsie 就能唯一確定它，因為單字 $4$ 已經被讀過。

輸入格式 3

4
0 0 1 1
2
3
4

輸出格式 3

1
2
0

子任務

• 輸入四至五：沒有單字的長度超過 $20$。
• 輸入六至十：詞庫中所有單字的長度之和不超過 $10^7$。
• 輸入十一至十八：沒有額外限制。

題目作者：Benjamin Qi