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. The first line contains two integers n and k ( 1 ≤ n ≤ 10 5 , 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 . 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. 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,