Background

二十年后,小开同学成了一家大型软件公司拼夕夕的Boss。该公司由N人组成。编号为1到N,小开同学的工号为1。公司的结构像一棵树一样,每个员工(小开同学除外)都有一个唯一的直接上司,每个老板都可以有多名下属。小开同学没有上司,只有下属。

公司接到订单后,小开同学会将该任务安排给他编号最小的直接下属。然后,该直接下属也将任务委托给他编号最小的下属,这个过程会重复进行,直到任务被发送给没有下属的人,然后此人必须亲自完成任务。

真正完成任务的人将获得1个单位的奖励,这个人的直接上司将获得2个单位的奖励这个人的直接上司的直接上司获得3个单位的奖励,依此类推,一直到小开同学。之后,真正完成工作的员工意识到制度的不公平并感到伤心,就会辞职。

当公司收到的下一个订单时,虽然少了一个人,但工作必须继续。任务是无限多的(直到公司倒闭),因此整个过程(分配新任务,执行任务,发放奖励和执行任务人员的退出重复进行,最后小开同学独自留在公司并完成他的第一个(也是他的最后一个)任务.

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

Description

Given two integers x and y, print the sum.

Format

Input

输入有两行。

第一行输入包含一个正整数N,表示包括小开同学在内的员工的个数。

第二行有n-1整数,分别为a2,a3,.......an(1<=ai<i)表示第i个员工的上司。

Output

输出包括一行,包含n个整数,第i个整数表示编号为i的人能得到的奖励数。

Samples

5 1 2 2 3

13 8 3 1 1

Limitation

1s, 1024KiB for each test case.