题目描述

有 $n$ 个岛，编号 $1\sim n$。给定长度为 $(n-1)$ 的正整数数列 $v_1,v_2,\ldots,v_{n-1}$。

当你在岛 $i$（$1\le i\lt n$）上时，可以跳到岛 $(i+1)$ 上或者岛 $v_i$ 上。这里，$i\lt v_i$。

给定正整数 $k$。对于岛 $i$，定义 $f(i,k)$ 表示从它出发跳至多 $k$ 步能够跳到的岛有多少个（包括自身）。

此外，$v_i$ 还满足特殊性质：对于任意 $1\le i\lt j\lt n$，要么 $v_i\le j$，要么 $v_j\le v_i$。

对于 $i=1,2,\ldots,n$，求出 $f(i,k)$。

补充说明：即使岛 $i$ 有多种在 $k$ 步内跳到岛 $j$ 的方式，岛 $j$ 也只算一次。

输入格式

第一行，两个正整数 $n,k$。

第二行，$(n-1)$ 个正整数 $v_1,v_2,\ldots,v_{n-1}$。

输出格式

输出一行 $n$ 个正整数，第 $i$ 个数表示 $f(i,k)$。

5 1
4 3 4 5

3 2 2 2 1

6 2
2 3 5 5 6

3 4 4 3 2 1

提示

样例解释

• 样例 $1$ 解释：以岛 $1$ 为例，跳 $0$ 步可以到达岛 $1$，跳 $1$ 步可以到达岛 $\{2,4\}$。所以 $f(1,1)=3$。

数据范围

对于 $100\%$ 的数据，保证：

• $1\le n\le 3\times 10^5$；
• $1\le k\lt n$；
• $i\lt v_i\le n$；
• 对于任意 $1\le i\lt j\lt n$，要么 $v_i\le j$，要么 $v_j\le v_i$。

• 特殊性质 $\text{A}$：$k\le 50$。
• 特殊性质 $\text{B}$：$v_i\le i+2$。