Anh Khôi là một giám đốc điều hành (CEO) của một công ty phần mềm rất lớn. Công ty của anh ấy có ~ n ~ người được đánh số thứ tự từ 1 đến ~ n ~ (CEO được đánh số thứ tự là 1). Để đơn giản trong việc quản lý và phân công công việc, mọi người trong công ty được phân cấp quản lý theo dạng hình cây. Với một người bất kỳ được quản lý trực tiếp bởi một người cao hơn (trừ CEO) và người đó cũng có thể quản lý một số người cấp dưới của mình. Những người không quản lý ai cả là những lập trình viên.

Anh Khôi vừa nhận được một dự án và cần phân công việc cho tất cả mọi người trong công ty. Khi một người nhận được một công việc từ người quản lý trực tiếp của mình (CEO chỉ nhận dự án từ đối tác) thì người này nhận được một đồng tiền ảo Token và người quản lý trực tiếp sẽ nhận được 2 Token, người quản lý cấp cao hơn kế tiếp nhận được 3 Token…, tiếp tục cho đến CEO là người nhận được số tiền nhiều nhất. Như vậy, khi những lập trình viên nhận công việc, họ chỉ có được 1 Token vì họ không phải là người quản lý nên không thể chia công việc cho những người khác mà phải tự thực hiện.

Yêu cầu: Hãy giúp anh Khôi tính số Token của mỗi người trong công ty sau khi công ty đã thực hiện xong dự án.

Dữ liệu vào

• Dòng đầu ghi số nguyên dương ~ n ~ ~ (2 ≤ n ≤ 2.10^5) ~;
• Dòng thứ hai ghi ~ n - 1 ~ số nguyên cách nhau một dấu cách, với số thứ ~ i ~ ~ (i = 1..n-1) ~ là số thứ tự của người quản lý trực tiếp người thứ ~ i+1 ~.

Kết quả

Ghi ~ n ~ số nguyên trên một dòng, với số thứ ~ i ~ ~ (i = 1..n) ~ là số Token của người thứ ~ i ~ nhận được. Giữa các số trên cùng dòng được ghi cách nhau đúng một dấu cách.

Ràng buộc

• Có 50% số test với ~ 2 ≤ n ≤ 5000 ~.
• Có 50% số test với ~ 5000 ≤ n ≤ 2.10^5) ~.

Ví dụ:

Input 1

3
1 1 

Output 1

5 1 1 

Input 2

5
1 2 2 4 

Output 2

13 8 1 3 1