Bessie giúp Elsie chuẩn bị bài kiểm tra từ vựng sắp tới. Từ được chọn từ ngân hàng $M$ từ khác nhau, không từ nào là tiền tố của từ khác trong ngân hàng.

Khi ngân hàng chưa rỗng, Bessie chọn từ, xóa nó và đọc từng ký tự từ trái sang phải. Elsie báo ngay khi xác định duy nhất được từ, rồi Bessie ngừng đọc.

Thứ tự đã là $w_1,w_2,\dots,w_M$. Nếu Elsie trả lời nhanh nhất có thể, Bessie sẽ đọc bao nhiêu ký tự mỗi từ?

Từ được cho ở dạng nén. Trước tiên định nghĩa $N+1$ ($1\le N\le 10^6$) từ khác nhau; ngân hàng gồm mọi từ không là tiền tố của từ khác. Định nghĩa như sau:

• Ban đầu, từ thứ $0$ là chuỗi rỗng.
• Với mỗi $1\le i\le N$, từ thứ $i$ là từ thứ $p_i$ thêm một ký tự ở cuối ($0\le p_i<i$). Ký tự được chọn để mọi $N+1$ từ đều khác nhau.

Dữ liệu vào

Dòng đầu chứa $N$, với $N+1$ là số từ dạng nén.

Dòng sau chứa $p_1,p_2,\dots,p_N$; $p_i$ biểu thị từ thứ $i$ được tạo bằng cách thêm ký tự vào cuối từ thứ $p_i$.

Gọi $M$ là số từ không là tiền tố của từ khác. $M$ dòng tiếp chứa $w_1,w_2,\dots,w_M$: từ thứ $w_i$ được đọc thứ $i$. Đảm bảo thứ tự đọc là hoán vị các từ trong ngân hàng.

Dữ liệu ra

In $M$ dòng; dòng thứ $i$ là số ký tự Bessie đọc của từ thứ $i$ theo thứ tự đọc.

Ví dụ

Dữ liệu vào 1

5
0 1 2 3 4
5

Dữ liệu ra 1

0

Ghi chú

Có $6$ từ mang nhãn $0\dots 5$. Chỉ từ $5$ không là tiền tố của từ khác nên ngân hàng chỉ có nó. Nói chung, khi còn một từ, Elsie không cần ký tự nào để xác định.

Dữ liệu vào 2

4
0 0 1 1
4
3
2

Dữ liệu ra 2

2
1
0

Ghi chú

Ngân hàng gồm các từ $2$, $3$, $4$.

Elsie cần hai ký tự để xác định $4$, vì $3$ và $4$ chung ký tự đầu.

Khi Bessie đọc ký tự đầu của $3$, Elsie xác định được nó, vì $4$ đã được đọc.

Dữ liệu vào 3

4
0 0 1 1
2
3
4

Dữ liệu ra 3

1
2
0

Nhiệm vụ con

• Đầu vào thứ tư đến thứ năm: không từ nào dài hơn $20$.
• Đầu vào thứ sáu đến thứ mười: tổng độ dài mọi từ trong ngân hàng không vượt quá $10^7$.
• Đầu vào thứ mười một đến thứ mười tám: không có ràng buộc bổ sung.

Tác giả bài toán: Benjamin Qi