← 返回题目列表

Codeforces · 928/B

B. 聊天

中文机器翻译题面 查看原题

有时您会想起一位好老朋友以及你们一起经历的一切。幸运的是,社交网络可以存储您所有的消息历史记录,让您可以轻松了解 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。