Jump Civilization

"Here in Parkour Jump Civilization, No One Chooses to Jump for the Beef" ━ Evbo - Parkour Civilization, the movie

Task

In jump civilization, the world consists of $N$ floating islands, numbered $1$ to $N$. When at island $i$ (for $1 \leq i < N$), the members of jump civilization can either take:

• an easy jump, from island $i$ to island $i + 1$; or
• a difficult jump, from island $i$ to island $v_i$, where $i < v_i \leq N$.

In order to rank up in jump civilization, the members of jump civilization need to compute the jumping power of each island. The jumping power of island $i$ is the number of islands which can be reached by starting at island $i$ and using at most $K$ jumps.

The previous Jump Champion, wanting to make sure that the jumping course is fair, instituted the following important rule: Whenever $1 \leq i < j \leq N$, either $v_i \leq j$ or $v_j \leq v_i$.

You, as an aspiring member of jump civilization, want to find the jumping power of every island - can you do this efficiently?

Input data

The first line of the input contains two space-separated integers $N$, $K$. The second line of the input contains $N - 1$ space-separated integers $v_1, \dots, v_{N - 1}$.

Output data

Output $N$ space-separated integers, the jumping power of the islands in order.

Constraints and clarifications

• $1 \leq N \leq 300 \ 000$
• $1 \leq K \leq N - 1$
• $i < v_i \leq N$
• For $1 \leq i < j \leq N$, either $v_i \leq j$ or $v_j \leq v_i$.
• If island $j$ can be reached from island $i$ in two different ways using at most $K$ jumps, then the island is only counted once for the jumping power of island $i$.
• When computing the jumping power of an island, it doesn't matter whether we use easy or difficult jumps — only the number of jumps matters.

Example 1

stdin

5 1
4 3 4 5

stdout

3 2 2 2 1

Explanations

From island $1$, one can reach island $1$ without jumping, and islands $2$ and $4$ with $1$ jump. In total, the jumping power of island $1$ is $3$.

Example 2

stdin

6 2
2 3 5 5 6

stdout

3 4 4 3 2 1