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

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


#差分だけで良い，これを*1 or -1していく
diff = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        diff[i][j] = abs(A[i][j] - B[i][j])

#i,jマスにおいて，偏りがkになれるかどうかでDP
K = 6401 #適当,[-3200,3200]
kk = int((K-1)/2)
dp = [[[False]*K for _ in range(W)] for _ in range(H)]

dp[0][0][kk+diff[0][0]] = True
dp[0][0][kk-diff[0][0]] = True

for i in range(H):
    for j in range(W):
        for k in range(K):
            if i-1>=0:
                if k+diff[i][j]<K:
                    if dp[i-1][j][k+diff[i][j]]:
                        dp[i][j][k] =True
                if k-diff[i][j]>=0:
                    if dp[i-1][j][k-diff[i][j]]:
                        dp[i][j][k] =True
            if j-1>=0:
                if k+diff[i][j]<K:
                    if dp[i][j-1][k+diff[i][j]]:
                        dp[i][j][k] =True
                if k-diff[i][j]>=0:
                    if dp[i][j-1][k-diff[i][j]]:
                        dp[i][j][k] =True

ans = K
for k in range(K):
    if dp[H-1][W-1][k]:
        ans = min(ans,abs(k-kk))

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

H,W = map(int,input().split())
#差分だけで良い，これを*1 or -1していく
diff = [list(map(int, input().split())) for _ in range(H)]

for i in range(H):
    B = list(map(int,input().split()))
    for j in range(W):
        diff[i][j] = abs(diff[i][j] - B[j])
        
 # i,jマスにおいて，偏りがkになれるかどうかでDP
#dp[i][j]にはkという数字にたどり着けるかどうかを示す2進数を入れる

dp = [[False]*W for _ in range(H)]
ofs = 80*(H+W)


dp[0][0]=(1<<(ofs+diff[0][0]) | 1>>(ofs-diff[0][0]))
 
for i in range(H):
    for j in range(W):
        if i>0:
            dp[i][j]|=(dp[i-1][j]<<diff[i][j] | dp[i-1][j]>>diff[i][j])
        if j>0:
            dp[i][j]|=(dp[i][j-1]<<diff[i][j] | dp[i][j-1]>>diff[i][j])


#0のところから見て，最初に1が出てきたところが答え
for k in range(ofs):
    if (dp[-1][-1]>>(k+ofs)&1):
        print(k)
        break
### BUGGY CODE ###

S = input()
Q = int(input())
Que = [list(map(str,input().split())) for i in range(Q)]

from collections import deque

S = list(S)
S = deque(S)

for i in range(Q):
    if Que[i][0] == '1':
        S.reverse()
    elif Que[i][0] == '2':
        if Que[i][1] == '1':
            S.appendleft(Que[i][2])
        elif Que[i][1] == '2':
            S.append(Que[i][2])
            
print("".join(S))

### FIXED CODE ###

S = input()
Q = int(input())
Que = [list(map(str,input().split())) for i in range(Q)]

from collections import deque
count = 0
 
S = list(S)
S = deque(S)
 
for i in range(Q):
    if Que[i][0] == '1':
        #S.reverse()
        count += 1
    elif Que[i][0] == '2':
        if Que[i][1] == '1' and count%2 == 0:
            S.appendleft(Que[i][2])
        elif Que[i][1] == '1' and count%2 == 1:
            S.append(Que[i][2])
        elif Que[i][1] == '2' and count%2 == 0:
            S.append(Que[i][2])
        elif Que[i][1] == '2' and count%2 == 1:
            S.appendleft(Que[i][2])
            
if count%2 == 0:
    print("".join(S))
else:
    S.reverse()
    print("".join(S))
### BUGGY CODE ###

N=int(input())
p=list(map(int,input().split()))
a=0
i=0

for i in range(N):
  b=p[0:i+1] 
  if min(b)==p[i]:
    a+=1
print(a)

  

### FIXED CODE ###

N=int(input())
p=list(map(int,input().split()))
a=0
b=p[0]
for i in range(N):
  if p[i]<=b:
    a+=1
    b=p[i]
  else:
    pass
print(a)
### BUGGY CODE ###

import bisect

s = input()
t = input()

s_dict = {}
for i, si in enumerate(s):
    s_dict[si] = [i] if si not in s_dict else s_dict[si] + [i]

# print(s_dict)

s_len = len(s)
counter = 0
fail = False
memo = {}
for ti in t:
    if ti not in s_dict:
        fail = True
        break
    # counter in s
    c_in_s = counter % s_len
    c = 0
    if (ti, c_in_s) not in memo:
        c = bisect.bisect_left(s_dict[ti], c_in_s)
        memo[(ti, c_in_s)] = c
    else:
        c = memo[(ti, c_in_s)]
    if c == len(s_dict[ti]):
        counter += s_len - c_in_s
        counter += s_dict[ti][0]
        counter += 1
    else:
        counter += s_dict[ti][c] - c_in_s
        counter += 1

print(counter if not fail else '-1')




### FIXED CODE ###

import bisect

s = input()
t = input()

s_dict = {}
for i, si in enumerate(s):
    if si not in s_dict:
        s_dict[si] = [i]
    else:
        s_dict[si].append(i)

# print(s_dict)

s_len = len(s)
counter = 0
fail = False
for ti in t:
    if ti not in s_dict:
        fail = True
        break
    # counter in s
    c_in_s = counter % s_len
    c = bisect.bisect_left(s_dict[ti], c_in_s)
    if c == len(s_dict[ti]):
        counter += s_len - c_in_s
        counter += s_dict[ti][0]
        counter += 1
    else:
        counter += s_dict[ti][c] - c_in_s
        counter += 1

print(counter if not fail else '-1')
### BUGGY CODE ###

from collections import Counter, deque

N = int(input())
A = deque(map(int, input().split()))
B = deque(map(int, input().split()))

ca, cb = Counter(A), Counter(B)

cab = ca+cb

if any(c > N for c in cab.values()):
    print('No')
else:
    print('Yes')
    for _ in range(N):
        if all(a != b for a, b in zip(A, B)):
            print(' '.join(str(i) for i in B))
            break
        
        B.rotate()

### FIXED CODE ###

from collections import Counter, deque

N = int(input())
A = deque(map(int, input().split()))
B = deque(map(int, input().split()))

ca, cb = Counter(A), Counter(B)

cab = ca+cb

if any(c > N for c in cab.values()):
    print('No')
else:
    print('Yes')
    B.rotate(N//2)
    res = []
    while A:
        if A[0] != B[0]:
            A.popleft()
            res.append(str(B.popleft()))
        else:
            B.rotate()
        
    print(' '.join(res))
### BUGGY CODE ###

import math
import sys
sys.setrecursionlimit(100000000)

# N = 4
# HRR = [10, 30, 40, 20]
# # N = 2
# HRR = [10, 10]

N = int(input())
HRR = list(map(int,input().split()))
result = []


def calculate(pos, cost):
    if pos == N-1:
        result.append(int(cost))
        return

    if pos + 1 <= N - 1:
        calculate(pos + 1, cost + math.fabs(HRR[pos + 1] - HRR[pos]))

    if pos + 2 <= N - 1:
        calculate(pos + 2,cost + math.fabs(HRR[pos + 2] - HRR[pos]))


calculate(0, 0)
print(min(result))

### FIXED CODE ###

# N = 4
# HRR = [10, 30, 40, 20]
# N = 2
# HRR = [10, 10]

N = int(input())
HRR = list(map(int,input().split()))
result = []
for i in range(N):
    if i == 0:
        result.append(0)
    elif i == 1:
        s1 = result[i - 1] + abs(HRR[i] - HRR[i - 1])
        result.append(s1)
    else:
        s1 = result[i - 1] + abs(HRR[i] - HRR[i - 1])
        s2 = result[i - 2] + abs(HRR[i] - HRR[i - 2])
        result.append(min(s1, s2))

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

def LI(): return list(map(int, input().split()))
n, m, d = LI()
if d == 0:
    one = n
    two = 0
else:
    hidari = d - max(0, 2*d-n)
    migi = n-hidari

    one = hidari*2
    two = max(0, migi - hidari)
    #print(hidari, migi,one,two)
a = one + 2*two
ans = n**(m-2)*(a*(m-1))
print(ans/n**m)



### FIXED CODE ###

def LI(): return list(map(int, input().split()))
n, m, d = LI()
if d == 0:
    one = n
    two = 0
else:
    hidari = d - max(0, 2*d-n)
    migi = n-hidari

    one = hidari*2
    two = max(0, migi - hidari)
    #print(hidari, migi,one,two)
a = one + 2*two
ans = (a*(m-1))/n**2
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
min_turn = 300000
for i in range(N):
    if i == 0:
        turn = S[1:].count('E')
    elif i == (N-1):
        turn = S[0:i].count('W')
    else:
        turn = S[0:i].count('W') + S[i+1:].count('E')
    if min_turn > turn:
        min_turn = turn
print(min_turn)

### FIXED CODE ###

N = int(input())
S = input()
min_turn = 300000
wnum = 0
for i in range(N):
    if i == 0:
        enum = S[1:].count('E')
    if (1 <= i) and (S[i] == 'E'):
        enum -= 1
    if (1 <= i) and (S[i-1] == 'W'):
        wnum += 1
    turn = enum + wnum
    if min_turn > turn:
        min_turn = turn
print(min_turn)
### BUGGY CODE ###

[A, B] = list(map(int, input().split(' ')))

answer = 0
for n in range(A, B + 1):
    answer = answer ^ n

print(answer)

### FIXED CODE ###

# [A, B] = list(map(int, input().split(' ')))
#
# answer = 0
# for n in range(A, B + 1):
#     answer = answer ^ n
#
# print(answer)


[A, B] = list(map(int, input().split(' ')))

answer = 0

A1_digit = len(bin(A - 1)) - 2
Abit_list = []
Amin_bit = 1 if 1 <= (A - 1) % 4 <= 2 else 0
Abit_list.append(Amin_bit)

for i in range(2, A1_digit + 1):
    rem = (A - 1) % 2 ** i
    A_bit = 0 if rem < 2 ** (i - 1) or (rem - 2 ** (i - 1)) % 2 == 1 else 1
    Abit_list.append(A_bit)

B_digit = len(bin(B)) - 2
Bbit_list = []
Bmin_bit = 1 if 1 <= B % 4 <= 2 else 0
Bbit_list.append(Bmin_bit)
for i in range(2, B_digit + 1):
    rem = B % 2 ** i
    B_bit = 0 if rem < 2 ** (i - 1) or (rem - 2 ** (i - 1)) % 2 == 1 else 1
    Bbit_list.append(B_bit)

Abit_list.reverse()
Bbit_list.reverse()
# print(Abit_list)
# print(Bbit_list)
Axor = 0
for v in Abit_list:
    Axor = Axor << 1
    if v == 1:
        Axor = Axor + 1

Bxor = 0
for v in Bbit_list:
    Bxor = Bxor << 1
    if v == 1:
        Bxor = Bxor + 1

# print(bin(Axor ^ Bxor))
# print(bin(435))
print(Axor ^ Bxor)
### BUGGY CODE ###

n,k=map(int,input().split())
if k>((n-2)*(n-1))//2:
  print(-1)
else:
  ans=[]
  for b in range(1,n):
    ans.append((1,b+1))
  i,j,cnt=2,3,0
  while cnt<((n-2)*(n-1))//2-k:
    while j<=n:
      ans.append((i,j))
      j+=1
      cnt+=1
      if cnt==((n-2)*(n-1))//2-k:
        break
    i+=1
  print(len(ans))
  for i in range(len(ans)):
    print(*ans[i])

### FIXED CODE ###

n,k=map(int,input().split())
if k>((n-2)*(n-1))//2:
  print(-1)
else:
  ans=[]
  for b in range(1,n):
    ans.append((1,b+1))
  s=[]
  for i in range(1,n-1):
    for j in range(i+1,n):
      s.append((i+1,j+1))
  for i in range(((n-2)*(n-1))//2-k):
    ans.append((s[i][0],s[i][1]))
  print(len(ans))
  for i in range(len(ans)):
    print(*ans[i])
### BUGGY CODE ###

n,m,q=map(int,input().split())
counts=[[0 for _ in range(n)] for _ in range(n)]
for _ in range(m):
    l,r=map(int,input().split())
    counts[l-1][r-1]+=1
cumsum=[[0 for _ in range(n+1)] for _ in range(n)]
for i in range(n):
    for j in range(n):
        cumsum[i][j+1]=cumsum[i][j]+counts[i][j]
    
for _ in range(q):
    l,r=map(int,input().split())
    print(sum(cumsum[i][r]-cumsum[i][l-1] for i in range(l-1,r)))


### FIXED CODE ###

n,m,q=map(int,input().split())
counts=[[0 for _ in range(n)] for _ in range(n)]
for _ in range(m):
    l,r=map(int,input().split())
    counts[l-1][r-1]+=1
cumsum=[[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(n):
    for j in range(n):
        cumsum[i+1][j+1]=cumsum[i+1][j]+counts[i][j]
for j in range(n+1):
    for i in range(n):
        cumsum[i+1][j]+=cumsum[i][j]
        
for _ in range(q):
    l,r=map(int,input().split())
    print(cumsum[r][r]-cumsum[r][l-1]-cumsum[l-1][r]+cumsum[l-1][l-1])
### BUGGY CODE ###

from collections import deque
import numpy as np

H, W = list(map(int, input().split()))
field = [[i=='#' for i in input()] for _ in range(H)]
count = 0

def bfs():
  global count
  q = deque()
  for y in range(H):
    for x in range(W):
      if field[y][x]:
        q.append((y, x))
  while True:
    nq = deque()
    while len(q) > 0:
      y, x = q.popleft()
      for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
          continue
        if field[ny][nx]:
          continue
        field[ny][nx] = True
        nq.append((ny, nx))
    if len(nq) > 0:
      q = nq
    else:
      break
    count += 1
      
bfs()
print(count)

### FIXED CODE ###

from collections import deque
import copy

def main():
  H, W = map(int, input().split())
  maps = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if maps[i][j]])
  count = 0
  while True:
    nq = deque()
    while q:
      x, y = q.popleft()
      if x > 0 and not maps[x-1][y]:
        maps[x-1][y] = True
        nq.append((x-1,y))
      if y > 0 and not maps[x][y-1]:
        maps[x][y-1] = True
        nq.append((x,y-1))
      if x < H-1 and not maps[x+1][y]:
        maps[x+1][y] = True
        nq.append((x+1,y))
      if y < W-1 and not maps[x][y+1]:
        maps[x][y+1] = True
        nq.append((x,y+1))
    if nq:
      q = copy.copy(nq)
    else:
        break
    count += 1
  print(count)

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

from collections import deque
import numpy as np
import sys
def input():
  return sys.stdin.readline()[:-1]

H, W=map(int, input().split())
S=['#'*(W+2)]+['#'+input()+'#' for i in range(H)]+['#'*(W+2)]

def f(data):
  m[data[0]][data[1]]=data[2]
  if m[data[0]-1][data[1]]<0 and S[data[0]-1][data[1]]=='.':
    q.append([data[0]-1, data[1], data[2]+1])
  if m[data[0]+1][data[1]]<0 and S[data[0]+1][data[1]]=='.':
    q.append([data[0]+1, data[1], data[2]+1])
  if m[data[0]][data[1]-1]<0 and S[data[0]][data[1]-1]=='.':
    q.append([data[0], data[1]-1, data[2]+1])
  if m[data[0]][data[1]+1]<0 and S[data[0]][data[1]+1]=='.':
    q.append([data[0], data[1]+1, data[2]+1])

out=0
for x in range(1, H+1):
  for y in range(1, W+1):
    if S[x][y]=='#':
      continue
    q=deque()
    q.append([x, y, 0])
    m=[[-1]*(W+2) for i in range(H+2)]
    while len(q)>0:
      data=q.popleft()
      f(data)
    tmp=np.max(m)
    if tmp>out:
      out=tmp
      
print(out)

### FIXED CODE ###

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

H, W=map(int, input().split())
S=['#'*(W+2)]+['#'+input()+'#' for i in range(H)]+['#'*(W+2)]

def f(data):
  m[data[0]][data[1]]=data[2]
  if m[data[0]-1][data[1]]==-2 and S[data[0]-1][data[1]]=='.':
    m[data[0]-1][data[1]]=-1
    q.append([data[0]-1, data[1], data[2]+1])
  if m[data[0]+1][data[1]]==-2 and S[data[0]+1][data[1]]=='.':
    m[data[0]+1][data[1]]=-1
    q.append([data[0]+1, data[1], data[2]+1])
  if m[data[0]][data[1]-1]==-2 and S[data[0]][data[1]-1]=='.':
    m[data[0]][data[1]-1]=-1
    q.append([data[0], data[1]-1, data[2]+1])
  if m[data[0]][data[1]+1]==-2 and S[data[0]][data[1]+1]=='.':
    m[data[0]][data[1]+1]=-1
    q.append([data[0], data[1]+1, data[2]+1])

out=0
for x in range(1, H+1):
  for y in range(1, W+1):
    if S[x][y]=='#':
      continue
    q=deque()
    q.append([x, y, 0])
    m=[[-2]*(W+2) for i in range(H+2)]
    while len(q)>0:
      data=q.popleft()
      f(data)
      if data[2]>out:
        out=data[2]
      
print(out)
### BUGGY CODE ###

import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import cmath as cma
import copy as cp
import sys
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf

n,x,y = map(int,input().split())
dist = []
for i in range(1,n+1):
    for j in range(i+1,n+1):
        a = abs(i - j)
        b = abs(i - x) + 1 + abs(j - y)
        c = abs(i - y) + 1 + abs(j - x)
        dist.append(min(a,b,c))

cnt = col.Counter(dist)
for i in range(1,n): print(cnt[i])


### FIXED CODE ###

import collections as col


n,x,y = map(int,input().split())
dist = []
for i in range(1,n+1):
    for j in range(i+1,n+1):
        a = abs(i - j)
        b = abs(i - x) + 1 + abs(j - y)
        c = abs(i - y) + 1 + abs(j - x)
        dist.append(min(a,b,c))

cnt = col.Counter(dist)
for i in range(1,n): print(cnt[i])
### BUGGY CODE ###

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

import itertools

seq=[x for x in range(0,n)]
l=list(itertools.combinations(seq,2))

ans=0

for ll in l:
  ans += a[ll[1]] * a[ll[0]]

print(ans%(10**9+7))

### FIXED CODE ###

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

ans=0
x=0
for i in range(n):
  ans += a[i] * x
  x +=a[i]
print(ans%(10**9+7))
### BUGGY CODE ###

import heapq
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
q = []
for i, b in enumerate(B):
    q.append([-b, i])
heapq.heapify(q)
ans = 0
while q:
    b, idx = heapq.heappop(q)
    b = -b
    #print(b, idx)
    if b==A[idx]:
        continue
    #nb = q[0][0]
    #nb = -nb
    nb = max(B[(idx+1)%N], B[idx-1], B[idx])
    d = B[(idx+1)%N] + B[idx-1]
    p = (b - nb) // d + 1
    b -= p * d
    B[idx] = b
    heapq.heappush(q, [-b, idx])
    ans += p
    # print("b, ans, d =", b, ans, d)
    # print(A)
    # print(B)
    if b < A[idx]:
        B[idx] += d
        #if B[idx]==A[idx]:
        #    continue
        #print("aaaa")
        for a, b in zip(A, B):
            if a!=b:
                print(-1)
                exit()
        else:
            print(ans-1)
            exit()
print(ans)


### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline

# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
q = []
q = [(-b, i) for i, b in enumerate(B)]
heapq.heapify(q)
ans = 0
N_m1 = N-1
while len(q)>0:
    b, idx = q[0]
    b = -b
    b_p1, b_m1 = B[idx+1 if idx<N_m1 else 0], B[idx-1]
    d = b_p1 + b_m1

    a = A[idx]
    p = min((b-a)//d, (b-b_m1)//d+1, (b-b_p1)//d+1)

    b -= p * d
    B[idx] = b
    ans += p
    if b > a:
        heapq.heapreplace(q, (-b, idx))
        if q[0][1] == idx:
            print(-1)
            exit()
    else:
        heapq.heappop(q)
print(ans)
### BUGGY CODE ###

N,K = map(int,input().rstrip().split(" "))
A = [list(map(int,input().rstrip().split(" ")))]
imos = [0 for i in range(N + 1)]
P = 0
flag = True
counter = 0
while flag:
    A.append([0 for i in range(N)])
    P = 0
    for i in range(N+1):
        imos[i] = 0
    for i in range(N):
        imos[max(0,i - A[counter][i])] += 1
        imos[min(N,i + A[counter][i] + 1)] -= 1
    if imos[0] == N and imos[N] == -1 * N:
        flag = False
    for i in range(N):
        P += imos[i]
        A[counter + 1][i] = P
    counter += 1
    if counter == K:
        break
print(" ".join(list(map(str,A[-1]))))

### FIXED CODE ###

N,K = map(int,input().rstrip().split(" "))
A = [list(map(int,input().rstrip().split(" ")))]
imos = [0 for i in range(N + 1)]
P = 0
flag = True
counter = 0
while flag:
    A.append([0 for i in range(N)])
    P = 0
    for i in range(N+1):
        imos[i] = 0
    for i in range(N):
        imos[max(0,i - A[counter][i])] += 1
        imos[min(N,i + A[counter][i] + 1)] -= 1
    if imos[0] == N and imos[N] == -1 * N:
        flag = False
    for i in range(N):
        P += imos[i]
        A[counter + 1][i] = P
    counter += 1
    if counter == K:
        break
print(" ".join(map(str,A[-1])))
### BUGGY CODE ###

from collections import Counter

N = int(input())
s = []
for _ in range(N):
    s_ = list(input())
    s.append(sorted(s_))

counter = []
for i in range(N):
    counter.append(Counter(s[i]))

cnt = 0
for i in range(N-1):
    for j in range(i+1,N):
        if counter[i] == counter[j]:
            cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
s = [sorted(input()) for _ in range(N)]
s.sort()

cnt = 0
ans = 0
for i in range(N-1):
    if s[i] == s[i+1]:
        cnt +=1
        ans += cnt
    else:
        cnt = 0
print(ans)
### BUGGY CODE ###

import itertools
n,x=map(int,input().split())
a=list(map(int,input().split()))
a.append(0)
comb=list(itertools.combinations_with_replacement(a,n))
ans=[]
for i in comb:
    per=sum(i)
    if per==x:
        if 0 in i:
            ans.append(len(set(i))-1)
        else:
            ans.append(len(set(i)))
if len(ans)==0:
    print(0)
else:
    print(max(ans))


### FIXED CODE ###

cnt=0
n,x=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
for i,j in enumerate(a):
    if x>=j:
        x-=j
        cnt+=1
        if i==(n-1) and x>0:
            cnt-=1
print(cnt)
### BUGGY CODE ###

from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import Counter

n=int(input())
l=lnii()

def eratosthenes(lim):
  num=[1 for i in range(lim)]
  for i in l:
    for j in range(i+i,lim,i):
      num[j]=0
  return num

lim=10**6+5
num=eratosthenes(lim)

count=Counter(l)

ans=0
for i in l:
  if num[i]==1 and count[i]==1:
    ans+=1

print(ans)

### FIXED CODE ###

from collections import Counter

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

is_p=[1 for i in range(10**6+1)]

for i in set(a):
  v=i
  if is_p[v]:
    for j in range(v+v,10**6+1,v):
      is_p[j]=0

c=Counter(a)

cnt=0
for i in a:
  if is_p[i]==1 and c[i]==1:
    cnt+=1

print(cnt)
### BUGGY CODE ###

from sys import stdin
from collections import Counter


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    len_S = len(S)
    cnt = 0
    for i in range(len_S):
        for j in range(i+3,len_S):
            if j == i+3:
                mod = int(S[len_S-j-1:len_S-i])%3
            else:
                mod = (mod+int(S[len_S-j-1]))%3
            if mod == 0:
                _ = int(S[len_S-j-1:len_S-i])
                if _%673==0:
                    cnt += 1
                    break
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


def ans():
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    len_S = len(S)
    cnt = 0
    mod_arr = [0]
    for i in range(0,len_S+1):
        _ = int(S[len_S-i-1:])
        if i==0: mod = _%2019
        else: mod = (mod+int(S[len_S-i-1])*10**i)%2019
        mod_arr.append(mod)
    mod_count = Counter(mod_arr)
    for value in mod_count.values():
        if value>1:
            cnt += value*(value-1)//2
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


if __name__ == "__main__":
    #main()
    ans()


### FIXED CODE ###

from sys import stdin


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    len_S = len(S)
    cnt = 0
    for i in range(len_S):
        for j in range(i+3,len_S):
            if j == i+3:
                mod = int(S[len_S-j-1:len_S-i])%3
            else:
                mod = (mod+int(S[len_S-j-1]))%3
            if mod == 0:
                _ = int(S[len_S-j-1:len_S-i])
                if _%673==0:
                    cnt += 1
                    break
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


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

    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = 0
    mod_arr = [0] * 2019
    mod_arr[0] += 1

    num, dec = 0, 1
    for s in S[::-1]:
        num += int(s)*dec
        num %= 2019
        dec *= 10
        dec %= 2019
        mod_arr[num] += 1

    for i in range(2019):
        if mod_arr[i] > 0:
            cnt += mod_arr[i]*(mod_arr[i]-1)//2
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)