CF928B.Chat

There are times you recall a good old friend and everything you've come through together. Luckily there are social networks — they store all your message history making it easy to know what you argued over 10 years ago.

More formal, your message history is a sequence of messages ordered by time sent numbered from 1 to n where n is the total number of messages in the chat.

Each message might contain a link to an earlier message which it is a reply to. When opening a message x or getting a link to it, the dialogue is shown in such a way that k previous messages, message x and k next messages are visible (with respect to message x). In case there are less than k messages somewhere, they are yet all shown.

Digging deep into your message history, you always read all visible messages and then go by the link in the current message x (if there is one) and continue reading in the same manner.

Determine the number of messages you'll read if your start from message number t for all t from 1 to n. Calculate these numbers independently. If you start with message x, the initial configuration is x itself, k previous and k next messages. Messages read multiple times are considered as one.

有时，你会想起一位久违的老朋友，以及你们共同经历的一切。幸运的是，如今有社交网络——它们保存了你全部的聊天记录，让你能轻松查到十年前你们究竟为何而争执。

更形式化地讲，你的聊天记录是一个按发送时间排序的消息序列，编号从 $1$ 到 $n$，其中 $n$ 是该聊天中消息的总数。

每条消息可能包含一个指向其回复对象（即某条更早发出的消息）的链接。当你打开消息 $x$ 或通过链接访问它时，对话界面会以消息 $x$ 为中心，显示其前 $k$ 条消息、消息 $x$ 本身以及其后 $k$ 条消息（相对于消息 $x$ 的位置）。若某侧消息不足 $k$ 条，则将该侧所有可用消息全部显示。

当你深入挖掘自己的聊天记录时，你总是先完整阅读当前可见的所有消息，然后顺着当前消息 $x$ 中所含的链接（如果存在）跳转至被回复的消息，并以同样方式继续阅读。

对每个起始消息编号 $t$（$t = 1, 2, \dots, n$），求出从消息 $t$ 开始阅读所涉及的不同消息的总数。这些数值需独立计算。若从消息 $x$ 开始，则初始可见范围为：消息 $x$ 本身、其前 $k$ 条消息及后 $k$ 条消息。若某条消息被多次读到，仅计为一次。

The first line contains two integers n and k (1 ≤ n ≤ 105, 0 ≤ k ≤ n) — the total amount of messages and the number of previous and next messages visible.

The second line features a sequence of integers _a_1, _a_2, ..., a__n (0 ≤ a__i < i), where a__i denotes the i-th message link destination or zero, if there's no link from i. All messages are listed in chronological order. It's guaranteed that the link from message x goes to message with number strictly less than x.

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 10^5$，$0 \leq k \leq n$）—— 分别表示消息的总数以及可见的前驱和后继消息的数量。

第二行包含一个整数序列 $a_1,\ a_2,\ \dots,\ a_n$（$0 \leq a_i < i$），其中 $a_i$ 表示第 $i$ 条消息的链接目标；若第 $i$ 条消息无链接，则 $a_i = 0$。所有消息按时间顺序列出。保证从消息 $x$ 出发的链接必定指向编号严格小于 $x$ 的消息。

Print n integers with i-th denoting the number of distinct messages you can read starting from message i and traversing the links while possible.

输出 $n$ 个整数，其中第 $i$ 个整数表示从第 $i$ 条消息开始、在可能的情况下沿链接遍历所能读取的不同消息的数量。

Consider i = 6 in sample case one. You will read message 6, then 2, then 1 and then there will be no link to go.

In the second sample case i = 6 gives you messages 5, 6, 7 since k = 1, then 4, 5, 6, then 2, 3, 4 and then the link sequence breaks. The number of distinct messages here is equal to 6.

考虑样例一中的 $i = 6$。你将依次读取消息 6、2、1，然后链接中断，无法继续。

在样例二中，当 $i = 6$ 且 $k = 1$ 时，你将依次读取消息 5、6、7，接着是 4、5、6，再接着是 2、3、4，之后链接序列中断。此处不同消息的总数为 6。