Mirko 成为了一家大公司的 CEO。这家公司由 $N$ 个人组成，编号为 $1$ 到 $N$，Mirko 的编号为 $1$。公司的结构使得每个员工（除了 Mirko）都有一个老板，我们称该员工是该老板的助手。每个老板可以有多个助手，但仍然需要向自己的老板汇报。除了处于金字塔顶端、没有老板但有助手的 Mirko 之外，这对每个人都适用。

当 Mirko 从投资者那里得到一项任务时，他会将该任务委托给编号最小的助手。然后，该助手将任务委托给他们编号最小的助手，这个过程不断重复，直到任务被分配给一个没有助手的倒霉员工，该员工必须完成这项任务。

这时真正的问题开始了。完成任务的人获得 $1$ 枚硬币，该人的老板获得 $2$ 枚硬币，该老板的老板获得 $3$ 枚硬币，依此类推，一直到 Mirko，他获得的硬币数量与该序列中的人数相同。之后，真正完成工作的员工意识到这个系统是多么不公平，出于原则辞职了。

当公司要执行下一项任务时，公司里少了一个人，所以也许薪水会变少，但工作必须继续。任务不断堆积，因此整个过程（分配新任务、执行任务、分发薪水以及执行任务的人辞职）不断重复，直到 Mirko 独自一人留在公司并完成他的第一项（也是最后一项）任务。

当然，到那时 Mirko 已经积累了相当多的财富，但他还想知道每个员工赚了多少钱。

输入格式

第一行包含一个正整数 $N$（$2 \le N \le 2 \cdot 10^5$），表示员工人数（包括 Mirko）。

第二行包含 $N - 1$ 个正整数 $a_2, a_3, a_4, \dots, a_n$（$1 \le a_i < i$），其中 $a_i$ 表示员工 $i$ 的老板。

输出格式

输出单行，包含 $N$ 个数字，第 $i$ 个数字对应第 $i$ 个员工赚取的硬币数量。

子任务

在占总分 50% 的测试用例中，满足 $2 \le N \le 5000$。

样例

输入样例 1

3
1 1

输出样例 1

5 1 1

输入样例 2

5
1 2 2 4

输出样例 2

13 8 1 3 1

说明

第二个样例的解释：

Mirko 将第一个任务分配给员工 2，员工 2 随后将其分配给员工 3，员工 3 完成了该任务。为此，员工 3 获得 1 枚硬币，员工 2 获得 2 枚硬币，员工 1（Mirko）获得 3 枚硬币。然后员工 3 辞职。

Mirko 将第二个任务分配给员工 2，员工 2 随后将其分配给员工 4（因为员工 3 辞职了），员工 4 随后将其分配给员工 5，员工 5 完成了该任务。为此，员工 5 获得 1 枚硬币，员工 4 获得 2 枚硬币，员工 2 获得 3 枚硬币，员工 1 获得 4 枚硬币。然后员工 5 辞职。

该过程共重复进行 5 次任务。

总共，Mirko 获得 13 枚硬币，员工 2 获得 8 枚硬币，员工 4 获得 3 枚硬币，员工 3 和员工 5 各获得 1 枚硬币。