Hobson 先生退休后不再经营马厩，转而投资了一种更现代的交通工具——火车。他建造了一个拥有 $n$ 个车站的铁路网。然而，他依然坚持让乘客免受选择之苦：从每个车站出发，乘客只能乘火车前往唯一的一个车站。这样的旅程被称为一“段”（leg）。请注意，这是一次单向旅程，可能无法原路返回。

Hobson 先生还提供了一种车票，允许乘客在一次行程中最多乘坐 $k$ 段。每个车站的出口处都设有一台自动检票机（只有一个，因此乘客无需决定使用哪一个）。检票机会检查从起始站到终点站的距离是否不超过 $k$ 段。

每台检票机都需要预设一个有效起始站列表，但这个列表占用的内存越多，机器就越昂贵。请帮助 Hobson 先生确定，对于每个车站 $A$，有多少个车站（包括 $A$ 本身）满足乘客可以在最多 $k$ 段内到达 $A$。

图 H.1：样例 1 的示意图。每个圆圈代表一个车站。圆圈外的数字是当 $k=2$ 时加载到检票机中的车站编号。

输入格式

输入的第一行包含两个整数 $n$ 和 $k$，其中 $n$ ($2 \le n \le 5 \cdot 10^5$) 是车站数量，$k$ ($1 \le k \le n - 1$) 是车票允许乘坐的最大段数。接下来有 $n$ 行，第 $i$ 行包含一个整数 $d_i$ ($1 \le d_i \le n$ 且 $d_i \neq i$)，表示从车站 $i$ 出发乘一段火车可以到达的车站。

输出格式

输出 $n$ 行，第 $i$ 行包含可以在最多 $k$ 段内到达车站 $i$ 的车站数量。

样例

输入 1

6 2
2
3
4
5
4
3

输出 1

1
2
4
5
3
1

输入 2

5 3
2
3
1
5
4

输出 2

3
3
3
2
2