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<sup class="upper-index">5</sup>, 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*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (0 ≤ *a*<sub class="lower-index">*i*</sub> &lt; *i*), where *a*<sub class="lower-index">*i*</sub> 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*.
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.
6 0
0 1 1 2 3 2
1 2 2 3 3 3 
10 1
0 1 0 3 4 5 2 3 7 0
2 3 3 4 5 6 6 6 8 2 
2 2
0 1
2 2 
1 1
0
1 
5 2
0 1 2 3 1
3 4 5 5 5 
30 1
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 2 0 0 0 0 0 2 1 0
2 3 3 3 3 3 3 3 3 3 3 3 3 5 5 5 3 3 3 3 3 6 3 3 3 3 3 6 5 2 
100 5
0 1 1 1 0 5 6 6 8 8 9 11 12 11 8 0 0 14 6 16 7 21 15 23 15 24 0 0 0 28 0 29 26 27 19 0 0 21 37 32 40 30 37 34 39 38 34 38 0 0 41 24 45 47 0 33 46 26 31 0 21 57 57 31 63 63 25 59 65 56 68 0 30 55 55 0 70 43 59 49 59 79 66 74 0 11 65 0 80 63 0 84 73 49 73 81 0 86 76 98
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 11 11 23 22 15 23 24 28 29 30 31 11 11 11 13 11 14 38 18 33 11 11 34 13 22 23 24 17 28 19 42 29 44 11 11 33 40 27 36 11 49 53 42 22 11 34 58 59 22 61 62 41 31 65 60 34 11 24 22 22 11 67 28 33 22 33 36 73 32 11 27 72 11 31 70 11 40 35 22 35 43 9 35 18 35 
2 2
0 0
2 2 
2 1
0 0
2 2 
2 1
0 1
2 2 
2 0
0 0
1 1 
2 0
0 1
1 2 
3 0
0 0 0
1 1 1 
3 0
0 0 1
1 1 2 
3 0
0 0 2
1 1 2 
3 0
0 1 0
1 2 1 
3 0
0 1 1
1 2 2 
3 0
0 1 2
1 2 3 
3 1
0 0 0
2 3 2 
3 1
0 0 1
2 3 3 
3 1
0 0 2
2 3 3 
3 1
0 1 0
2 3 2 
3 1
0 1 1
2 3 3 
3 1
0 1 2
2 3 3 
3 2
0 0 0
3 3 3 
3 2
0 0 1
3 3 3 
3 2
0 0 2
3 3 3 
3 2
0 1 0
3 3 3 
3 2
0 1 1
3 3 3 
3 2
0 1 2
3 3 3 
3 3
0 0 0
3 3 3 
3 3
0 0 1
3 3 3 
3 3
0 0 2
3 3 3 
3 3
0 1 0
3 3 3 
3 3
0 1 1
3 3 3 
3 3
0 1 2
3 3 3 
10 3
0 0 0 0 0 0 0 4 0 4
4 5 6 7 7 7 7 10 5 10 
20 2
0 0 0 0 2 1 0 3 0 1 1 11 0 10 0 0 9 17 9 0
3 4 5 5 7 8 5 10 5 8 8 9 5 12 5 5 10 11 9 3 
40 0
0 1 2 3 4 5 0 0 0 0 0 11 12 0 14 10 0 16 15 0 19 21 22 0 23 25 25 24 24 29 29 0 0 31 0 35 31 36 34 29
1 2 3 4 5 6 1 1 1 1 1 2 3 1 2 2 1 3 3 1 4 5 6 1 7 8 8 2 2 3 3 1 1 4 1 2 4 3 5 3 
n,k = map(int, input().split())
a = list(map(int , input().split()))
a = [i-1 for i in a]
ans = []
for i in range(n):
    if a[i] == -1:
        ans.append(1 + min(n-i-1, k) + min(i, k))
    else:
        ref = a[i]
        r1 = min(ref+k, n-1)
        r2 = min(i+k, n-1)
        l2 = max(i-k, 0)
        if l2 > r1:
            ans.append(ans[ref] + (r2-l2+1))
        else:
            ans.append(ans[ref] + (r2-r1))
print(' '.join([str(i) for i in ans]))