Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import copy

H, W = map(int, input().split())
A = [[0 for i in range(W)]for j in range(H)]
white_num = 0
for i in range(H):
    S = input()
    for j in range(W):
        A[i][j] = S[j]
        if A[i][j] == '.':
            white_num += 1

ans = 0
while white_num > 0:
    A_ = copy.deepcopy(A)
    ans += 1
    for y in range(H):
        for x in range(W):
            if A[y][x] == ".":
                continue
            if A[y][x] == "#":
                for k in range(4):
                    nx = x + [1, 0, -1, 0][k]
                    ny = y + [0, 1, 0, -1][k]
                    if nx < 0 or ny < 0 or nx >= W or ny >= W:
                        continue
                    if A[ny][nx] == "#":
                        continue
                    if A[ny][nx] == "." and A_[ny][nx] == ".":
                        A_[ny][nx] = "#"
                        white_num -= 1
    A = A_
print(ans)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
que = deque()
A = [[0 for i in range(W)] for j in range(H)]
white_num = 0
for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == '.':
            A[i][j] = -1
            white_num += 1
        elif S[j] == '#':
            A[i][j] = 0
            que.append([j, i])

ans = 0
while len(que) > 0:
    x, y = que.popleft()
    for k in range(4):
        nx = x + [1, 0, -1, 0][k]
        ny = y + [0, 1, 0, -1][k]
        if nx < 0 or ny < 0 or nx >= W or ny >= H:
            continue
        if A[ny][nx] == -1:
            que.append([nx, ny])
            A[ny][nx] = A[y][x] + 1
            ans = max(ans, A[ny][nx])
print(ans)
### BUGGY CODE ###

#Energy Drink Collector
N, M = map(int, input().strip().split())
A = []
B = []
for n in range(N):
	a, b = map(int, input().strip().split())
	A.append(a)
	B.append(b)
total   = 0
collect = 0
while True:
	min_i = A.index(min(A))
	if collect + B[min_i] < M:
		total += A[min_i]*B[min_i]
		collect += B[min_i]
		del A[min_i]
		del B[min_i]
	else:
		total += A[min_i]*(M - collect)
		collect = M
		break
print(total)	

### FIXED CODE ###

#Energy Drink Collector
N, M = map(int, input().strip().split())

list = [list(map(int, input().strip().split())) for i in range(N)]	
list.sort(key = lambda x : x[0])
sum = 0
cnt = 0
for a, b in list:
	if cnt + b < M:
		sum += a*b
		cnt += b
	else:
		sum += a*(M - cnt)
		break

print(sum)
### BUGGY CODE ###

A,B,K = map(int,input().split())
s = list(set(range(A,B+1))&(set(range(A,A+K))|set(range(B-K+1,B+1))))
for i in sorted(s):
  print(i)

### FIXED CODE ###

A,B,K = map(int,input().split())
if (2*K)<(B-A+2):
  for i in range(A,A+K):
    print(i)
  for i in range(B-K+1,B+1):
    print(i)
else:
  for i in range(A,B+1):
    print(i)
### BUGGY CODE ###

N = int(input())
total = 0
total = sum(range(1, N))
print(total)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

N = int(input())
total = sum(range(1, N))
  
print(total)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

S = min(R, G, B)
L = max(R, G, B)
M = R + G + B - S - L

cnt = 0
sum = 0
for i in range(N // L + 1):
    for j in range(N // M + 1):
        for k in range(N // S + 1):
            sum = N - i * L - j * M - k * S
            if sum == 0:
                cnt += 1
            if sum < 0:
                break
print(cnt)


### FIXED CODE ###

R, G, B, N = map(int, input().split())

S = min(R, G, B)
L = max(R, G, B)
M = R + G + B - S - L

cnt = 0
sum = 0
for i in range(N // L + 1)[::-1]:
    for j in range(N // M + 1):
        sum = N - i * L - j * M
        if sum < 0:
            break
        if sum % S == 0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

R,G,B,N=map(int, input().split())
ans=0
for i in range(N//R+1):
    for j in range((N-i*R)//G+1):
        for k in range((N-i*R-j*G)//B+1):
            if (i*R+j*G+k*B)==N:
                ans +=1
print(ans) 

### FIXED CODE ###

R,G,B,N=map(int, input().split())
ans=0
for i in range(N//R+1):
    for j in range((N-i*R)//G+1):
        if (N-i*R-j*G)%B==0:
            ans+=1
print(ans)
### BUGGY CODE ###

R,G,B,n=map(int,input().split())
i=0
ans=0
while(R*i<=n):
  j=0
  while(R*i+G*j<=n):
    if((n-R*i-G*j)%B==0):
      ans+=1
    j+=1
  i+=1
print(ans)

### FIXED CODE ###

R,G,B,n=map(int,input().split())
i=0
ans=0
for i in range(int(n/R)+1):
  for j in range(int((n-i*R)/G)+1):
    if((n-R*i-G*j)%B==0):
      ans+=1

print(ans)
### BUGGY CODE ###

from copy import deepcopy
import numpy as np
def factor(N):
    ans = []
    for i in range(1,int(np.sqrt(N))+1):
        if N%i == 0:
            ans.append(i)
    for i in range(len(ans)):
        ans.append(N//ans[i])
    ans = list(set(ans))
    return ans

def check(K,N):
    while 1:
        if N%K == 0:
            N = N//K
        else:
            break
    if N%K == 1:
        return True
    else:
        return False

N = int(input())
ans = len(factor(N-1)[1:])
for K in factor(N)[1:]:
    if check(K,N):
        ans += 1

print(ans)            


### FIXED CODE ###

import numpy as np
def factor(N):
    ans = []
    for i in range(1,int(np.sqrt(N))+1):
        if N%i == 0:
            ans.append(i)
            if N//i != i:
                ans.append(N//i)
    return ans

def check(K,N):
    while N >= K:
        if N%K == 0:
            N //= K
        else:
            N %= K
    if N%K == 1:
        return True
    else:
        return False

N = int(input())
ans = len(factor(N-1))-1

for K in factor(N)[1:]:
    if check(K,N):
        ans += 1

print(ans)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    N = int(input())
    K = int(input())

    counter = [0, 0, 0, 0]
    for i in range(1, N+1):
        cnt = len(str(i)) - str(i).count('0')
        if cnt <= 3:
            counter[cnt] += 1
    print(counter[K])


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import bisect, collections, copy, functools, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    K = I()

    # [0, N]で、non0の数字がK個あるものの数
    @functools.lru_cache
    def f(N, K):
        if N == K == 0:
            ret = 1
        elif N > 0 and K >= 0:
            ret = f(N // 10, K) + N % 10 * f(N // 10, K - 1) + (9 - N % 10) * f(N // 10 - 1, K - 1)
        else:
            ret = 0
        return ret
    
    ans = f(N, K)
    print(ans)

if __name__ == '__main__':
    resolve()
### BUGGY CODE ###

import math
r,g,b,n = [int(u) for u in input().split(" ")]
i = 0
for ir in range(math.floor(n/r)+1):
  if ir*r>n:
    break
  for ig in range(math.floor(n/g)+1):
    if ig*g>n:
      break
    y = n- (ir*r+ig*g)
    if y>=0 and y%b==0:
      #print(ir,ig,y/b)
      i+=1
print(i)

### FIXED CODE ###

import math
r,g,b,n = [int(u) for u in input().split(" ")]
i = 0
for ir in range(math.floor(n/r)+1):
  if ir*r==n:
    i+=1
    break
  elif ir*r>n:
    break
  for ig in range(math.floor(n/g)+1):
    y = n - (ir*r+ig*g)
    if y<0:
      break
    if y%b==0:
      #print(ir,ig,y/b)
      i+=1
      continue
print(i)
### BUGGY CODE ###

N, Q = map(int, input().split())
dic = {}
amari = {}
for i in range(N-1):
  k, v = map(int, input().split())
  try:
    dic[k].append(v)
  except KeyError:
    dic[k] = [v]
  try:
    amari.pop(k)
  except:
    pass
  amari[v] = None
for i in amari.keys():
  dic[i] = []
counter = [list(map(int, input().split())) for i in range(Q)]
q = {i: 0 for i in dic.keys()}
 
def child_sum(q,v, child):
  if child == []:
    return q
  else:
    for j in child:
      q[j] += v
      child = dic[j]
      q = child_sum(q, v, child)
  return q
    
for i, v in counter:
  q[i] += v
  child = dic[i]
  #print(q, i, child)
  q = child_sum(q, v, child)
print(' '.join([str(i) for i in q.values()]))

### FIXED CODE ###

N, Q = map(int, input().split())
edge = [[] for i in range(N)]
q = [0 for i in range(N)]
 
for i in range(N-1):
  a, b = map(int, input().split())
  edge[a-1].append(b)
for i in range(Q):
  a, v = map(int, input().split())
  q[a-1] += v
 
for i, v in enumerate(q):
  #print(i, v)
  for j in edge[i]:
    #print(j)
    q[j-1] += v
print(*q)
### BUGGY CODE ###

a, b, x = map(int, input().split())
count = 0
for i in range(a, b+1):
    if i % x ==0:
        count += 1
print(count)        

### FIXED CODE ###

a, b, x = map(int, input().split())
ans = b//x - (a-1)//x
print(ans)
### BUGGY CODE ###

from fractions import gcd
 
def primeNum(n):
  ans = 1
  if n == 1:
    return ans
  if n % 2 == 0:
    ans += 1
    while n % 2 == 0:
      n = n // 2
  if n == 1:
    return ans
  for k in range(3, n+1, 2):
    if n % k == 0:
      ans += 1
      while n % k == 0:
        n = n // k
    if n == 1:
      return ans
  return ans
 
a,b = list(map(int, input().split()))
n=gcd(a,b)
print(primeNum(n))

### FIXED CODE ###

from fractions import gcd
 
def primeNum(n):
  ans = 1
  if n == 1:
    return ans
  if n % 2 == 0:
    ans += 1
    while n % 2 == 0:
      n = n // 2
  for k in range(3, int(n**0.5)+1, 2):
    if n % k == 0:
      ans += 1
      while n % k == 0:
        n = n // k
    if n == 1:
      return ans
  if n != 1:
    ans += 1
  return ans
  
a,b = list(map(int, input().split()))
n=gcd(a,b)
print(primeNum(n))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import bisect
import sys
input=sys.stdin.readline
n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))
ans='NO'
d.sort()
for i in range(m):
    if d[bisect.bisect_right(d,t[i])-1]==t[i]:
        d.remove(t[i])
        if i==m-1:
            ans='YES'
    else:
        break
print(ans)


### FIXED CODE ###

from collections import Counter
n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))

d_c=Counter(d)
t_c=Counter(t)
for i in t_c.keys():
    if t_c[i]>d_c[i]:
        print('NO')
        exit()
print('YES')
### BUGGY CODE ###

##C - Step(TLE)
N = int(input())
A = list(map(int,input().split()))
ans = 0
for i in range(N):
    ##print(i,A)
    if A != []:
        maxi = max(A)
        Idx = A.index(maxi)
        ans += maxi*(len(A) - Idx) - sum(A[Idx::])
        del A[Idx::]
    else:
        break
print(ans)

### FIXED CODE ###

##C - Step(TLE)
N = int(input())
A = list(map(int,input().split()))
ans = 0
maxi = 0
for i in A:
    ans += max(0,maxi-i)
    maxi = max(maxi,i)
print(ans)
### BUGGY CODE ###

import numpy as np
from sys import stdin
input = stdin.readline
N = int(input())
A = list(map(int, input().split()))
number = np.zeros(N, dtype = int)
for i in range(N):
  number[i] = A.count(i + 1)
total = 0
for k in range(N):
  tmp = number[k]
  total += tmp * (tmp-1) // 2
for j in range(N):
  print(total - number[A[j]-1] + 1)


### FIXED CODE ###

import numpy as np
from sys import stdin
input = stdin.readline
N = int(input())
A = list(map(int, input().split()))
number = np.zeros(N, dtype = int)
total = 0

dic = {}
a = sorted(A)
now_key = a[0]
value = 1
dic[now_key] = 1
for i in range(1,N):
  if a[i] == now_key:
    value += 1
  else:
    dic[now_key] = value
    if value >= 2:
      total += value * (value-1) // 2
    now_key = a[i]
    value = 1
dic[now_key] = value
if value >= 2:
  total += value * (value-1)//2
for j in A:
  print(total - dic[j] + 1)
### BUGGY CODE ###

import math
import itertools

N, K = map(int, input().strip().split())
L = math.pow(10, 10)

values = [0] * (N + 1)
for i in range(N + 1):
    values[i] = i

amount = 0
each_combination = []
for comb_no in range(K, N + 2):
    possible_values = set()
    for combination in itertools.combinations(values, comb_no):
        possible_values.add(sum(combination))
    each_combination.append(len(possible_values))
print(sum(each_combination))

### FIXED CODE ###

import math
import itertools

N, K = map(int, input().strip().split())

all_combination = 0
for num in range(K, N + 2): # 選ぶ個数を1 から N + 1個までずらす
    min = (0 + num - 1) * num / 2
    max = (N - (num - 1) + N) * num / 2
    possiblility = (int(max) - int(min) + 1)
    all_combination += possiblility

print(all_combination % (1000000007))
### BUGGY CODE ###

k, s = map(int, input().split())

ans = 0
for x in reversed(range(k+1)):
    for y in reversed(range(k+1)):
        for z in reversed(range(k+1)):
            if x+y+z == s:
                ans += 1
                break
            elif x+y+z < s:
                break
print(ans)

### FIXED CODE ###

k, s = map(int, input().split())

ans = 0
for x in reversed(range(k+1)):
    for y in reversed(range(k+1)):
        if s-(x+y) >= 0 and s-(x+y) <= k:
            ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())
X = tuple(map(int, input().split()))
 
Y = X[::-1]
 
li = set(range(N))
 
for k in li:
    try:
        i = Y.index(k+1)
        Y = Y[:i]
    except:
        i = -1
        leng = k
        break
    leng = k + 1

if leng == 0:
    ans = -1
else:
    ans = N - leng
print(ans)

### FIXED CODE ###

N = int(input())
X = tuple(map(int, input().split()))

c = 0
for x in X:
    if x == c+1:
        c+=1
if c == 0:
    ans = -1
else:
    ans = N-c
print(ans)
### BUGGY CODE ###

def main():
    N,K = map(int, input().split())
    h = list(map(int, input().split()))
    # 初期化
    # 初期条件
    # ループ
    # テーブルから解を得る
    INF = float('inf')
    dp = [INF] * N
    dp[0] = 0
    for i in range(N-1):
        t = min(K+1, N-i)
        for j in range(1, t):
            dp[i+j] = min(dp[i+j], dp[i]+abs(h[i+j]-h[i]))
    print(dp[-1])

main()


### FIXED CODE ###

def main():
    N,K = map(int, input().split())
    h = list(map(int, input().split()))
    # 初期化
    # 初期条件
    # ループ
    # テーブルから解を得る
    INF = float('inf')
    dp = [INF] * N
    dp[0] = 0
    for i in range(N-1):
        for j in range(1, min(K+1, N-i)):
            dp[i+j] = min(dp[i+j], dp[i]+abs(h[i+j]-h[i]))
    print(dp[-1])

main()
### BUGGY CODE ###

a,b,x=map(int,input().split())
ans=0

for i in range(a,b+1):
    if i%x==0:
        ans+=1
print(ans)

### FIXED CODE ###

a,b,x=map(int,input().split())

bb=b//x
aa=(a-1)//x
print(bb-aa)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
import time

def bfs(graph,N,s,t):
    start=time.time()
    S=[s]
    visited=set()
    distance={(i+1,j):0 for i in range(N) for j in range(3)}
    while len(S)>0:
        if time.time()-start==1.7:
            return False,-1
        v=S.pop(0)
        if v==t:
            return True,distance[v]+1
        if v not in visited:
            visited.add(v)
            for w in graph[v]:
                distance[w] = distance[v]+1
                S.append(w)
    return False,-1
if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    E=[list(map(int,input().split())) for _ in range(M)]
    S,T=list(map(int,input().split()))
    graph={(i+1,j):[] for i in range(N) for j in range(3)}
    for e in E:
        graph[(e[0],0)].append((e[1],1))
        graph[(e[0],1)].append((e[1],2))
        graph[(e[0],2)].append((e[1],0))
    flag,ans=bfs(graph,N,(S,0),(T,0))

    if flag:
        print(ans//3)
    else:
        print(-1)

### FIXED CODE ###

import sys
input=sys.stdin.readline
import heapq

def dijkstra(graph,N,s):
    distance = {(i + 1, j): 1e7 for i in range(N) for j in range(3)}
    distance[s]=0
    q=[]
    heapq.heappush(q,(distance[s],s))
    while len(q)>0:
        cost,v=heapq.heappop(q)
        if cost>distance[v]:
            continue
        else:
            for w in graph[v]:
                if distance[w]>distance[v]+1:
                    distance[w]=distance[v]+1
                    heapq.heappush(q,(distance[w],w))
    return distance


if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    E=[list(map(int,input().split())) for _ in range(M)]
    S,T=list(map(int,input().split()))
    graph={(i+1,j):[] for i in range(N) for j in range(3)}
    for e in E:
        graph[(e[0],0)].append((e[1],1))
        graph[(e[0],1)].append((e[1],2))
        graph[(e[0],2)].append((e[1],0))
    distance=dijkstra(graph,N,(S,0))
    d=distance[(T,0)]
    if d%3==0:
        print(d//3)
    else:
        print(-1)
### BUGGY CODE ###


N,Q=map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N-1)]
PQ = [list(map(int,input().split())) for _ in range(Q)]
AB.sort()
PQ.sort()
l=[[] for _ in range(N)]
ans=[0]*N
for a,b in AB:
	l[a-1].append(b-1)
for p,q in PQ:
	ans[p-1]+=q
for i in range(N-1):
	for j in l[i]:
		ans[j]+=ans[i]
	
print(*ans)

### FIXED CODE ###


N,Q=map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N-1)]
PQ = [list(map(int,input().split())) for _ in range(Q)]
#AB.sort()
#PQ.sort()
l=[[] for _ in range(N)]
ans=[0]*N
for a,b in AB:
	l[a-1].append(b-1)
for p,q in PQ:
	ans[p-1]+=q
for i in range(N-1):
	for j in l[i]:
		ans[j]+=ans[i]
	
print(*ans)
### BUGGY CODE ###

def knapsack(n,w):
    global weight,value,bag
    if(n==0 or w==0):
        return 0
    if(bag[n][w]!=-1):
        return bag[n][w]
    if(weight[n-1]<=w):
        bag[n][w]=max(value[n-1] + knapsack(n-1,w-weight[n-1]),knapsack(n-1,w))
        return bag[n][w]
    else:
        bag[n][w]=knapsack(n-1,w)
        return bag[n][w]
n,w=map(int,input().split())
weight=[]
value=[]
bag=[[-1 for j in range(w+1)] for i in range(n+1)]
for _ in range(n):
    tempw,tempv=map(int,input().split())
    weight.append(tempw)
    value.append(tempv)
temp=knapsack(n,w)
print(temp)


### FIXED CODE ###

import array
n,w=map(int,input().split())
weight=[]
value=[]
for _ in range(n):
    tempw,tempv=map(int,input().split())
    weight.append(tempw)
    value.append(tempv)
t=[[0 for i in range(n+1)] for j in range(w+1)]
for i in range(1,w+1):
    for j in range(1,n+1):
        if(weight[j-1]<=i):
            t[i][j]=max(value[j-1]+t[i-weight[j-1]][j-1],t[i][j-1])
        else:
            t[i][j]=t[i][j-1]
print(t[-1][-1])
### BUGGY CODE ###

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

x = 0

for i in range(0, n - 1):
    for j in range(i + 1, n):

        x += (k[i] * k[j]) % (10 ** 9 + 7)

        if x < 10 ** 9 + 7:
            continue
        else:
            x = x % (10 ** 9 + 7)

print(x)

### FIXED CODE ###

mod = 10 ** 9 + 7

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

s = sum(a) 

ans = 0

for i in a:
    s -= i
    s %= mod
    ans += i * s
    ans %= mod

print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()

count = [0] * N

for i in range(N-1):
	
	if S[i] == 'A' and S[i+1] == 'C':
		count[i] = 1


for i in range(Q):
	l, r = map(int, input().split())
	l -= 1; r -= 1
	
	res = count[l:r].count(1)
	print(res)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

count = [0] * N

for i in range(N-1):
	
	if S[i] == 'A' and S[i+1] == 'C':
		count[i] = 1

accum = count.copy()
for i in range(1, N):
	accum[i] += accum[i-1]

for i in range(Q):
	l, r = map(int, input().split())
	l -= 1; r -= 1;
	if l == 0:
		res = accum[r]
	else:
		res = accum[r] - accum[l-1]
	if count[r] == 1:
		res -= 1
	print(res)
### BUGGY CODE ###

n = int(input())
d = list(map(int,input().split()))
d.sort()
m = int(input())
t = list(map(int,input().split()))
t.sort()
for x in d:
    if x == t[0]:
        t.pop(0)
    if len(t)==0:
        break
if len(t)==0:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

from itertools import accumulate
from math import*
from collections import deque
from collections import defaultdict
from itertools import permutations
from heapq import*
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

input()
d = Counter(map(int,input().split()))
input()
t = Counter(map(int,input().split()))
d.subtract(t)
if -d:
    print("NO")
else:
    print("YES")
### BUGGY CODE ###

S = input()
S = S[::-1]

# i~nまでの値をmod2019したときの数
ls = [0for i in range(2019)]

# 0文字の時
ls[0] += 1

x = 0
pow10 = 1
count = 0
for i in range(len(S)):
    x += int(S[i])*pow10
    count += ls[x%2019]
    ls[x%2019] += 1
    pow10 *= 10

# for x in ls:
#     count += x*(x-1)/2

print(int(count))



### FIXED CODE ###

S = input()
digits = list(map(int,S))
# S = S[::-1]→これが時間かかる

# i~nまでの値をmod2019したときの数
# ls = [0for i in range(2019)]
ls = [0] * 2019

# 0文字の時
ls[0] += 1

x = 0
pow10 = 1
count = 0
for i in reversed(digits):
    x += i*pow10
    x %= 2019
    count += ls[x]
    ls[x] += 1
    pow10 *= 10
    pow10 %= 2019

# for x in ls:
#     count += x*(x-1)/2

print(int(count))
### BUGGY CODE ###

import sys
#import copy
#import math
#import bisect
import numpy as np
#import itertools
#import collections
#from collections import deque
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix
#import functools

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
#read = sys.stdin.buffer.read

def main():
    N, K = map(int, readline().split())
    A = np.array(readline().split(), dtype=np.int64)
    for i in range(K):
        B = np.zeros(N, dtype=np.int64)
        for j in range(N):
            st = max(0, j - A[j])
            ed = j + A[j] + 1
            B[st:ed] += 1
        #print(B)
        if np.all(B == N):
            A = B
            break
        A = B
    print(*A)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import itertools

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

def main():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    
    K = min(50, K)
    for i in range(K):
        B = [0]*N
        for j in range(N):
            st = max(0, j - A[j])
            ed = j + A[j] + 1
            B[st] += 1
            if ed < N:
                B[ed] -= 1
        Bcum = itertools.accumulate(B)
        A = list(Bcum)
    print(*A)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

from collections import deque
h, w = map(int, input().split())
grid = []
graph = [[2000 for i in range(w)] for j in range(h)]
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False

#graph => そこまでの距離を保存した二次元配列　grid=>与えられた迷路
def bfs(que):
    finished = set()
    while que:
        x , y, cost = que.popleft()
        if (grid[y][x] == '#' and cost != 0):
            continue
        if (x,y) not in finished and graph[y][x] > cost:
            finished.add((x,y))
            graph[y][x] = cost
            if check(y,x+1):
                que.append([x+1,y,cost+1])
            if check(y+1,x):
                que.append([x, y+1, cost+1])
            if check(y,x-1):
                que.append([x-1,y,cost+1])
            if check(y-1,x):
                que.append([x,y-1,cost+1])
for i in range(h):
    grid.append(list(input()))
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            que = deque([(j,i,0)])
            bfs(que)
ans = 0
for i in range(h):
    ans = max(ans, max(graph[i]))
print(ans)

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
grid = []
graph = [[2000 for i in range(w)] for j in range(h)]
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False

#graph => そこまでの距離を保存した二次元配列　grid=>与えられた迷路
def bfs(que):
    finished = set()
    while que:
        x ,y = que.popleft()
        if y*w+x not in finished:
            finished.add(y*w+x)
            for n_x,n_y in [(x+1,y),(x,y+1),(x-1,y),(x,y-1)]:
                if check(n_y,n_x) and graph[n_y][n_x] > graph[y][x] + 1:
                    graph[n_y][n_x] = graph[y][x] + 1
                    que.append((n_x,n_y))
for i in range(h):
    grid.append(list(input()))
que = deque()
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            graph[i][j] = 0
            que.append((j,i))
bfs(que)
ans = 0
for i in range(h):
    ans = max(ans, max(graph[i]))
print(ans)