在跳跃文明中，世界由 $N$ 个浮岛组成，编号为 $1$ 到 $N$。当位于岛屿 $i$（对于 $1 \le i < N$）时，跳跃文明的成员可以选择：
- 简单跳跃：从岛屿 $i$ 跳到岛屿 $i+1$；或者
- 困难跳跃：从岛屿 $i$ 跳到岛屿 $v_i$，其中 $i < v_i \le N$。
为了在跳跃文明中晋升，成员们需要计算每个岛屿的“跳跃力”。岛屿 $i$ 的跳跃力是指从岛屿 $i$ 出发，使用最多 $K$ 次跳跃所能到达的岛屿数量。
上一任跳跃冠军为了确保跳跃课程的公平性，制定了以下重要规则：“对于任意 $1 \le i < j \le N$，要么 $v_i \le v_j$，要么 $v_j \le v_i$。”
作为一名有抱负的跳跃文明成员，你想要找出每个岛屿的跳跃力——你能高效地完成这项任务吗？
输入格式
输入的第一行包含两个空格分隔的整数 $N, K$。输入的第二行包含 $N-1$ 个空格分隔的整数 $v_1, \dots, v_{N-1}$。
输出格式
输出 $N$ 个空格分隔的整数，依次表示各岛屿的跳跃力。
数据范围
- $1 \le N \le 300\,000$
- $1 \le K \le N - 1$
- $i < v_i \le N$
- 对于 $1 \le i < j \le N$，要么 $v_i \le v_j$，要么 $v_j \le v_i$。
- 如果岛屿 $j$ 可以通过两种不同的方式从岛屿 $i$ 在最多 $K$ 次跳跃内到达，则该岛屿在计算岛屿 $i$ 的跳跃力时仅计数一次。
- 在计算岛屿的跳跃力时，使用简单跳跃还是困难跳跃并不重要——只有跳跃次数很重要。
子任务
| # | 分值 | 数据范围 |
|---|---|---|
| 1 | 6 | $N \le 2\,000$ |
| 2 | 27 | $N \le 100\,000$ 且 $K \le 50$ |
| 3 | 11 | $v_i \le i + 2$ 对于 $1 \le i < N$ |
| 4 | 37 | $N \le 100\,000$ |
| 5 | 19 | 无附加限制 |
样例
样例输入 1
5 1 4 3 4 5
样例输出 1
3 2 2 2 1
说明 1
从岛屿 1 出发，无需跳跃即可到达岛屿 1，通过 1 次跳跃可到达岛屿 2 和 4。总计，岛屿 1 的跳跃力为 3。
样例输入 2
6 2 2 3 5 5 6
样例输出 2
3 4 4 3 2 1