Bureaucracy

Mirko is now the CEO of a huge corporation. The corporation has $N$ people, numbered $1$ to $N$, and Mirko is number $1$. Everyone except Mirko has exactly one boss, and we call that person an assistant of the boss. A boss can have several assistants and still reports to their own boss. Mirko is the exception. He sits at the top of the pyramid, so he has no boss, only assistants.

When the investors give Mirko a task, he passes it to his assistant with the smallest number. That assistant passes it to their own assistant with the smallest number, and this repeats until the task reaches somebody with no assistants. That person does the work.

This is where the real problem starts. The person who did the task gets $1$ coin, that person's boss gets $2$ coins, the boss of that boss gets $3$ coins, and so on up to Mirko, who gets as many coins as there are people in the chain. After the payout, the employee who actually did the work decides the system is unfair and quits.

The next task is handled with one person fewer in the corporation, so the payouts can be smaller, but the work must go on. Tasks keep piling up, so the whole procedure (assigning a task, doing it, splitting the coins, and losing the worker) repeats until Mirko is alone and does his first and last task himself.

Mirko will have collected a fortune by then, and he also wants to know how much every employee earned.

The first line contains the integer $N$ ($2 \le N \le 200000$), the number of employees including Mirko.

The second line contains $N - 1$ integers $a_2, a_3, \dots, a_N$ ($1 \le a_i < i$), where $a_i$ is the number of the boss of employee $i$.

Print one line with $N$ numbers separated by single spaces. The $i$th number is the total number of coins employee $i$ earns.

Follow the sample with $N = 5$. Mirko gives the first task to employee $2$, who gives it to employee $3$, who does the work. Employee $3$ gets $1$ coin, employee $2$ gets $2$ coins, and employee $1$ (Mirko) gets $3$ coins. Employee $3$ then quits.

Mirko gives the second task to employee $2$ again. Employee $3$ is gone, so employee $2$ passes it to employee $4$, who passes it to employee $5$, who does the work. Employee $5$ gets $1$ coin, employee $4$ gets $2$ coins, employee $2$ gets $3$ coins, and employee $1$ gets $4$ coins. Employee $5$ then quits.

The procedure runs for $5$ tasks in total. Mirko ends up with $13$ coins, employee $2$ with $8$, employee $4$ with $3$, and employees $3$ and $5$ with $1$ coin each.