Chat
Contest: VK Cup 2018 - Квалификация 1
Difficulty rating: 1400
Tags: *special, dp

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.

Input format:
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 a1, a2, ..., an (0 ≤ ai < i), where ai 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.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
6 0
0 1 1 2 3 2

Example output:
1 2 2 3 3 3

Example input:
10 1
0 1 0 3 4 5 2 3 7 0

Example output:
2 3 3 4 5 6 6 6 8 2

Editorial:
Let's use the dynamic. We will calculate the answer for the messages in the order of increasing their numbers. Let the current message has number x, then the answer was calculated for each y from 1 to (x - 1) and equals to cnty.
If there is no a link in the message y then the answer for this message — is a length of the segment [y - k, y + k] (it is necessary not to forget that the left boundary of the segment should be positive, and the right boundary should not exceed n).
In the other case, the message y contains the link to the message z. We know that z < y, so the cntz has been already calculated. All messages which were counted for message z should be counted in the answer for message y. Also new messages should be added — it is messages from the segment [y - k, y + k] which do not included in the segment [z - k, y + k]. Also we remember that the left boundary of the segment should be positive, and the right boundary should not exceed n.
After we considered all messages — simply print the array cnt.