While wandering through a forest, you have stumbled upon a mysterious dynamic apple tree! This tree can be thought of as a set $N$ of connected junctions, numbered from $1$ to $N$, such that there is exactly one path between any two junctions. The root of the tree is at junction $1$ (which is at the bottom), and each junction has at most one branch connecting it to a junction below it, which we will call $J_i$ for all junctions $2\le i\le N$. The only junction without a branch connecting it to a junction below it is junction $1$, the root of the tree.

You will pick a junction and collect all apples from the root up to, and including the junction you stop at, before climbing back down the tree. Unfortunately for you, $M-1$ of your friends have decided to follow you to this apple tree and also want to collect apples. For simplicity, we will number your friends from $1$ to $M-1$, and you will be assigned number $M$.

There is exactly one apple at each junction, but since this is a dynamic tree, it has a special property where each apple regrows exactly $K$ minutes after it is picked. Note that an apple can be picked the same second it regrows.

Every minute, one of your friends (or you) will climb up the tree, collect some apples, and climb back down the tree. They will go in order of their number from $1$ to $M$. Each of you will do this once. Assuming each friend maximizes the total number of apples they will collect, you want to know the number of apples each of them will end up with.

Constraints

For this question, Python users are recommended to use CPython over PyPy.

For this problem, you will be required to pass all the samples in order to receive any points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

Subtask	Points	$N,M,K$
$1$	$10\mathrm{\%}$	$2\le N\le 300$ $1\le M,K\le 300$
$2$	$15\mathrm{\%}$	$2\le N\le 5000$ $1\le M,K\le 5000$
$3$	$75\mathrm{\%}$	$2\le N\le 100000$ $1\le M,K\le 100000$

For all subtasks:

$1\le J_i<i$ for all $i$ $(2\le i\le N)$

Input Specification

The first line contains 3 integers, $N$, $M$, $K$.

The last line contains $N-1$ integers, describing the tree structure. The $i^{th}$ integer contains the value $J_{i+1}$, indicating that junction $i$ is connected to junction $J_{i+1}$.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output a single line containing $M$ space separated integers. The $i^{th}$ integer is the number of apples collected by the $i^{th}$ person.

Sample Input

6 3 2
1 2 2 3 3

Sample Output

4 1 4

Sample Explanation

At the first minute, person $1$ can climb up to junction $6$ and collect $4$ apples.

At the second minute, person $2$ can climb up to junction $4$ and collect $1$ apple.

At the third minute, the apples at junctions $1$, $2$, $3$, and $6$ regrow. Person $3$ can climb up to junction $5$ and collect $4$ apples.