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

def main():
    import collections

    H, W, M_ko = map(int, input().split())

    zahyou = [[0 for i in range(W)] for j in range(H)]
    zahyou_H = [0 for i in range(H)]
    zahyou_W = [0 for i in range(W)]

    for i in range(M_ko):
        height, width = map(int, input().split())

        zahyou[height - 1][width - 1] = 1
        
        zahyou_H[height - 1] += 1
        zahyou_W[width - 1] += 1

    CTR_H = collections.Counter(zahyou_H)
    CTR_W = collections.Counter(zahyou_W)

    max_h = max(zahyou_H)
    max_w = max(zahyou_W)

    len_h = CTR_H[max_h]
    len_w = CTR_W[max_w]

    index_h = [i for i, x in enumerate(zahyou_H) if x == max_h]
    index_w = [i for i, x in enumerate(zahyou_W) if x == max_w]


    maxi = max_h + max_w
    FLAG = False


    if (len_h == 1 and len_w == 1):    
        maxi -= zahyou[index_h[0]][index_w[0]]


    else:
        for i in range(len_h):        
            for j in range(len_w):
                val = zahyou[index_h[i]][index_w[j]]
                
                if (val == 0):
                    FLAG = True
                    break
        
        if (not FLAG):
            maxi -= 1

    print(maxi)
    # print(zahyou_H, zahyou_W)
    # print(index_h,index_w)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np
import numba
import sys
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


@njit((i8, i8, i8[:]), cache=True)
def main(Height, Width, XY):
    UP = 300010
    row = np.zeros(UP, np.int64)
    col = np.zeros(UP, np.int64)
    
    for i in range(0, len(XY), 2):
        x, y = XY[i:i + 2] - 1
        row[x] += 1
        col[y] += 1
    
    row_max = row.max()
    col_max = col.max()

    judge = np.sum(row == row_max) * np.sum(col == col_max)

    for i in range(0, len(XY), 2):
        x, y = XY[i:i + 2] - 1
        
        if (row[x] == row_max and col[y] == col_max):
            judge -= 1
    
    summ = row_max + col_max
    
    return (summ if judge else summ - 1)


Height, Width, M_ko = map(int, readline().split())
XY = np.array(read().split(), np.int64)

ans = main(Height, Width, XY)
print(ans)
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))
count = 0
for i in range(n):
  for k in range(i):
    if p[k]<p[i]:
      break
  else:
    count += 1
print(count)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
count = 0
min = n+1
for i in range(n):
  if min > p[i]:
    count += 1
    min = p[i]
print(count)
### BUGGY CODE ###

# B - Multiplication 2

import sys
readline = sys.stdin.readline

N = int(readline())
A = list(int(x) for x in readline().split())

ans = 1
for a in A:
    ans *= a

if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

# B - Multiplication 2

import sys
readline = sys.stdin.readline

N = int(readline())
A = list(int(x) for x in readline().split())
A.sort()

ans = 1
for a in A:
    ans *= a
    if ans == 0:
        break
    if ans > 10**18:
        break

if ans > 10**18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
N,M=map(int,input().split())
#dab={}
lab=[]
for i in range(N):
    a,b=map(int,input().split())
    #dab[a]=b
    lab.append([a,b])
#dab.sort(key=lambda )
lab.sort(key=lambda x:-x[1])
#print("lab",lab)
#lsch=[-1]*M#ミスしてた#やっぱおk_どうせM番目には入らない
#lsch=[M-1-i for i in range(M)]
dsch={i:0 for i in range(M)}
ans=0
for ab in lab:
    if ab[0]<=M:
        d=M-ab[0]
        #while d>=0:
        #for i in range(d,-1,-1):
        #    if lsch[i]==-1:#whileから書き直したときiではなくdのままにしていた
        #        lsch[i]=1
        #        ans+=ab[1]
        #        #print("ab",ab)
        #        break
            #d-=1
        #while d>=0:
        for i in range(d,-1,-1):
            if i in dsch:
                ans+=ab[1]
                #print("ab",ab)
                del dsch[i]
                break
#print("lsch",lsch)
#print("dsch",dsch)
print(ans)


### FIXED CODE ###

import heapq
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
lab=[]
for i in range(N):
    llab=list(map(int,input().split()))
    lab.append(llab)
lab.sort(key=lambda ab:ab[0])
hq=[]
ind=0
ans=0
#print(lab)
#c=0
for i in range(M):
    if hq:
            ans-=heapq.heappop(hq)
    for j in range(ind,N):
        #if f==0:
        #print(i,j,lab[j][0])
        if lab[j][0]==i+1:
            heapq.heappush(hq,-lab[j][1])#
        else:
            ind=j
            #j=N-1#これダメ、抜けられていない
            break
        #c+=1
    #if hq:
    #        ans-=heapq.heappop(hq)
    #print(hq)
#print(c)
if hq:
    ans-=heapq.heappop(hq)
print(ans)
#for i in range(3):
#    i=3
#    print(12345)
### BUGGY CODE ###

from collections import Counter
H, W, M = [int(i) for i in input().split()]
g = [0] * M
h = [0] * M
w = [0] * M
for i in range(M):
    h[i], w[i] = [int(j) for j in input().split()]
    g[i] = [h[i],w[i]]

ch = Counter(h)
cw = Counter(w)

chm = max(ch.values())
cwm = max(cw.values())
hi = [i for i in ch.keys() if ch[i] == chm]
wi = [i for i in cw.keys() if cw[i] == cwm]

for i in hi:
    for j in wi:
        if [i,j] not in g:
            print(ch[i] + cw[j])
            exit()
print(ch[hi[0]] + cw[wi[0]] - 1)

### FIXED CODE ###

from collections import Counter
H, W, M = [int(i) for i in input().split()]
g = set()
h = [0] * M
w = [0] * M
for i in range(M):
    h[i], w[i] = [int(j) for j in input().split()]
    g.add((h[i],w[i]))

ch = Counter(h)
cw = Counter(w)

chm = max(ch.values())
cwm = max(cw.values())
hi = [i for i in ch.keys() if ch[i] == chm]
wi = [i for i in cw.keys() if cw[i] == cwm]

for i in hi:
    for j in wi:
        if (i,j) not in g:
            print(ch[i] + cw[j])
            exit()
print(ch[hi[0]] + cw[wi[0]] - 1)
### BUGGY CODE ###

import heapq
INF = float('inf')
yen = 10**15
def pcc(src, adj):
	pq = [(0,src)]
	heapq.heapify(pq)
	dist = [INF]*(n+1)
	dist[src] = 0
	while pq:
		d,u = heapq.heappop(pq)
		if d>dist[u]:continue
		for w, v in adj[u]:
			if dist[v] > dist[u] + w:
				dist[v] = dist[u] + w
				heapq.heappush(pq, (dist[v], v))
	return dist

n,m,s,t = (int(i) for i in input().split())
adjs = [[] for _ in range(n+1)]
adjt = [[] for _ in range(n+1)]
for _ in range(m):
	u,v,a,b = map(int, input().split())
	adjs[u].append([a,v])
	adjs[v].append([a,u])
	adjt[u].append([b,v])
	adjt[v].append([b,u])

dist_s = pcc(s,adjs)
dist_t = pcc(t,adjt)
ans = [0]*(n)
ans[n-1] = yen -dist_s[n] - dist_t[n]
for i in range(n-2,-1,-1):
	ans[i] = max(ans[i+1], yen - dist_s[i+1] - dist_t[i+1])
print(*ans, sep = '\n')


### FIXED CODE ###

import heapq
def dijkstra(s, neighbor):
	dist = [float('inf')] * N
	dist[s] = 0
	que = [(0, s)]
	heapq.heapify(que)
	while que:
		d, v = heapq.heappop(que)
		if d > dist[v]:
			continue
		for u, l in neighbor[v]:
			tmp_d = d + l
			if tmp_d < dist[u]:
				dist[u] = tmp_d
				heapq.heappush(que, (tmp_d, u))
	return dist
 
N, M, s, t = map(int, input().split())
yen = [[] for _ in range(N)]
snuuk = [[] for _ in range(N)]
for _ in range(M):
	u, v, a, b = map(int, input().split())
	yen[u-1].append((v-1, a))
	yen[v-1].append((u-1, a))
	snuuk[u-1].append((v-1, b))
	snuuk[v-1].append((u-1, b))
 
dist_s = dijkstra(s-1, yen)
dist_t = dijkstra(t-1, snuuk)
ans = [-1] * N
tmp = float('inf')
for i in range(N-1, -1, -1):
	if dist_s[i] + dist_t[i] < tmp:
		tmp = dist_s[i] + dist_t[i]
	ans[i] = 10 ** 15 - tmp
print(*ans, sep='\n')
### BUGGY CODE ###

# This program computes GCD and LCM
# -*- coding: utf-8
import sys


def gcd(a, b):
    for i in range(max([a, b]), 0, -1):
        if(a % i == 0 and b % i == 0):
            return i
    return 1


def lcm(a, b):
    for i in range(max([a, b]), a*b + 1):
        if(i % a == 0 and i % b == 0):
            return i
    return a*b


for i in sys.stdin:
    try:
        line = [int(k) for k in i.split(" ")]
        g = gcd(line[0], line[1])
        print(str(g) + " " + str(line[0]*line[1]//g))  # + str(lcm(line[0], line[1]))
    except:
        exit()

### FIXED CODE ###

# This program computes GCD and LCM
# -*- coding: utf-8
import sys


def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


for i in sys.stdin:
    try:
        line = [int(k) for k in i.split(" ")]
        g = gcd(min(line), max(line))
        print(str(g) + " " + str(line[0]*line[1]//g))
    except:
        exit()
### BUGGY CODE ###

from collections import deque

N,M=map(int,input().split())
A=[int(_) for _ in input().split()]

for m in range(M):
    a=max(A)
    A.remove(a)
    A.append(a//2)
print(sum(A))

### FIXED CODE ###

import heapq

N,M=map(int,input().split())
A=[-int(_) for _ in input().split()]
heapq.heapify(A)

for _ in range(M):
    a=heapq.heappop(A)
    heapq.heappush(A,-((-a)//2))

print(-sum(A))
### BUGGY CODE ###

from heapq import heappush, heappop

H,N = map(int,input().split())

AB = [tuple(map(int,input().split())) for _ in range(N)]

cost = [float('inf')]*(H+1)

q = [(0, 0)]

while q:
    c, t = heappop(q)
    if cost[t] <= c:
        continue
    cost[t] = c
    if t == H:
        break
    for a,b in AB:
        d = min(H,t+a)
        if cost[d] > c+b:
            heappush(q, (c+b, d))

print(cost[H])

### FIXED CODE ###

min2 = lambda x,y: x if x < y else y
H,N = map(int,input().split())


dp = [float('inf')]*(H+1)
dp[0] = 0

for _ in range(N):
    a,b = map(int,input().split())
    for i,v in enumerate(dp):
        j = min2(H,i+a)
        dp[j] = min2(dp[j],v+b)

print(dp[-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from itertools import combinations
from collections import Counter
import math

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))
#-----

A_cnt = Counter(A_list)

A_sum_of_combination={}
for k,v in A_cnt.items():
    # 個数2で場合分け
    if v >= 2:
        A_sum_of_combination[k] = math.factorial(v) // (math.factorial(v - 2) * math.factorial(2))
    else:
        A_sum_of_combination[k] = 0
    
sum_all = sum( [ v for k,v in A_sum_of_combination.items()] )

for i in A_list:
    num_selected = A_cnt[i] - 1
    
    if num_selected >= 2:
        cnt_selected = math.factorial(num_selected) // (math.factorial(num_selected - 2) * math.factorial(2))
        ans = sum_all - A_sum_of_combination[i] + cnt_selected
        print(ans)
    else:
        ans = sum_all - A_sum_of_combination[i]
        print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import combinations
from collections import Counter
import math

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))
#-----

A_cnt = Counter(A_list)

A_sum_of_combination={}
A_sum_of_combination_minus1={}
for k,v in A_cnt.items():
    # 個数2で場合分け
    if v >= 2:
        tmp_sum=1
        for i in range(2):
            tmp_sum *= (v-i)/(i+1)
        
        A_sum_of_combination[k] = int(tmp_sum)
        
    else:
        A_sum_of_combination[k] = 0
    
    if (v-1) >= 2:
        tmp_sum=1
        for i in range(2):
            tmp_sum *= ((v-1)-i)/(i+1)
        
        A_sum_of_combination_minus1[k] = int(tmp_sum)
        
    else:
        A_sum_of_combination_minus1[k] = 0

sum_all = sum( [ v for k,v in A_sum_of_combination.items()] )

for i in A_list:
    num_selected = A_cnt[i] - 1
    
    if num_selected >= 2:
        ans = sum_all - A_sum_of_combination[i] + A_sum_of_combination_minus1[i]
        print(ans)
    else:
        ans = sum_all - A_sum_of_combination[i]
        print(ans)
### BUGGY CODE ###

import gc

MOD = (10 ** 9) + 7

S = input()
N = len(S)

dp = [[0] * (N + 1) for _ in range(4)]

dp[0][0] = 1
dp[1][0] = 0
dp[2][0] = 0
dp[3][0] = 0

for i in range(1, N + 1):
    gc.collect()
    for j in range(4):
        s = S[i - 1]
        m = 3 if s == "?" else 1
        dp[j][i] += m * dp[j][i - 1]
        if j == 1:
            if s == "A" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        elif j == 2:
            if s == "B" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        elif j == 3:
            if s == "C" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        dp[j][i] = dp[j][i] % MOD 

print(dp[3][N] % MOD)


### FIXED CODE ###

import gc

MOD = (10 ** 9) + 7

S = input()
N = len(S)

dp = [[0] * (N + 1) for _ in range(4)]

dp[0][0] = 1
dp[1][0] = 0
dp[2][0] = 0
dp[3][0] = 0

for i in range(1, N + 1):
    for j in range(4):
        s = S[i - 1]
        m = 3 if s == "?" else 1
        dp[j][i] += m * dp[j][i - 1]
        if j == 1:
            if s == "A" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        elif j == 2:
            if s == "B" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        elif j == 3:
            if s == "C" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        dp[j][i] = dp[j][i] % MOD

print(dp[3][N] % MOD)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
num_list = list()

for i in range(q):
    l,r = map(int,input().split())
    num_list.append(s[l-1:r].count("AC"))
    
for i in num_list:
    print(i)

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
num_list = list()
#０文字目と１文字目はACの数０
ruisekiwa_tabun_rikaidekita = [0,0]

for i in range(q):
    num_list.append(list(map(int,input().split())))

for i in range(n-1):
    if s[i:i+2] == "AC":
        ruisekiwa_tabun_rikaidekita.append(ruisekiwa_tabun_rikaidekita[-1] + 1)
    else:
        ruisekiwa_tabun_rikaidekita.append(ruisekiwa_tabun_rikaidekita[-1])
        
for left,right in num_list:
    print(ruisekiwa_tabun_rikaidekita[right] - ruisekiwa_tabun_rikaidekita[left])
### BUGGY CODE ###

x = int(input())
ans = 1
for i in range(2,34):
    j = 2
    while True:
        if i**j>x:
            break
        ans = max(ans,i**j)
print(ans)


### FIXED CODE ###

x = int(input())
ans = 1
for i in range(2,34):
    j = 2
    while True:
        if i**j>x:
            break
        ans = max(ans,i**j)
        j += 1
print(ans)
### BUGGY CODE ###

n = int(input(''))
adl = input('')

a = list(map(int,adl.split(' ')))

number = 0

mod = 1000000007

amari = 0

for i in range(n):
    aa = 0
    for e in range(n-i-1):
        j = i+e+1
        if i != j:
            aa = aa + a[j]
    number = number + ((a[i] % mod) * aa)
    number = number % mod
amari = number % mod
print(amari)


### FIXED CODE ###

n = int(input(''))
adl = input('')

a = list(map(int,adl.split(' ')))

number = 0

mod = 1000000007

amari = 0

all_a = 0

for i in range(n):
    all_a = all_a + a[i]

for i in range(n):
    all_a = all_a - a[i]
    number = number + (a[i] * all_a)
    number = number % mod
amari = number % mod
print(amari)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# from collections import deque
import bisect

N, M = map(int, input().split())
A_list = list(map(int, input().split()))
A_list.sort()
# A_list = deque(A_list)

ans = 0
ans += sum(A_list[0:N - M])
del(A_list[0:N - M])
for i in range(M):
    max_price = A_list.pop()
    bisect.insort(A_list, max_price // 2)
    

ans += sum(A_list)
print(ans)

### FIXED CODE ###

# D 終了後再チャレンジ
# -*- coding: utf-8 -*-
import heapq

N, M = map(int, input().split())
A_list = list(map(int, input().split()))
A_list = [-a for a in A_list]
heapq.heapify(A_list)

for i in range(M):
    max_price = heapq.heappop(A_list) * (-1)
    heapq.heappush(A_list, max_price // 2 * (-1))
    
ans = sum(A_list) * (-1)
print(ans)
### BUGGY CODE ###

r1,c1,r2,c2 = map(int,input().split())

n = [1]*(r2+c2+1)
mod = 10**9 + 7
for i in range(r2+c2):
    n[i+1] = (n[i]*((i+1)%mod))%mod
    
def calc(r,c):
    x = n[r+c]%mod
    y = (n[r]*n[c])%mod
    return (x*(pow(y,mod-2,mod)%mod))%mod

ans = 0
for i in range(r1,r2+1):
    for j in range(c1,c2+1):
        ans += calc(i,j)
        ans %= mod
        
print(ans)

### FIXED CODE ###

r1,c1,r2,c2 = map(int,input().split())

n = [1]*(r2+c2+3)
mod = 10**9 + 7
for i in range(r2+c2+2):
    n[i+1] = (n[i]*((i+1)%mod))%mod

def calc(r,c):
    x = n[r+c]%mod
    y = (n[r]*n[c])%mod
    return (x*(pow(y,mod-2,mod)%mod))%mod

ans = calc(r2+1,c2+1)-calc(r2+1,c1)-calc(r1,c2+1)+calc(r1,c1)
ans %= mod

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

n = int(input())
As = list(map(int, input().split()))
sunuke = 0
anslist = []

for i in range(n-1):
  sunuke += As[i]
  arai = sum(As) - sunuke
  
  anslist.append(abs(sunuke-arai))

print(min(anslist))

### FIXED CODE ###

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

snk = a[0]
ari = sum(a)-snk
ans = abs(snk-ari)
for i in range(n-2):
    snk += a[i+1]
    ari -= a[i+1]
    ans = min(ans, abs(snk-ari))
print(ans)
### BUGGY CODE ###

from collections import deque
import math

H, W = map(int, input().split())
C = [list(input()) for _ in range(H)]

move = ((1, 0), (-1, 0), (0, 1), (0, -1))
visited = [['.'] * W for _ in range(H)]
ideal = [['#'] * W for _ in range(H)]
c_max = 0

def bfs(S):
    global visited
    global c_max
    c = 0

    for s in S:
        visited[s[0]][s[1]] = '#'
    que_init = [(s[0], s[1], 0) for s in S]
    que = deque(que_init)

    while que:
        if ideal == visited:
            return c_max

        ci, cj, c = que.popleft()
        for di, dj in move:
            ni, nj = ci + di, cj + dj
            if 0 <= ni < H and 0 <= nj < W and visited[ni][nj] == '.' and C[ni][nj] != '#':
                visited[ni][nj] = '#'
                c_max = max(c_max, c+1)
                que.append((ni, nj, c+1))
    return 0


sg = []
ans = 0
for h in range(H):
    for w in range(W):
        if C[h][w] == '#':
            sg.append((h,w))

ans = bfs(sg)
print(ans)

### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())
grid = (np.array([list(input())
                  for _ in range(H)]) == "#")
cost = np.full((H, W), 10 ** 9, dtype=np.int64)
cost[grid[:, :]] = 0

for i in range(1, H):
    cost[i] = np.minimum(cost[i], cost[i - 1] + 1)

for i in range(H - 2, -1, -1):
    cost[i] = np.minimum(cost[i], cost[i + 1] + 1)

for i in range(1, W):
    cost[:, i] = np.minimum(cost[:, i], cost[:, i - 1] + 1)

for i in range(W - 2, -1, -1):
    cost[:, i] = np.minimum(cost[:, i], cost[:, i + 1] + 1)

print(np.max(cost))
### BUGGY CODE ###

s = input()

q = int(input())
r = 0
b = ""
c = ""
for i in range(q):
    A = list(input().split())
    if A[0] == '1':
        r += 1
    else:
        if (A[1] == '1' and r % 2 == 0) or (A[1] != '1' and r % 2 != 0):
            # s = A[2] + s
            b = A[2] + b
        else:
            # s = s+ A[2]
            c = c + A[2]
s = b + s + c
if r % 2 == 0:
    print(s)
else:
    print(s[::-1])


### FIXED CODE ###

from collections import deque

s = deque(input())

q = int(input())
r = 0
for _ in range(q):
    A = list(input().split())
    if A[0] == '1':
        r = (r + 1)%2
    else:
        if (A[1] == '1' and r % 2 == 0) or (A[1] == '2' and r % 2 == 1):
            s.appendleft(A[2])
        else:
            s.append(A[2])

if r == 1:
    s.reverse()
print("".join(s))
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
for i in range(q):
    l, r = map(int, input().split())
    c = s[l-1:r]
    print(int((len(c)-len(c.replace("AC", "")))/2))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
m = [0]
c = 0
for i in range(1, n):
    if (s[i-1] == "A") & (s[i] == "C"):
        c += 1
    m.append(c)

for j in range(q):
    l, r = map(int, input().split())
    print(m[r-1] - m[l-1])
### BUGGY CODE ###

N = int(input())
ti = [int(input()) for i in range(N)]

maxti = max(ti)

def all_mods(ls, val):
    mods = [val % l for l in ls]
    return max(mods) == 0

i = 1

while 1:
    valid = all_mods(ti, i * maxti)
    if valid:
        break
    i += 1

print(i * maxti)


### FIXED CODE ###

N = int(input())
ti = [int(input()) for i in range(N)]


def euc_alg(val1, val2):

    if val1 == val2:
        return val1

    mod = min(val1, val2)
    divided = max(val1, val2)
    while 1:
        tmp_mod = divided % mod

        if tmp_mod == 0:
            break
        divided = mod
        mod = tmp_mod

    ret = val1 * val2 // mod

    return ret

maxti = max(ti)
# least_common_mult = max([euc_alg(maxti, t) for t in ti])

ans = ti[0]
for t in ti:
    ans = euc_alg(ans, t)

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

#!/usr/bin/env python3
import sys
import itertools

input = sys.stdin.readline


def ST():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


h, w = MI()
Ch, Cw = MI()
Dh, Dw = MI()

S = [["#"] * (w + 4), ["#"] * (w + 4)]
for _ in range(h):
    S.append(["#", "#"] + list(ST()) + ["#", "#"])
S.append(["#"] * (w + 4))
S.append(["#"] * (w + 4))

dxy = ((0, 1), (0, -1), (1, 0), (-1, 0), (0, 0))
wxy = tuple(
    (x, y)
    for x, y in itertools.product([-2, -1, 0, 1, 2], repeat=2)
    if (x, y) not in dxy
)
dxy = ((0, 1), (0, -1), (1, 0), (-1, 0))

wq = {(Ch + 1, Cw + 1)}
cost = 0
while wq:
    q = wq
    passed = []
    while q:
        qq = []
        for y, x in q:
            if y == Dh + 1 and x == Dw + 1:
                print(cost)
                exit()
            passed.append((y, x))
            S[y][x] = "#"
            for dy, dx in dxy:
                ny, nx = y + dy, x + dx
                if S[ny][nx] == "#":
                    continue
                # if ny == Dh + 1 and nx == Dw + 1:
                #     print(cost)
                #     exit()
                qq.append((ny, nx))
                # S[ny][nx] = "#"
        q = qq

    # print(cost, set(passed))
    wq = set()
    for y, x in passed:
        for dy, dx in wxy:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == "#":
                continue
            wq.add((ny, nx))

    cost += 1

print(-1)


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import itertools

input = sys.stdin.readline


def ST():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


h, w = MI()
Ch, Cw = MI()
Dh, Dw = MI()

S = [["#"] * (w + 4), ["#"] * (w + 4)]
for _ in range(h):
    S.append(["#", "#"] + list(ST()) + ["#", "#"])
S.append(["#"] * (w + 4))
S.append(["#"] * (w + 4))

dxy = ((0, 1), (0, -1), (1, 0), (-1, 0), (0, 0))
wxy = tuple(
    (x, y)
    for x, y in itertools.product([-2, -1, 0, 1, 2], repeat=2)
    if (x, y) not in dxy
)
dxy = ((0, 1), (0, -1), (1, 0), (-1, 0))

wq = {(Ch + 1, Cw + 1)}
cost = 0
while wq:
    q = wq
    passed = set()
    while q:
        qq = set()
        for y, x in q:
            if y == Dh + 1 and x == Dw + 1:
                print(cost)
                exit()
            passed.add((y, x))
            S[y][x] = "#"
            for dy, dx in dxy:
                ny, nx = y + dy, x + dx
                if S[ny][nx] == "#":
                    continue
                # if ny == Dh + 1 and nx == Dw + 1:
                #     print(cost)
                #     exit()
                qq.add((ny, nx))
                # S[ny][nx] = "#"
        q = qq

    # print(cost, set(passed))
    wq = set()
    for y, x in passed:
        for dy, dx in wxy:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == "#":
                continue
            wq.add((ny, nx))

    cost += 1

print(-1)
### BUGGY CODE ###

N, K = map(int, input().split())
lightPow = list(map(int, input().split()))

for i in range(K):
  newLightPow = [0]*N
  for t_pos in range(1, N+1):
    count = 0
    for pos in range(1, N+1):
      low = float(pos)-(lightPow[pos-1]+0.5)
      high = float(pos)+(lightPow[pos-1]+0.5)
      #print(t_pos)
      #print("low"+str(low)+" high"+str(high))
      if ((low<=t_pos) and (t_pos<=high)):
        #print("yes")
        count += 1
    newLightPow[t_pos-1] = count
  lightPow = newLightPow
print(*lightPow)


### FIXED CODE ###

import math
N, K = map(int, input().split())
lightPow = list(map(int, input().split()))

for i in range(K):
  newLightPow = [0]*(N+1)
  #print(lightPow)
  for pos in range(1, N+1):
    low = pos - lightPow[pos-1]
    high = pos + lightPow[pos-1]
    low = min(max(1, low), N)
    high = min(max(1, high), N)
    newLightPow[low-1] += 1
    newLightPow[high] -= 1
    #print("pos:"+str(pos))
    #print("low"+str(low)+" high"+str(high))
    #print(newLightPow)
    
  check = True
  for i in range(0, N):
    if (i > 0):
      newLightPow[i] += newLightPow[i-1]
    if (newLightPow[i] < N):
      check = False
  lightPow = newLightPow
  if (check):
    break

print(*lightPow[:-1])