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-----

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.


-----Output-----

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.


-----Examples-----
Input
6 0
0 1 1 2 3 2

Output
1 2 2 3 3 3 

Input
10 1
0 1 0 3 4 5 2 3 7 0

Output
2 3 3 4 5 6 6 6 8 2 

Input
2 2
0 1

Output
2 2 



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

Difficulty: interview

Starter code:

Solutions:
# python3

def readline(): return tuple(map(int, input().split()))


def main():
    n, k = readline()
    a = readline()

    answer = list()

    for (i, link) in enumerate(a):
        bottom = max(0, i - k)
        top = min(n, i + k + 1)

        if link == 0:
            answer.append(top - bottom)
        else:
            bottom = max(bottom, link + k)
            answer.append(max(0, top - bottom) + answer[link - 1])

    print(" ".join(map(str, answer)))


main()


n, k = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))
dp = [0] * n
for i in range(n):
	if a[i] == -1:
		dp[i] = min(i, k) + min(n - i - 1, k) + 1
	else:
		dp[i] = dp[a[i]] - min(n - a[i] - 1, k) + min(n - i - 1, k) + min(2 * k, i - a[i] - 1) + 1
print(' '.join(list(map(str, dp))))

n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
b=[min(1+k,n)]*n
for i in range(1,n):
    x = a[i] - 1
    if x==-1:
        b[i]=min(i,k)+1+min(n-i-1,k)
    else:
        b[i]=b[x]+min(k+1,i-(x+min(k,n-x-1)))+min(n-i-1,k)
print(*b)


n, k = map(int,input().split())
dp = [0]
bound = [0]
a = list(map(int,input().split()))

for i in range(1, n+1):
    dp.append(dp[a[i-1]])
    bound.append(i+k)
    t1 = max(bound[a[i-1]]+1, i-k)
    t2 = min(i+k, n)
    t3 = t2 - t1 + 1
    if t3>0: dp[i] += t3

for i in range(1, n+1):
    print(dp[i],end = ' ')


n, k = map(int, input().split())
a = [int(x) for x in input().split()]

ans = []
for i in range(n):
    c = 0
    imin = max(0, i - k)
    imax = min(n-1, i + k)
    if a[i] != 0:
        c += ans[a[i]-1]
        amin = max(0, a[i]-1 - k)
        amax = min(n - 1, a[i]-1 + k)
        if imin > amax:
            c += imax-imin + 1
        else:
            c += imax-amax
    else:
        c += imax-imin + 1
    ans.append(c)

print(" ".join([str(x) for x in ans]))

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
ans = [0] * n
for i in range(n):
    ans[i] += min(n, i + 1 + k) - max(1, i + 1 - k) + 1
    if a[i] != 0:
        ans[i] += ans[a[i] - 1] - max(0, min(n, a[i] + k) - max(1, i + 1 - k) + 1)
print(*ans)


def read_ints():
    return list(map(int, input().split()))

n_messages, n_visible = read_ints()

refs = read_ints()

NO_REF = -1

# To match indexes in list
refs = [i-1 for i in refs]

read = [0] * n_messages

def messages_seen_at(index):
    return 1 + min(index, n_visible) + min(n_messages - index - 1, n_visible)

def intersection_seen(index, reference):
    if index <= reference:
        print("NOoooooooooo")

    def segment(index):
        return (max(0, index - n_visible), min(reference + n_visible, n_messages - 1))

    a, b = segment(reference)
    c, d = segment(index)

    return max(b - c + 1, 0)

def get_read(index):
    if refs[index] == NO_REF:
        read[index] = messages_seen_at(index)
    else:
        reads_by_ref = read[refs[index]]
        read[index] = reads_by_ref + messages_seen_at(index) - intersection_seen(index, refs[index])
    return read[index]

for i in range(n_messages):
    get_read(i)

print(' '.join(map(str, read)))

n,k=map(int,input().split())
s=list(map(int,input().split()))
ans=[[0] for i in range(n)]
for i in range(len(s)):
    s[i]-=1
for i in range(n):
    l=max(0,i-k)
    r=min(n-1,i+k)
    if s[i]==-1:   
        ans[i]=[r-l+1,r]
    else:    
        ans[i]=[ans[s[i]][0]+(r-l+1)-max(0,ans[s[i]][1]-l+1),r]
for j in range(n):
    print(ans[j][0],end=' ')

        


n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

ans = [min(i - 1, k) + 1 + min(n - i, k) for i in range(1, n + 1)]

# l + 1 + min(n - l, k) - (r - min(r - 1, k)) - число перекрываюихся сообщений

for i in range(1, n + 1):
    a_ = a[i - 1]

    if a_ != 0:
        l, r = sorted([i, a_])

        d1 = ans[a_ - 1]
        d2 = max(0, l + 1 + min(n - l, k) - (r - min(r - 1, k)))

        delta = d1 - d2

        ans[i - 1] += delta

print(' '.join(map(str, ans)))


q,w=map(int,input().split())
a=[0]+list(map(int,input().split()))
s=[0 for i in range(0,q+1)]
def f(q,w,pos):
    d=1
    if w>=pos:
        d+=pos-1
    else:
        d+=w
    if pos>=q-w:
        d+=q-pos
    else:
        d+=w
    return d
def g(q,w,i,j):
    ans=w*2-j+i+1
    if j-w<=0:
        ans-=w-j+1
    if i+w>q:
        ans-=i+w-q
    return ans
    
for i in range(1,q+1):
    if a[i]==0:
        s[i]=f(q,w,i)
    else:
        t=i-a[i]
        if t>2*w:
            s[i]=f(q,w,i)+s[a[i]]
        else:
            s[i]=s[a[i]]+f(q,w,i)-g(q,w,a[i],i)
print(*s[1:])

def main():
    n, k = list(map(int, input().split()))
    b = list(map(int, input().split()))
    a = [0] * n
    for i in range(n):
        l, r = 0, n - 1
        a[i] = 0
        if b[i]:
            l = b[i] + k
            a[i] += a[b[i] - 1]
        l = max(l, i - k)
        r = min(r, i + k)
        if r >= l:
            a[i] += r - l + 1

    print(' '.join(map(str, a)))


main()


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]))

n, k = input().split(' ')
n = int(n)
k = int(k)
arr = input().split(' ')
arr = list(map(lambda x: int(x), arr))

arr_d = [0] * 100005;
arr_d_right = [0] * 100005;

def count(i, k, n):
    # total_count = 0
    # while True:
    if i - k > 0:
        left_ind = i - k
    else:
        left_ind = 0
        
    if i + k < n - 1:
        right_ind = i + k
    else:
        right_ind = n - 1 
        
    #print(arr_d[:n])
    #print(arr_d_right[:n])
    #print('>>>>>')
    next_i = arr[i] - 1
    
    if next_i != -1:
        prev_val = arr_d[next_i]
        #print(left_ind, right_ind)
        if left_ind <= arr_d_right[next_i]:
            left_ind = arr_d_right[next_i] + 1
    else:
        prev_val = 0
        
    arr_d[i] = prev_val + right_ind - left_ind + 1
    arr_d_right[i] = right_ind
    return arr_d[i]
    
res_arr = []
for ind in range(0, len(arr)): 
    res_arr.append(str(count(ind, k, n)))
        
print(' '.join(res_arr))

n, k = map(int, input().split())
mes = list(map(int, input().split()))
ss = [0] * n
def calc(start):
  last = n
  cur = start
  s = 0
  while (cur != 0) and (last > 0):
    if cur <= last:
      s += 1
      s += min(k, cur - 1)
      s += min(k, last - cur)
    else:
      s += max(last - (cur - min(k, cur - 1) - 1), 0)
    
    last = cur - min(k, cur - 1) - 1
    cur = mes[cur - 1]

    if ss[cur - 1] != 0:
      s += max(ss[cur - 1] - max(min(cur + k, n) - last, 0), 0)
      break
    
  ss[start - 1] = s
  return s
    
for i in range(1, len(mes)):
  print(calc(i), end=' ')
print(calc(len(mes)))

from sys import setrecursionlimit
setrecursionlimit(10**6)
n, k = map(int, input().split())
a = list(map(int, input().split()))
save = [[] for i in range(0, len(a)+1)]

def fun(pos):
    if save[pos] == []:
        left = max(pos-1-k, 0)
        right = min(pos+k, len(a))
        if a[pos-1] != 0:
            new_set=fun(a[pos-1])
            if new_set[-1][1]>=left:
                new_set[-1]=(new_set[-1][0],right)
            else:
                new_set.append(tuple([left,right]))
        else:
            new_set=[tuple([left,right])]
        save[pos]=new_set
        return new_set.copy()
    else:
        return save[pos].copy()
def enc(a):
    #print(a)
    z=0
    for i in a:
        z=z+i[1]-i[0]
    return z

for i in range(1, len(a)+1):
    #print(fun(i))
    print(enc(fun(i)),end=' ')


n, k = map(int, input().split())
a = map(int, input().split())
b = [0] * n
for i, p in enumerate(a):
    cur_start = max(0, i - k)
    cur_end = min(n - 1, i + k)
    if p == 0:
        b[i] = cur_end - cur_start + 1
    else:
        p -= 1
        prev_end = min(n-1, p + k)
        if cur_start > prev_end:
            b[i] = b[p] + cur_end - cur_start + 1
        else:
            b[i] = b[p] + cur_end - prev_end

print(' '.join(map(str, b)))

def s(x,y):
    nonlocal k,n
    if x-y-1>=2*k:
        return k+1+min(k,n-x-1)
    elif x-y-1>=k:
        return min(n-x-1,k)+x-y-k
    else:
        return min(n-1,x+k) - min(n-1,y+k)
def search(i):
    nonlocal a,n,k,ans
    if a[i]==-1:
        ans[i] = min(k,i)+min(k,n-i-1)+1
        return min(k,i)+min(k,n-i-1)+1
    else:
      if ans[i]==0:
          ans[i] = search(a[i])+s(i,a[i])
          return search(a[i])+s(i,a[i])
      else:
          return ans[i]

n,k = input().split()
n = int(n)
k = int(k)
ans = []
a = input().split()
for i in range(n):
    a[i] = int(a[i])-1
    ans.append(0)
for i in range(n):
    if ans[i]==0:
        ans[i]=search(i)
for i in range(len(ans)):
    print(ans[i],end = ' ')
    

def read():
    return list(map(int,input().split()))
n,k=read()
a=read()
b=[min(k,n-1)+1]
for i in range(1,n):
    if a[i]==0:
        b.append(min(i,k)+1+min(n-i-1,k))
    else:
        b.append(b[a[i]-1]-min(k,n-a[i])+min(i-a[i],2*k)+min(n-i-1,k)+1)
print(*b)

    
        


def count_unic_mess(crt, display, array, n, result_arr):
    low_bound = 0 if crt - display < 0 else crt - display

    high_bound = n if crt + display + 1 > n else crt + display + 1

    result = high_bound - low_bound

    if array[crt] == 0:
        result_arr.append(result)
        return result

    ref = array[crt] - 1
    high_bound_ref = n if ref + display + 1 > n else ref + display + 1

    if high_bound_ref >= low_bound:
        result += result_arr[ref] - high_bound_ref + low_bound
    else:
        result += result_arr[ref]

    result_arr.append(result)
    return result


n, k = map(int, input().split(' '))

links = [int(x) for x in input().split(' ')]
count_arr = []

for i in range(n):
    print(count_unic_mess(i, k, links, n, count_arr), end=' ')


n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * n
for i in range(n):
  if a[i] == 0:
    b[i] = min(k,i)

for i in range(n):
  if a[i] != 0:
    b[i] = b[a[i]-1] + min(2*k, i - a[i]) + 1
ans = [0] * n

for i in range(n):
  ans[i] = b[i] + min(k, n - i - 1) + 1

print(*ans)

n, k = map(int, input().split())
k = min(k, n - 1)
a = list(map(lambda x: int(x) - 1, input().split()))
kek = [0 for i in range(n)]
ans = [0 for i in range(n)]
for i in range(n):
    if a[i] == -1:
        cur_l = max(0, i - k)
        cur_r = min(i + k, n - 1)
        ans[i] = (i - cur_l) + (cur_r - i) + 1
    else:
        x = ans[a[i]]
        d = (i - a[i] - 1)
        if d >= 2 * k:
            x += min(k, i) + min(k, n - i - 1) + 1
        else:
            o = 0
            cur_l = max(0, i - k)
            cur_r = min(i + k, n - 1)
            his_l = min(0, a[i] - k)
            his_r = min(a[i] + k, n - 1)
            if 2 * k >= d >= k:
                o = d - 2 * (k)
            elif d == k - 1:
                o = (-d - 2)
            else:
                o = (-(his_r - a[i] + 1)) - (a[i] - cur_l)
            #print(d, o, x, i, cur_l, cur_r)
            x += (i - cur_l) + (cur_r - i) + 1 + o
        ans[i] = x
print(' '.join(map(str, ans)))

# python3
# utf-8

def solve():
    n, k = (int(x) for x in input().split())
    idx___parent = [int(x) - 1 for x in input().split()]
    idx___l_cl = [max(0, idx - k) for idx in range(n)]
    idx___r_op = [min(n, idx + k + 1) for idx in range(n)]

    idx___message_count = []
    for idx in range(n):
        curr_l_cl = idx___l_cl[idx]
        curr_r_op = idx___r_op[idx]
        if idx___parent[idx] == -1:
            idx___message_count.append(curr_r_op - curr_l_cl)
            continue
        parent = idx___parent[idx]
        prev_r_op = idx___r_op[parent]
        curr_message_count = idx___message_count[parent]
        if prev_r_op > curr_l_cl:
            curr_l_cl = prev_r_op
        curr_message_count += curr_r_op - curr_l_cl
        idx___message_count.append(curr_message_count)
    print(*idx___message_count)

t = 1
# t = int(input())
for _ in range(t):
    solve()


from math import *
from random import *
from copy import *
import os, sys

n, k = list(map(int, input().split()))
A = list(map(int, input().split()))
res = [0] * (n + 1)

for i in range(1, n + 1):
  prev = A[i - 1]
  res[i] = res[prev]
  prev = prev - k if prev == 0 else prev
  res[i] += min(max(0, i - prev - k - 1), k) + max(0, min(k + 1, n - i + 1) - max(0, min(n - prev + 1, prev + k - i + 1)))
print(' '.join(list(map(str, res[1 :]))))


n, k = (int(s) for s in input().split())
a = [0] + [int(s) for s in input().split()]
ans = [0,]

for i in range(1, n + 1):
    if not a[i]:
        ans.append( min(i - 1, k) + 1 + min(n - i, k) )
    else:
        if a[i] + k < i - k:
            ans.append( min(i - 1, k) + 1 + min(n - i, k) + ans[a[i]] )
        else:
            ans.append( ans[a[i]] + min(n, i + k) - a[i] - min(k, n - a[i]))
    
print(*ans[1:])