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

import sys
input = sys.stdin.readline
import heapq
from operator import itemgetter
N, Q = map(int, input().split())
Stop = []
for i in range(N):
    S, T, X = map(int, input().split())
    Stop.append([S-X, X, True, i])
    Stop.append([T-X, X, False, i])
Stop.sort(key=itemgetter(0))
q = []
notClosed = [False]*N
for _ in range(Q):
    D = int(input())
    i = 0
    while i < len(Stop) and Stop[i][0] <= D:
        time, pos, lr, idx = Stop[i]
        if lr:
            heapq.heappush(q, (pos, idx))
        else:
            notClosed[idx] = True
            while len(q)>0 and notClosed[q[0][1]]:
                aaa = heapq.heappop(q)[1]
        i+=1
    if len(q):
        print(q[0][0])
    else:
        print(-1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
import heapq
from operator import itemgetter
from bisect import bisect_right
N, Q = map(int, input().split())
Stop = []
for i in range(N):
    S, T, X = map(int, input().split())
    Stop.append([S - X, X, 0, i])
    Stop.append([T - X, X, 1, i])
Stop.sort(key=itemgetter(0))
q = []
notClosed = [False]*N
A = [(-1, -1)]
for time, pos, lr, idx in Stop:
    if lr==0:
        heapq.heappush(q, (pos, idx))
    else:
        notClosed[idx] = True
        while len(q)>0 and notClosed[q[0][1]]:
            aaa = heapq.heappop(q)[1]

    if len(q):
        A.append((time, q[0][0]))
    else:
        A.append((time, -1))
A0 = list(map(itemgetter(0), A))
for _ in range(Q):
    D = int(input())
    idx = bisect_right(A0, D)

    print(A[idx-1][1])
### BUGGY CODE ###

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

for _ in range(Q):
    l, r = map(int, input().split())
    part_len = r - l + 1
    removed_len = len(S[l - 1:r].replace('AC', ''))
    n_ac = (part_len - removed_len) // 2
    print(n_ac)


### FIXED CODE ###

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

t = [0] * (N+2)
t[0] = 1 if S[:2] == 'AC' else 0

for i in range(N-1):
    t[i+1] = t[i] + (1 if S[i:i + 2] == 'AC' else 0)

for _ in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

n, m, r = map(int, input().split())
v = list(map(int, input().split()))

inf = 10 ** 18
d = [[inf for _ in range(n)] for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

import itertools
ans = 10 ** 18
for a in itertools.permutations(v):
    dis = 0
    for i in range(r-1):
        dis += d[a[i+1]-1][a[i]-1]
    ans = min(ans, dis)
print(ans)

### FIXED CODE ###

n, m, r = map(int, input().split())
v = list(map(int, input().split()))

inf = 10 ** 18
d = [[inf for _ in range(n)] for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

import itertools
ans = 10 ** 18
for a in itertools.permutations(v):
    dis = 0
    for i in range(r-1):
        dis += d[a[i+1]-1][a[i]-1]
    ans = min(ans, dis)
print(ans)
### BUGGY CODE ###

n = int(input())
d = {}
for i in range(0,n):
  c = input()
  if c in d:
    d[c] +=1
  else:
    d[c] = 1
max_k_list = sorted([kv[0] for kv in d.items() if kv[1] == max(d.values())])
for i in max_k_list:
  print(i)
  

### FIXED CODE ###

q=int(input())
dic={}
for i in range(q):
    s=input()
    if not s in dic:
        dic[s]=1
    else:
        dic[s]+=1
max_val=max(dic.values())
a=sorted([i for i, k in dic.items() if k == max_val])
for i in a:
    print(i)
### BUGGY CODE ###

# -*- coding: utf-8 -*-


def main():
    s = list(input())
    n = len(s)
    t = list(input())
    m = len(t)
    # LCSの長さを状態として持つ
    dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]

    # See:
    # https://qiita.com/drken/items/03c7db44ccd27820ea0d
    # LCSの求め方は蟻本のpp.56-57も参照
    # △文字列s, tを二次元配列の形で扱う
    for i in range(n):
        for j in range(m):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

    ans = ''
    i = n
    j = m

    # △復元
    # dp tableの値を見てどこから更新されたかを特定
    while i > 0 and j > 0:
        # (i - 1, j) -> (i, j)
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        # (i, j - 1) -> (i, j)
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        # (i - 1, j - 1) -> (i, j)
        else:
            ans = s[i - 1] + ans
            i -= 1
            j -= 1

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-


def main():
    s = list(input())
    n = len(s)
    t = list(input())
    m = len(t)
    # LCSの長さを状態として持つ
    dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]

    # See:
    # https://qiita.com/drken/items/03c7db44ccd27820ea0d
    # LCSの求め方は蟻本のpp.56-57も参照
    # △文字列s, tを二次元配列の形で扱う
    for i in range(n):
        for j in range(m):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

    ans = ''
    i = n
    j = m

    # △復元
    # dp tableの値を見てどこから更新されたかを特定
    while i > 0 and j > 0:
        # (i - 1, j) -> (i, j)
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        # (i, j - 1) -> (i, j)
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        # (i - 1, j - 1) -> (i, j)
        else:
            ans = s[i - 1] + ans
            i -= 1
            j -= 1

    print(ans)


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

import sys
def fastio():
    from io import StringIO
    from atexit import register
    global input
    sys.stdin = StringIO(sys.stdin.read())
    input = lambda : sys.stdin.readline().rstrip('\r\n')
    sys.stdout = StringIO()
    register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()
import collections as cc
n=int(input())
l=list(map(int,input().split()))
ff=cc.Counter(l)
ff=dict(ff)
ans=[]
for i in range(n):
    f=ff.copy()
    f[l[i]]=max(0,f[l[i]]-1)
    t=0
    for i in f:
        x=f[i]
        t+=(x*(x-1))//2
    ans.append(t)
for i in ans:
    print(i)
    
    

### FIXED CODE ###

import collections as cc
n=int(input())
l=list(map(int,input().split()))
ff=cc.Counter(l)
ff=dict(ff)
ans=0
for i in ff:
    x=ff[i]
    ans+=(x*(x-1))//2
v={}
for i in set(l):
    vv=max(ff[i]-1,0)
    te=ans-(ff[i]*(ff[i]-1))//2+(vv*(vv-1))//2
    v[i]=te
for i in l:
    print(v[i])
### BUGGY CODE ###

N, M = map(int, input().split())
INF = 10**9
A = []
B = []

for i in range(N):
  a,b = map(int, input().split())
  A.append(a)
  B.append(b)

ans = 0
count = 0
while(count < M):
  min_A = min(A)
  min_Ai = A.index(min_A)
  if count + B[min_Ai] > M:
    ans += min_A * (M - count)
    count = M
  else:
    ans += min_A * B[min_Ai]
    count += B[min_Ai]
  del A[min_Ai]
  del B[min_Ai]

print(ans)


### FIXED CODE ###

def unzip(li):
  return map(list, zip(*li))

N, M = map(int, input().split())
tmp_C = [0 for i in range(N)]

for i in range(N):
  a,b = map(int, input().split())
  tmp_C[i] = (a,b)
  
C = sorted(tmp_C)
A, B = unzip(C)
ans = 0
count = 0
cur = 0
while(count < M):
  min_A = A[cur]
  B_min = B[cur]
  if count + B_min >= M:
    print(ans + min_A * (M - count))
    break
  else:
    ans += min_A * B_min
    count += B_min
    cur += 1
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from math import ceil
N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for _ in range(N)]
XH.sort(key = lambda x:x[0])

ans = 0
for i,xh in enumerate(XH):
    X = xh[0]
    H = xh[1]
    if H > 0:
        num = ceil(H/A)
        for j in range(i,N):
            if XH[j][0] <= X+2*D:
                XH[j][1] -= A*num
            else:
                break
        ans += num
print(ans)


### FIXED CODE ###

#https://atcoder.jp/contests/abc153/submissions/9750027

import sys
input = sys.stdin.readline
from math import ceil
from collections import deque
N,D,A = map(int, input().split())
XH = [list(map(int,input().split())) for _ in range(N)]
XH.sort(key = lambda x:x[0])
#X,H = map(list, zip(*XH))
q = deque()
d = 0
ans = 0

for x,h in XH:
    while q and q[0][0] < x:    #今見ている座標が既にそれまでの爆弾範囲から外れていたら
        d -= q.popleft()[1]
    h -= d
    if h > 0:
        num = ceil(h/A)
        ans += num
        q.append((x+2*D, num*A))    #(末端, そこまででの爆弾の威力)
        d += num*A
print(ans)
### BUGGY CODE ###

import numpy as np
from collections import defaultdict

N, K = map(int, input().split())
As = np.array([0] + list(map(int, input().split())))
#Find (i, j) that satisfies "sum(As[i:j]) % K == j - i"
#If 0 < j - i < K then 
#sum(As[i:j]) % K == j - i % K
#<-> (sum(As[:j]) - j) % K == (sum(As[:i]) - i) % K

mods = As % K
csum_mods = np.cumsum(mods)
magic_array = (csum_mods - np.arange(0, N+1)) % K

indices = defaultdict(list)
for i, m in enumerate(magic_array.tolist()):
    indices[m].append(i)

ans = 0
for ls in indices.values():
    for i in range(len(ls)):
        for j in range(i+1, len(ls)):
            if ls[j] - ls[i] < K:
                ans += 1
            else:
                break
        
print(ans)

### FIXED CODE ###

import numpy as np
from collections import defaultdict

N, K = map(int, input().split())
As = np.array([0] + list(map(int, input().split())))
#Find (i, j) that satisfies "sum(As[i:j]) % K == j - i"
#If 0 < j - i < K then 
#sum(As[i:j]) % K == j - i % K
#<-> (sum(As[:j]) - j) % K == (sum(As[:i]) - i) % K

mods = As % K
csum_mods = np.cumsum(mods)
magic_array = (csum_mods - np.arange(0, N+1)) % K

indices = defaultdict(list)
for i, m in enumerate(magic_array.tolist()):
    indices[m].append(i)

ans = 0
for ls in indices.values():
    j = 1
    for i in range(len(ls)):
        while j < len(ls):
            if ls[j] - ls[i] < K:
                j += 1
            else:
                break
        ans += j - i - 1
        
print(ans)
### BUGGY CODE ###

N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]

from itertools import permutations

colors = tuple(i for i in range(C))

table = [[0 for i in range(C)] for j in range(3)]
for color in colors:
    for col in range(N):
        for row in range(N):
            table[(col+row)%3][color]+=D[c[col][row]-1][color]
            
ans = 10**9    
for i, j, k in permutations(colors, 3):
    ans = min(ans, table[0][i]+table[1][j]+table[2][k])

print(ans)

### FIXED CODE ###

N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]

from itertools import permutations

colors = tuple(i for i in range(C))

table = [[0 for i in range(C)] for j in range(3)]
for color in colors:
    for col in range(N):
        for row in range(N):
            table[(col+row)%3][color]+=D[c[col][row]-1][color]
            
ans = 10**9    
for i, j, k in permutations(colors, 3):
    ans = min(ans, table[0][i]+table[1][j]+table[2][k])

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

from collections import deque

n, x, y = map(int, input().split())
graph = dict()
for i in range(1, n+1):
    if i not in graph.keys():
        graph[i] = set()
    if i < n:
        graph[i].add(i+1)
    if i > 1:
        graph[i].add(i-1)
graph[x].add(y)
graph[y].add(x)
dist = [[]]
def bfs(source):
    q = deque()
    q.append(source)
    d = [pow(10, 4)] * (n+1)
    d[source] = 0
    vis = [0] * (n+1)
    while len(q):
        temp = q.popleft()
        for i in graph[temp]:
            if not vis[i]:
                q.append(i)
                vis[i] = 1
            d[i] = min(d[temp]+1, d[i])
    dist.append(d)
for i in range(1, n+1):
    bfs(i)
dp = dict()
for i in range(1, n):
    for j in range(i+1, n+1):
        if dist[i][j] not in dp.keys():
            dp[dist[i][j]] = 0
        dp[dist[i][j]] += 1
for i in range(1, n):
    if i not in dp.keys():
        print(0)
    else:
        print(dp[i])

### FIXED CODE ###

"""
    Template written to be used by Python Programmers.
    Use at your own risk!!!!
    Owned by enraged(rating - 5 star at CodeChef and Specialist at Codeforces).
"""
import sys
from functools import lru_cache
from collections import defaultdict as dd
def data(): return sys.stdin.readline().strip()
def out(var): sys.stdout.write(str(var))
def outln(var): sys.stdout.write(str(var)+"\n")
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


n, x, y = sp()
dp = dd(int)
for i in range(1, n):
    for j in range(i+1, n+1):
        answer = min(abs(j-i), abs(x-i)+1+abs(j-y), abs(y-i)+1+abs(j-x))
        dp[answer] += 1
for i in range(1, n):
    outln(dp[i])
### BUGGY CODE ###

N=int(input())
plist=list(map(int,input().split()))

mat=[[True]*N for _ in range(N)]
answer=0
for p in plist:
  i=(p-1)//N
  j=(p-1)%N
  #print(i,j)
  
  queue=[(i,j)]
  visited=[[False]*N for _ in range(N)]
  reach=False
  d=0
  while queue:
    new_queue=set()
    
    while queue:
      x,y=queue.pop()
      if x==0 or x==N-1 or y==0 or y==N-1:
        reach=True
        break
        
      visited[x][y]=True
      if not visited[x-1][y]:
        if mat[x-1][y]:
          new_queue.add((x-1,y))
        else:
          queue.append((x-1,y))
      if not visited[x+1][y]:
        if mat[x+1][y]:
          new_queue.add((x+1,y))
        else:
          queue.append((x+1,y))
      if not visited[x][y-1]:
        if mat[x][y-1]:
          new_queue.add((x,y-1))
        else:
          queue.append((x,y-1))
      if not visited[x][y+1]:
        if mat[x][y+1]:
          new_queue.add((x,y+1))
        else:
          queue.append((x,y+1))
          
    if reach:
      break
      
    queue=list(new_queue)
    d+=1
    
  #print(i,j,d)
  answer+=d
  mat[i][j]=False
  
print(answer)

### FIXED CODE ###

N=int(input())
plist=list(map(int,input().split()))

sit=[[1]*N for _ in range(N)]
dist=[[min(i,j,N-1-i,N-1-j) for j in range(N)] for i in range(N)]

answer=0
for p in plist:
  i=(p-1)//N
  j=(p-1)%N
  #print(i,j)
  sit[i][j]=0
  answer+=dist[i][j]
  
  queue=[(i,j,dist[i][j])]
  d=0
  while queue:
    x,y,d=queue.pop()
    if x>0 and dist[x-1][y]>d:
      dist[x-1][y]=d
      queue.append((x-1,y,d+sit[x-1][y]))
    if x<N-1 and dist[x+1][y]>d:
      dist[x+1][y]=d
      queue.append((x+1,y,d+sit[x+1][y]))    
    if y>0 and dist[x][y-1]>d:
      dist[x][y-1]=d
      queue.append((x,y-1,d+sit[x][y-1]))
    if y<N-1 and dist[x][y+1]>d:
      dist[x][y+1]=d
      queue.append((x,y+1,d+sit[x][y+1]))
      
print(answer)
### BUGGY CODE ###

import numpy as np

S = list(input().strip())
length = len(S)
op = np.asarray(S)

def checkValue():
    count = 0
    for i in range(length):
        group = ""
        for j in range(i, length):
            group += op[j]
            if int(group) % 2019 == 0:
                count += 1
    print(count)
checkValue()
    


### FIXED CODE ###

import numpy as np
#S = list(input().strip())
#length = len(S)
#op = np.asarray(S)

def solution():
    S = input()
    N = len(S)
    num = [0] * 2019
    num[0] = 1
    c, ans, dgt = 0, 0, 1
    for i in range(N-1, -1, -1):
        c = (c + int(S[i]) * dgt) % 2019
        dgt *= 10
        dgt %= 2019
        ans += num[c]
        num[c] += 1
        
    print(ans)

solution()



def sample():
    x = -1
    count = 0
    for i in op:
        x += 1
        group = ""
        for j, name in enumerate(op, x):
            group += name
            if int(group) % 2019 == 0:
                count += 1
    print(count)

def checkValue():
    count = 0
    for i in range(length):
        group = ""
        for j in range(i, length):
            group += op[j]
            if int(group) % 2019 == 0:
                count += 1
    print(count)
#checkValue()
### BUGGY CODE ###

h_len, w_len = map(int, input().split())
m_list = [[True for _ in range(w_len+2)]]
for _ in range(h_len):
    m_list.append([True] + [s=='#' for s in input()] + [True])
m_list.append([True for _ in range(w_len+2)])
q_list = []
for h, w_list in enumerate(m_list[1:-1]):
    for w, a in enumerate(w_list[1:-1]):
        if a:
            q_list.append([h+1, w+1])
dx_list = [1, 0, -1, 0]
dy_list = [0, -1, 0, 1]
cnt = -1
while q_list:
    cnt += 1
    new_q_list = []
    for h, w in q_list:
        for dx, dy in zip(dx_list, dy_list):
            x, y = w+dx, h+dy
            if not m_list[y][x]:
                m_list[y][x] = True
                new_q_list.append([y, x])
    q_list = new_q_list
print(cnt)


### FIXED CODE ###

def bfs(q_list):
    cnt = -1
    while q_list:
        cnt += 1
        new_q_list = []
        for h, w in q_list:
            if not m_list[h][w+1]:
                m_list[h][w+1] = True
                new_q_list.append((h, w+1))
            if not m_list[h+1][w]:
                m_list[h+1][w] = True
                new_q_list.append((h+1, w))
            if not m_list[h][w-1]:
                m_list[h][w-1] = True
                new_q_list.append((h, w-1))
            if not m_list[h-1][w]:
                m_list[h-1][w] = True
                new_q_list.append((h-1, w))
        q_list = new_q_list
    print(cnt)


if __name__ == "__main__":
    h_len, w_len = map(int, input().split())
    m_list = [[True for _ in range(w_len+2)]]
    for _ in range(h_len):
        m_list.append([True] + [s=='#' for s in input()] + [True])
    m_list.append([True for _ in range(w_len+2)])
    q_list = []
    for h in range(1, h_len+1):
        for w in range(1, w_len+1):
            if m_list[h][w]:
                q_list.append((h, w))
    bfs(q_list)
### BUGGY CODE ###

from itertools import islice


def main():
    city_count, express_count, query_count = map(int, input().split())

    city_list = [(set(), set()) for _ in range(city_count + 1)]

    for express_index in range(1, express_count + 1):
        l, r = map(int, input().split())
        for city in islice(city_list, 1, l + 1):
            city[0].add(express_index)
        for city in islice(city_list, r, None):
            city[1].add(express_index)

    for _ in range(query_count):
        p, q = map(int, input().split())
        city_p = city_list[p][0]
        city_q = city_list[q][1]
        print(len(city_p & city_q))


if __name__ == '__main__':
    main()


### FIXED CODE ###

from array import array
from itertools import accumulate, repeat, starmap
from operator import add, itemgetter


def main():
    city_count, express_count, query_count = map(int, input().split())

    city_list = [array('L', repeat(0, city_count + 1))
                 for _ in range(city_count + 1)]

    for _ in range(express_count):
        l, r = map(int, input().split())
        city_list[l][r] += 1

    for city_index in range(1, city_count + 1):
        city_list[city_index] = array('L', accumulate(city_list[city_index]))

    for city_index in range(2, city_count + 1):
        city_list[city_index] = array('L', starmap(
            add, zip(*(city_list[city_index + i] for i in (-1, 0)))))

    for _ in range(query_count):
        p, q = map(int, input().split())
        print(city_list[q][q] - city_list[p - 1][q])


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

import sys
from collections import defaultdict
input=sys.stdin.readline

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

D=defaultdict(int)
L=[s]
LL,LLL,LLLL,l=[],[],[],[]
cnt=0

while L:
    if t in L:
        print(cnt)
        exit()
    for i in L:
        for j in G[i]:
            LL.append(j)
    for ii in LL:
        for jj in G[ii]:
            LLL.append(jj)
    for iii in LLL:
        for jjj in G[iii]:
            LLLL.append(jjj)
    for iiii in LLLL:
        if D[iiii]==0:
            D[iiii]=1
            l.append(iiii)
    L,LL,LLL,LLLL=l,[],[],[]
    l=[]
    cnt+=1

print(-1)

### FIXED CODE ###

import sys
from collections import deque
input=sys.stdin.readline

n,m=map(int,input().split())
G=[[] for _ in range(3*(n+1))]
for _ in range(m):
    u,v=map(int,input().split())
    G[3*u].append(3*v+2)
    G[3*u+1].append(3*v)
    G[3*u+2].append(3*v+1)
s,t=map(int,input().split())

Q=deque()
Q.append(s*3)
D=[-3 for _ in range(3*(n+1))]
D[s*3]=0

while Q:
    q=Q.popleft()
    for i in G[q]:
        if D[i]==-3:
            D[i]=D[q]+1
            Q.append(i)

print(D[t*3]//3)
### BUGGY CODE ###

import copy
import itertools
    
h,w = (int(x) for x in input().split())
ab = []
step = []
count = 0
for i in range(h):
    a = list(input())
    ab.append(a+['#'])
    for j in range(w):
        if a[j] == '#':
            step.append([i,j])

ab.append(list('#'*w))           
memo_step = copy.deepcopy(step)

dp = [[0 for a in range(w)] for b in range(h)]
 
while len(step) > 0:
    y, x = step.pop(0)
    if ab[y+1][x] == '.' and dp[y+1][x] == 0 :
        step.append([y+1, x])
        dp[y+1][x] = dp[y][x] + 1
    if ab[y][x+1] == '.' and dp[y][x+1] == 0 :
        step.append([y, x+1])
        dp[y][x+1] = dp[y][x] + 1
    if ab[y-1][x] == '.' and dp[y-1][x] == 0 :
        step.append([y-1, x])
        dp[y-1][x] = dp[y][x] + 1
    if ab[y][x-1] == '.' and dp[y][x-1] == 0 :
        step.append([y, x-1])
        dp[y][x-1] = dp[y][x] + 1

for i,j in memo_step:
    dp[i][j] = 0

mx = max(list(itertools.chain.from_iterable(dp)))
 
print(mx)


### FIXED CODE ###

from collections import deque
 
H, W = [int(x) for x in input().split()]
cell = [list(input()) for i in range(H)]
 
painted = deque()
for h in range(H):
    for w in range(W):
        if cell[h][w] == '#':
            painted.append([h, w, 0])
 
ans = 0
while len(painted) > 0:
    blackcell = painted.popleft()
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = blackcell[0] + dy
        nw = blackcell[1] + dx
        d = blackcell[2]
        if 0 <= nh < H and 0 <= nw < W and cell[nh][nw] == '.':
            cell[nh][nw] = '#'
            painted.append([nh, nw, d + 1])
        ans = d
 
print(ans)
### BUGGY CODE ###

def count_num_light(a):
  ret = [0 for _ in range(len(a))]
  for i in range(len(a)):
    start = max(0, i-a[i])
    end = min(n, i+a[i]+1)
    for j in range(start, end):
      ret[j] += 1
  
  return ret
                  
n, k = map(int, input().split())
a = list(map(int, input().split()))
num_light = count_num_light(a)
 
for i in range(k-1):
  num_light = count_num_light(num_light)
  if sum(num_light) == n**2:
    break
    
print(*num_light)

### FIXED CODE ###

def count_num_light(a):
  ret = [0 for _ in range(len(a))]
  n = len(a)
  for i in range(n):
    start = max(0, i-a[i])
    end = min(n-1, i+a[i])
    ret[start] += 1
    if end+1 < n:
      ret[end+1] -= 1
  for i in range(1,n):
    ret[i] += ret[i-1]
  
  return ret
                  
n, k = map(int, input().split())
a = list(map(int, input().split()))
num_light = count_num_light(a)
 
for i in range(k-1):
  num_light = count_num_light(num_light)
  if sum(num_light) == n**2:
    break
    
print(*num_light)