Mirko has become CEO of a huge corporation. This corporation consists of people, labeled from to , and Mirko is labeled . The corporation is structured so that each employee (except Mirko) has a boss, and we say that employee is an assistant to that boss. Each boss can have multiple assistants, but still reports to their boss. This holds for everyone except Mirko, who is at the top of the pyramid and doesn't have a boss, but has his assistants.
When Mirko gets a task from the investors, he then delegates that task to his assistant with the minimal number. This assistant then delegates the task to their assistant with the minimal number, and this process repeats until the task is given to an unlucky person without an assistant, who then must do the task.
This is when the real problems begin. The person that did the task gets paid coin, the boss of that person gets coins, the boss of that person gets coins, and so on, all the way to Mirko, who gets as many coins as there are people in this sequence. After that, the employee that really did the job realizes how unfair the system is and quits their job out of principle.
When it comes to doing the next task in the corporation, there is a person less, so maybe the paychecks are less, but the work must continue. Tasks are piling up, so the whole procedure (assigning a new task, doing it, dividing paychecks and the person doing the task quitting) repeats until Mirko is left alone in the corporation and does his first (also his last) task. Of course, Mirko will have amassed quite a fortune until then, but he also wants to know how much money each of the employees earned.
Input Specification
The first line of input contains the positive integer , the number of employees (including Mirko).
The following line contains positive integers , where denotes the boss of employee .
Output Specification
You must output a single line consisting of numbers, the number corresponding to the amount of money earned by the employee.
Scoring
In test cases worth of total points, it will hold .
Sample Input 1
3
1 1
Sample Output 1
5 1 1
Sample Input 2
5
1 2 2 4
Sample Output 2
13 8 1 3 1
Explanation for Sample Output 2
Mirko assigns the first task to employee , who then assigns it to employee , who then does it. For this, employee gets coin, employee gets coins, and employee (Mirko) gets coins. Employee then quits.
Mirko assigns the second task to employee , who then assigns it to employee (because employee quit), who then assigns it to employee , who then does it. For this, employee gets coin, employee gets coins, employee gets coins, and employee gets coins. Employee then quits.
The procedure is repeated for a total of tasks.
In total, Mirko gets coins, employee gets , employee gets , and employee and each get coin.
Comments