题目描述

𝐽𝐾成为了一个大型企业的𝐶𝐸𝑂， 包含𝐽𝐾本人在内，这个公司一共有𝑁个人，编号从1到𝑁， 𝐽𝐾的编号为1，公司员工关系的构建使得所有的员工(除了𝐽𝐾)都有一个直属上司。
我们称一名员工为他的直属上司的一位助手。每一位上司可以有多个助手，但他也会有一个直属上司，除 了𝐽𝐾—这个企业的最终𝐵𝑂𝑆𝑆。我们保证任何一个员工的最终上司都是𝐽𝐾。
当𝐽𝐾接到了一个来自客户的委托的时候，他会把任务分配到给他编号最小的一个助手。然后得到任务的这个人又会把任务分配给他的编号最小的助手。以此类推，直到一个没有助手的人接到了这份工作。
这就是真正的问题的开端。真正着手进行工作的员工只获得了一个硬币的工资，而他的上司则获得了两个硬币的工资，他上司的上司则获得了三个硬币的收益。以此类推，在这份工作完成之后，真正完成工作的雇员意识到了这个制度是多么的邪恶，于是他决定退出这个公司。
当下一个委托到达的时候，这样的过程将会重复，直到最后𝐽𝐾接手进行自己的第一份(也是最后一份)工作。
当然，在公司完全解散之前， 𝐽𝐾仍然可以获得一笔不菲的财富。你的任务就是计算出𝐽𝐾的公司在解散之前每位员工究竟可以获得多少硬币。

输入格式

第一行包含一个正整数$𝑁(2 ≤ 𝑁 ≤ 2 * 10^5)$，含义如题面所示。
接下来一行𝑁 − 1个正整数$𝑎2, 𝑎3, 𝑎4, … , 𝑎𝑛, (1 ≤ 𝑎𝑖 < i)， 𝑎𝑖$表示员工$𝑖$的直属上司。

输出格式

输出一行$𝑁$个整数，第$𝑖$个整数表示编号为$𝑖$的员工获得的硬币数。

数据范围

存在50%的数据， $2 ≤ 𝑁 ≤ 5 000$。

样例

样例输入1

3
1 1

样例输出1

5 1 1

样例输入2

5
1 2 2 4

样例输出2

13 8 1 3 1

样例二解释：

第一个工作的传播路径为1−> 2−> 3，随后3退出， 3获得一个硬币， 2获得两个硬币,1获得三个硬币。
第二个工作的传播路径为1−> 2−> 4−> 5， 随后5退出， 5获得一个硬币,4获得两个硬币， 2获得三个硬币， 1获得四个硬币。
随后的工作传播路线为1−> 2−> 4， 1−> 2， 1。最终获得的硬币为13,8,1,3,1。