有时您会想起一位好老朋友以及你们一起经历的一切。幸运的是,社交网络可以存储您所有的消息历史记录,让您可以轻松了解 10 多年前您争论的内容。
更正式地说,您的消息历史记录是按发送时间排序的消息序列,编号从 1 到 n,其中 n 是聊天中的消息总数。
每条消息都可能包含指向其回复的较早消息的链接。当打开消息 x 或获取其链接时,对话以这样的方式显示:k 条前一条消息、k 条消息 x 和 k 条下一条消息可见(相对于消息 x)。如果某个地方的消息少于 k 条,它们仍然会全部显示。
深入挖掘您的消息历史记录,您始终会阅读所有可见的消息,然后通过当前消息 x 中的链接(如果有)并以相同的方式继续阅读。
确定如果您从消息编号 t 开始读取从 1 到 n 的所有 t,则您将阅读的消息数。独立计算这些数字。如果从消息 x 开始,初始配置是 x 本身、k 条上一条消息和 k 条下一条消息。多次读取的消息被视为一条消息。
输入
第一行包含两个整数 n 和 k (1 ≤ n ≤ 105, 0 ≤ k ≤ n) — 消息总数以及可见的上一条和下一条消息的数量。
第二行包含一系列整数 a1、a2、...、an (0 ≤ ai < i),其中 ai 表示第 i 个消息链接目标,如果没有来自 i 的链接,则表示零。所有消息均按时间顺序列出。保证消息 x 的链接转到编号严格小于 x 的消息。
输出
打印 n 个整数,其中第 i 个表示您可以从消息 i 开始读取并尽可能遍历链接的不同消息的数量。
示例
输入 #1
6 0 0 1 1 2 3 2
输出 #1
1 2 2 3 3 3
输入 #2
10 1 0 1 0 3 4 5 2 3 7 0
输出 #2
2 3 3 4 5 6 6 6 8 2
输入 #3
2 2 0 1
输出 #3
2 2
注意
在示例案例一中考虑 i = 6。您将阅读消息 6,然后阅读消息 2,然后阅读消息 1,然后就没有链接可去了。
在第二个示例中,i = 6 为您提供消息 5、6、7,因为 k = 1,然后是 4、5、6,然后是 2、3、4,然后链接序列中断。这里不同消息的数量等于 6。