Description

Mirko 是一家大公司的 CEO。该公司由 $N$ 人组成，编号为 $1$ 到 $N$，Mirko 编号为 $1$ 。公司的结构像一棵树一样，每个员工（Mirko 除外）都有老板，我们说这个员工是该老板的助手。每个老板都可以有多名助手。Mirko 没有老板，但有他的助手。

之后会有一些任务，Mirko 会将该任务委托给他编号最小的助手。然后，该助手也将任务委托给他编号最小的助手，并且这个过程重复进行，直到任务被发送给没有助手的人，然后他必须亲自完成任务。

执行任务的人获得 1 个硬币，那个人的老板获得 2 个硬币，那个人的老板获得 3 个硬币，依此类推，一直到 Mirko。之后，真正完成工作的员工意识到系统的不公平并感到伤心，并且不会再执行任务（也就是辞职）。

当公司收到的下一个任务时，因为少了一个人，所以薪水可能更少，但工作必须继续。任务是无限多的（直到公司倒闭），因此整个过程（分配新任务，执行任务，划分薪水和执行任务人员的退出）重复进行，最后 Mirko 独自留在公司并完成他的第一个（也是他的最后一个）任务。

当然，在此之前， Mirko 将积累相当多的财富，但他也想知道每个员工赚了多少钱。

Input Format

第一行有一个整数 $N(2 \le N \le 2 \times 10^5)$，即包括 Mirko 在内的员工的个数。

紧接着第二行有 $N-1$ 个整数，分别为 $a_2,a_3,\cdots ,a_N(1 \le a_i < i )$，$a_i$ 表示员工 $i$ 的老板。

Output Format

输出一行 $N$ 个整数，第 $i$ 个整数表示编号为 $i$ 的人能得到的金币数。

3
1 1

5 1 1

5
1 2 2 4

13 8 1 3 1

Hint

$50\%$ 的数据满足 $2 \le N \le 5000$。