Island Hopping with Limited Jumps

You are given $n$ islands numbered from $1$ to $n$. In addition, you are given a sequence of positive integers $v_1, v_2, \ldots, v_{n-1}$ of length $n-1$. When you are on island $i$ (with $1 \le i < n$), you can jump either to island $i+1$ or to island $v_i$ (note that $i < v_i$).

You are also given a positive integer $k$. For each island $i$, define $$f(i,k)$$ as the number of distinct islands that can be reached from island $i$ by performing at most $k$ jumps (including the starting island itself).

It is guaranteed that the sequence $v_i$ satisfies the following special property: for any $1 \le i < j < n$, either $$v_i \le j$$ or $$v_j \le v_i$$.

For each island $i=1,2,\ldots,n$, compute $$f(i,k)$$.

Note: Even if there are multiple ways to reach an island within $k$ jumps, that island is only counted once. Also, observe that since the jumps are only in the forward direction, the set of reachable islands will always form a contiguous segment of islands.

inputFormat

The first line contains two positive integers $n$ and $k$, where $n$ is the number of islands and $k$ is the maximum number of jumps allowed.

The second line contains $n-1$ positive integers: $v_1,v_2,\ldots,v_{n-1}$.

outputFormat

Output $n$ integers. The $i$-th integer should be equal to $$f(i,k)$$, the number of distinct islands that can be reached from island $i$ using at most $k$ jumps. The answers should be printed in order from island $1$ to island $n$, separated by spaces.

sample

5 2
3 3 5 5

5 4 3 2 1