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

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
def inpl_str():
    '''
    一行に複数の文字
    '''
    return list(input().split())


s = list(map(int,list(input())[:-1]))
n=len(s)
right = [0] * (n + 1)
for i in range(n):
    right[-i - 2] = (right[-i - 1] + s[-i-1] * 10**i) % 2019

log = defaultdict(lambda: 0)

for i in range(n + 1):
    log[right[-i - 1]] += 1
ans=0
for key,value in log.items():
    if value > 1:
        ans += value * (value - 1) // 2
print(ans)

### FIXED CODE ###

'''
1~9の文字列で構成されたSの中で
i文字目からj文字目までが2019の倍数になっているものの個数を求めよ

terms:
    1<=|S|<=2*10**5

input:
    1817181712114

output:
    3
'''
from collections import defaultdict
import sys
input = sys.stdin.readline
s = input()[:-1]
n=len(s)
arr = [int(s[i]) for i in range(n)]
ans = 0
dic = defaultdict(int)
dic[0] = 1
now = 0
for i in range(n - 1, -1, -1):
    now += arr[i] * pow(10, n - i - 1, 2019)
    now %= 2019
    ans += dic[now]
    dic[now] += 1
print(ans)
### BUGGY CODE ###

N, Ma, Mb = map(int, input().split())
items = []
for i in range(N):
    a, b, c = map(int, input().split())
    items.append((a, b, c))

a_sum = sum([item[0] for item in items])
b_sum = sum([item[1] for item in items])
inf = float("inf")
dp = [[[inf for _ in range(a_sum + 100)] for _ in range(b_sum + 100)] for i in range(N+1)]
dp[0][0][0] = 0

for i in range(N):
    for a in range(a_sum + 1):
        for b in range(b_sum + 1):
            dp[i + 1][a][b] = min(dp[i + 1][a][b], dp[i][a][b])
            dp[i + 1][a + items[i][0]][b + items[i][1]] = min(dp[i + 1][a + items[i][0]][b + items[i][1]],
                                                              dp[i][a][b] + items[i][2])
ans = inf
for a in range(1, a_sum + 1):
    for b in range(1, b_sum + 1):
        if a * Mb == b * Ma:
            ans = min(ans, dp[N][a][b])
if ans != inf:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

N, Ma, Mb = map(int, input().split())
items = []
for i in range(N):
    a, b, c = map(int, input().split())
    items.append((a, b, c))

a_sum = sum([item[0] for item in items])
b_sum = sum([item[1] for item in items])
inf = float("inf")
dp = [[[inf for _ in range(a_sum + 100)] for _ in range(b_sum + 100)] for i in range(N+1)]
dp[0][0][0] = 0

for i in range(N):
    for a in range(a_sum + 1):
        for b in range(b_sum + 1):
            dp[i + 1][a][b] = min(dp[i + 1][a][b], dp[i][a][b])
            dp[i + 1][a + items[i][0]][b + items[i][1]] = min(dp[i + 1][a + items[i][0]][b + items[i][1]],
                                                              dp[i][a][b] + items[i][2])
ans = inf
for a in range(1, a_sum + 1):
    for b in range(1, b_sum + 1):
        if a * Mb == b * Ma:
            ans = min(ans, dp[N][a][b])
if ans != inf:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

S=input()
N=len(S)

remainder=[0]*2019
for i in range(1,N+1):
  s=S[-i:]
  s=int(s)
  remainder[s%2019]+=1

ans=remainder[0]
for i in range(2019):
  if remainder[i]<=1:
    continue
  else:
    ans+=remainder[i]*(remainder[i]-1)//2
print(ans)

### FIXED CODE ###

S=input()
N=len(S)
M=2019

remainder=[0]*M
val=0
for i in range(N):
  val=(int(S[N-1-i])*pow(10,i,M)+val)%M
  remainder[val]+=1

ans=remainder[0]
for i in range(2019):
  ans+=remainder[i]*(remainder[i]-1)//2
print(ans)
### BUGGY CODE ###

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

N, K = map(int, input().split())
p = list(map(int, input().split()))
q = []
max = 0
for i in range(N):
    q.append(p[i]*(p[i]+1)/(2*p[i]))
for i in range(N-K+1):
    v = 0
    for j in range(K):
        v += q[i+j]
    if v > max:
        max = v
print(max)

### FIXED CODE ###

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

N, K = map(int, input().split())
p = list(map(int, input().split()))
q = [0]
for i in range(N):
    q.append(q[-1] + p[i]*(p[i]+1)/(2*p[i]))
print(max([q[i+K]-q[i] for i in range(N-K+1)]))
### BUGGY CODE ###

def dfs():
    pass


def main():
    n,k = map(int, input().split())
    dl = []
    for _ in range(k):
        l,r = map(int, input().split())
        for i in range(l,r+1):
            dl.append(i)

    dl.sort()
    MOD = 998244353
    dp = [0]*(n+1)
    dp[1] = 1
    for i in range(n):
        for d in dl:
            if i+d > n:break
            dp[i+d] += dp[i]
            dp[i+d]%=MOD

    print(dp[n])



if __name__ == "__main__":
    main()

### FIXED CODE ###

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

lrs = []
for _ in range(k):
    l,r = map(int, input().split())
    lrs.append((l,r))

dp = [0]*(n+1)
sdp = [0]*(n+1)
dp[1] = 1
sdp[1] = 1

MOD = 998244353
for i in range(2,n+1):
    # print('------',i)
    for l,r in lrs:
        dr = sdp[i-l] if i-l >= 0 else 0
        dl = sdp[i-r-1] if i-r-1 >= 0 else 0
        # print(dl,dr,'--')
        dp[i] += (dr-dl)
        dp[i] %= MOD        
    sdp[i] = sdp[i-1] + dp[i]
    sdp[i]%=MOD

# print(dp)
print(dp[n])
### BUGGY CODE ###

### https://atcoder.jp/contests/dp/tasks/dp_d
N,W = map(int,input().split())
dp={0:0}
for i in range(N):
    Current_Weight,Current_Value = map(int,input().split())
    if Current_Weight <= W:
        Last_Search_List = list(dp.keys())
        Current_Search_List = list(set(map(lambda x:x+Current_Weight if 
                                           x+Current_Weight <= W else 0, Last_Search_List)))
        Same_Search_List = list(set(Last_Search_List) & set(Current_Search_List))
        Diff_Search_List = list(set(Current_Search_List) - set(Last_Search_List))
        for j in Diff_Search_List:
            Last_Search_Weight = j - Current_Weight
            dp[j] = dp[Last_Search_Weight] + Current_Value
        for j in Same_Search_List:
            if j ==0:
                continue
            Last_Search_Weight = j - Current_Weight
            dp[j] = max(dp[j],dp[Last_Search_Weight] + Current_Value)

print(max(dp.values()))

### FIXED CODE ###

#https://atcoder.jp/contests/dp/tasks/dp_e
import copy
N,W = map(int,input().split())
Goods_List=[]
for i in range(N):
    Goods_List.append(list(map(int,input().split())))
 
Sum_Value = sum(map(lambda x:x[1],Goods_List))
dp = [[0] * (Sum_Value + 1) for i in range(N)]

for i in range(N):
    if i == 0:
        dp[i][Goods_List[i][1]] = Goods_List[i][0]
    else:
        dp[i] = copy.copy(dp[i-1])
        Valid_List = [k for k, x in enumerate(dp[i]) if x != 0]
        Valid_List.append(0)
        for j in Valid_List:
            if dp[i][j + Goods_List[i][1]] == 0:
                dp[i][j + Goods_List[i][1]] = dp[i-1][j] + Goods_List[i][0]
            else:
                dp[i][j + Goods_List[i][1]] = min(dp[i-1][j] + Goods_List[i][0],dp[i][j + Goods_List[i][1]])
        

for k in range(len(dp[-1])-1,0,-1):
    if (dp[-1][k] != 0) & (dp[-1][k] <= W):
        print(k)
        break
### BUGGY CODE ###

inf = float('inf')
V,E,P = map(int,input().split())
edge = []
edge_rev = []
for i in range(E):
    A,B,C = map(int,input().split())
    edge_rev.append([B-1,A-1,P-C])
    edge.append([A-1,B-1,P-C])

d = [inf]*V
d[0] = 0
for i in range(V):
    update = False
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break

d_rev = [inf]*V
d_rev[V-1] = 0
for i in range(V):
    update = False
    for j in range(E):
        From,To,cost = edge_rev[j]
        if d_rev[From] != inf and d_rev[To]>d_rev[From]+cost:
            d_rev[To]=d_rev[From]+cost
            update = True
    if not update:
        break

d_ = [x for x in d]
d_rev_ = [x for x in d_rev]

for i in range(V):
    update = False
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break

for i in range(V):
    update = False
    for j in range(E):
        From,To,cost = edge_rev[j]
        if d_rev[From] != inf and d_rev[To]>d_rev[From]+cost:
            d_rev[To]=d_rev[From]+cost
            update = True
    if not update:
        break

loop = False
for i in range(V):
    if d[i] != 0 and d_rev[i] != 0:
        loop = (d[i]+d_rev[i] != d_[i]+d_rev_[i]) or loop

if loop:
    print(-1)

else:
    ans = -d[-1]
    print(max(0,ans))

### FIXED CODE ###

inf = float('inf')
V,E,P = map(int,input().split())
edge = []
for i in range(E):
    A,B,C = map(int,input().split())
    edge.append([A-1,B-1,P-C])

d = [inf]*V
d[0] = 0
for i in range(V):
    update = False
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break

ans = d[V-1]

for i in range(V):
    update = False
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break
loop = ans != d[V-1]

if loop:
    print(-1)

else:
    ans = -d[-1]
    print(max(0,ans))
### BUGGY CODE ###

s = list(input())
n = len(s)
c = 0
for i in range(n):
  for j in range(n-i-1):
    if s[j] == "B" and s[j+1] == "W":
      s[j] = "W"
      s[j+1] = "B"
      c +=1
print(c)

### FIXED CODE ###

s = list(input())
n = len(s)
i = []
for j in range(n):
  if s[j] == "W":
    i.append(j)
c = 0
for k in range(len(i)):
  c += i[k]-k
print(c)
### BUGGY CODE ###

def solve():
  ans = 0
  N = int(input())
  stacks = [list(map(lambda x:int(x)-1, input().split()))[::-1] for _ in range(N)]
  cnt = 0
  while cnt<N*(N-1)//2:
    lis = [[] for _ in range(N)]
    flag = False
    for i in range(N):
      if not stacks[i]:
        continue
      if lis[i] and stacks[i][-1] in lis[i]:
        stacks[stacks[i][-1]].pop(-1)
        stacks[i].pop(-1)
        cnt += 1
        flag=True
      else:
        lis[stacks[i][-1]].append(i)
    if flag==False:
      return -1
    ans += 1
  return ans
print(solve())

### FIXED CODE ###

def solve():
  ans = 0
  N = int(input())
  stacks = [list(map(lambda x:int(x)-1, input().split()))[::-1] for _ in range(N)]
  lis = [0]*N
  cnt = 0
  now = 0
  flag = 0
  while cnt<N*(N-1)//2:
    while not stacks[now]:
      now = (now+1)%N
    a = stacks[now][-1]
    while not stacks[a]:
      now = (now+1)%N
      a = stacks[now][-1]
    if stacks[a][-1] == now:
      lis[now] = max(lis[now],lis[a])+1
      lis[a] = lis[now]
      stacks[a].pop(-1)
      stacks[now].pop(-1)
      cnt += 1
      flag = 0
    else:
      now = a
      flag += 1
    if flag==N:
      return -1
  ans = max(lis)
  return ans
print(solve())
### BUGGY CODE ###

def main():
    n = int(input())
    p = list(map(int, input().split()))
    count = 0
    for i in range(n):
        for j in range(i):
            if p[i] > p[j]:
                count += 1
                break

    print(n - count)


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    p = list(map(int, input().split()))
    count = 0
    min_num = n+1
    for i in p:
        if i < min_num:
            min_num = i
            count += 1
    print(count)


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

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

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**9
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


p = 1000000007

def abp(a, b, p):
    if b == 0:
        return 1
    if b % 2 == 0:
        tmp = abp(a, b // 2, p)
        return (tmp * tmp) % p
    if b % 2 == 1:
        return (a * abp(a, b - 1, p)) % p

total = (abp(2, n, p) - cmb(n, a, p) - cmb(n, b, p) - 1) % p
print(total)


### FIXED CODE ###

def abp(a, b, p):
    if b == 0:
        return 1
    if b % 2 == 0:
        tmp = abp(a, b // 2, p)
        return (tmp * tmp) % p
    if b % 2 == 1:
        return (a * abp(a, b - 1, p)) % p

def nCr(n, r, p):
    total = 1
    for i in range(r):
        total *= (n - i) * abp(r - i, p - 2, p)
        total %= p
    return total

n, a, b = map(int, input().split())
p = 1000000007
ret = abp(2, n, p) - nCr(n, a, p) - nCr(n, b, p) - 1
print(ret % p)
### BUGGY CODE ###

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

for i in range(N):
  print(A[i:].count(i+1))

### FIXED CODE ###

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

ans = [0] * N

for i in range(len(A)):
  ans[A[i]-1] += 1

for i in range(len(ans)):
  print(ans[i])
### BUGGY CODE ###

#!/usr/bin/env python3
n, m, k = map(int, input().split())
a = [0]+list(map(int, input().split()))
b = [0]+list(map(int, input().split()))
for i in range(1,n+1):
    a[i]= a[i-1]+ a[i]

for i in range(1,m+1):
    b[i]= b[i-1]+ b[i]

ans = 0
t = 0
for i in range(n + 1):
    for j in range(m + 1):
        if a[i] + b[j] <= k:
            ans = max(ans, i + j)
        else:
            break
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
A = [0]
B = [0]
for i in range(n):
    A.append(A[i] + a[i])
for i in range(m):
    B.append(B[i] + b[i])
ans = 0
j = m
for i in range(n + 1):
    if A[i] > k:
        break
    while j > 0 and k - A[i] < B[j]:
        j -= 1
    ans = max(ans, i + j)

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

import sys
n = int(input())
a_ls = [int(i) for i in sys.stdin.readline().split()]
MOD = 10**9+7
def gcd(a, b):
    while a and b:
        if a > b:
            a %= b
        else:
            b %= a
    return max(a, b)

def lcm(a, b):
    _gcd = gcd(a, b)
    return a * b // _gcd

_a = a_ls[0]
for a in a_ls:
    _a = lcm(_a, a)
ls = [_a // a for a in a_ls]
print(sum(ls) % MOD)

### FIXED CODE ###

import sys
n = int(input())
a_ls = [int(i) for i in sys.stdin.readline().split()]
MOD = 10**9+7
def gcd(a, b):
    while a and b:
        if a > b:
            a %= b
        else:
            b %= a
    return max(a, b)

def lcm(a, b):
    _gcd = gcd(a, b)
    return a * b // _gcd

_a = a_ls[0]
for a in a_ls:
    _a = lcm(_a, a)
ls = [_a // a for a in a_ls]
print(sum(ls) % MOD)
### BUGGY CODE ###

import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
Q = int(input())
BC= [list(map(int,input().split())) for _ in range(Q)]

for b,c in BC:
    A[A == b] = c
    print(np.sum(A))


### FIXED CODE ###

import numpy as np

from collections import defaultdict
N = int(input())
A = tuple(map(int, input().split()))
Q = int(input())
BC= [list(map(int,input().split())) for _ in range(Q)]

counter = defaultdict(int)
for x in A:
    counter[x] += 1

total = sum(A)
for b, c in BC:
    total += (c - b) * counter[b]
    counter[c] += counter[b]
    counter[b] = 0
    print(total)
### BUGGY CODE ###

from scipy.misc import comb
n, a, b = map(int, input().split())
l = [comb(n, k, exact = True) % (10**9 + 7) for k in range(1, n + 1)]
ans = 0
for i in range(n):
    if i != a - 1 and i != b - 1:
        ans += l[i]
print(ans)


### FIXED CODE ###

MOD = pow(10, 9) + 7

def modinv(a, mod):
    return pow(a, mod - 2, mod) % mod

def comb(n, r, mod):
    r = min(r, n - r)
    res = 1
    for i in range(r):
        res = res * (n - i) % mod
        res = res * modinv(i + 1, mod) % mod
    return res

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

ans = (pow(2, n, MOD) - 1 - comb(n, a, MOD) - comb(n, b, MOD)) % MOD

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

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

while(1):

    num = box.index(min(box))#最小値のインデックス
    #print(num,box)
    for index,item in enumerate(box):
    
        if num != index:
        
            if item % min(box) == 0:
                box.remove(item)
            else:
                box[index] = item % min(box)

    if len(box) == 1:
        break

print(box[0],end='')

### FIXED CODE ###

from fractions import gcd

n = int(input())
a = list(map(int,input().split()))
ans = a[0]

for i,item in enumerate(a):
    if i != 0:
        ans = gcd(ans,item)

print(ans,end='')
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import deque

n, k = map(int, input().split())
radius = k // 2
edge = [[] for _ in range(n)]
uv = []
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)
    uv.append((a, b))

def dfs(p, v, d):
    ret = 0
    st = []
    st.append((p, v, d))
    while st:
        p, v, d = st.pop()
        if d > radius:
            ret += 1
        for nv in edge[v]:
            if nv == p:
                continue
            st.append((v, nv, d+1))
    return ret

ans = n 
if k % 2 == 0:
    for i in range(n):
        ret = dfs(-1, i, 0)
        ans = min(ans, ret)
else:
    for u, v in uv:
        ret = dfs(u, v, 0) + dfs(v, u, 0)
        ans = min(ans, ret)

print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
from collections import deque

n, k = map(int, input().split())
radius = k // 2
edge = [[] for _ in range(n)]
uv = []
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)
    uv.append((a, b))

def dfs(p, v, d):
    ret = 0
    for nv in edge[v]:
        if nv == p:
            continue
        ret += dfs(v, nv, d+1)
    if d > radius:
        return ret + 1
    else:
        return ret

ans = n 
if k % 2 == 0:
    for i in range(n):
        ret = dfs(-1, i, 0)
        ans = min(ans, ret)
else:
    for u, v in uv:
        ret = dfs(u, v, 0) + dfs(v, u, 0)
        ans = min(ans, ret)

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

import sys
import math
#from me.io import dup_file_stdin

primes = [2,3,5,7]

def isPrime(x):
    if x<=primes[-1]:
        return x in primes
    else:
        for prime in primes:
            if x%prime==0:
                return False
        else:
            current=primes[-1]
            dst=math.sqrt(x)
            while current<dst:
                if(x%current==0):
                    return False
            else:
                return True

#@dup_file_stdin
def solve():
    for query in map(int,sys.stdin):
        if(query>primes[-1]):
            for i in range(primes[-1]+1,query+1):
                if isPrime(i):
                    primes.append(i);
        print(len([x for x in primes if x<=query]))
solve()

### FIXED CODE ###

import sys
#from me.io import dup_file_stdin

N=1000000
primes = [1]*N
primes[0:2]=[0,0,1]

for i in range(2,N):
    if primes[i]==1:
        j=i+i
        while j<=N:
            primes[j]=0
            j+=i

#@dup_file_stdin
def solve():
    for query in map(int,sys.stdin):
        print(sum(primes[2:query+1]))
solve()
### BUGGY CODE ###

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

ans=0
for i in range(max(a),0,-1):
	x = a.count(i)
	if x-i>=0:
		ans += x-i
	else:
		ans += x
print(ans)


### FIXED CODE ###

N = int(input())
a = map(int,input().split())
dic={}

ans=0
for i in a:
	dic.setdefault(i,0)
	dic[i]+=1
for a,b in dic.items():	
	if b-a>=0:
		ans += b-a
	else:
		ans += b
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
if __name__ == "__main__":
    N,M,Q = map(int,input().split())
    acc = [[0]*(N+1) for _ in range(N+1)]
    for _ in range(M):
        l,r = map(int,input().split())
        acc[l][r] += 1
    pqs = []
    for _ in range(Q): 
        p,q = map(int,input().split())
        pqs.append((p,q))
    for i in range(N):
        for j in range(1, N+1):
            acc[i][j] += acc[i][j-1]
    for p,q in pqs:
        ans = 0
        for i in range(p,q+1):
            ans += acc[i][q]-acc[i][p-1]
        print(ans)

### FIXED CODE ###

N,M,Q = map(int,input().split())
plane = [[0]*N for _ in range(N)]
for i in range(M):
    l,r = map(int,input().split())
    plane[l-1][r-1] += 1
acc = [[0]*(N+1) for _ in range(N)]

for i in range(N):
    for j in range(N):
        acc[i][j+1] = acc[i][j]+plane[i][j]

for i in range(Q):
    p,q = map(int,input().split())
    tmp = 0
    for j in range(p,q+1):
        tmp += acc[j-1][q]-acc[j-1][p-1]
    print(tmp)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

from queue import deque

def main():
  h, w = map(int, input().split())
  grids = [list(input().strip()) for _ in range(h)]
  dq = deque()
  for i in range(h):
    for j in range(w):
      if grids[i][j] == '#':
        dq.append((0, i, j))
  
  mcnt = -1
  while dq:
    cnt, i, j = dq.popleft()
    mcnt = cnt if cnt > mcnt else mcnt
    for dx, dy in zip([-1, 0, 1, 0], [0, -1, 0, 1]):
      if 0 <= i+dx < h and 0 <= j+dy < w and grids[i+dx][j+dy] == '.':
        grids[i+dx][j+dy] = '#'
        dq.append((cnt+1, i+dx, j+dy))
  print(cnt)
  
if __name__=='__main__':
  main()



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

from queue import deque

def main():
  h, w = map(int, input().split())
  grids = [False] * (w * h)
  dq = deque()
  for i in range(h):
    for j, c in enumerate(list(input().strip())):
      if c == '#':
        grids[i*w + j] = True
        dq.append((0, i, j))
  
  while dq:
    cnt, i, j = dq.popleft()
    for dx, dy in zip([-1, 0, 1, 0], [0, -1, 0, 1]):
      if 0 <= i+dx < h and 0 <= j+dy < w and not grids[(i+dx)*w + (j+dy)]:
        grids[(i+dx)*w + (j+dy)] = True
        dq.append((cnt+1, i+dx, j+dy))
  print(cnt)
  
if __name__=='__main__':
  main()
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
for i in range(n):
  ans = 0
  tmp = 0
  for j in range(n):  
    if i != j:
      ans += abs(tmp - a[j])
      tmp = a[j]
  print(ans+abs(tmp))

### FIXED CODE ###

n = int(input())
a = [0]+[int(i) for i in input().split()]+[0]
ans = sum(abs(a[i+1] - a[i]) for i in range(n+1))
for i in range(1, n+1):
  print(ans - abs(a[i+1] - a[i]) - abs(a[i] - a[i-1]) + abs(a[i+1] - a[i-1]))
### 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)]
dp = [[{} for _ in range(W)] for _ in range(H)]
dp[0][0][abs(A[0][0]-B[0][0])] = 0
for h in range(H-1):
    for w in range(W-1):
        for v in dp[h][w]:
            dp[h][w+1][abs(v+A[h][w+1]-B[h][w+1])] = 0
            dp[h][w+1][abs(v-A[h][w+1]+B[h][w+1])] = 0
            dp[h+1][w][abs(v+A[h+1][w]-B[h+1][w])] = 0
            dp[h+1][w][abs(v-A[h+1][w]+B[h+1][w])] = 0
for v in dp[H-1][W-2]:
    dp[H-1][W-1][abs(v+A[H-1][W-1]-B[H-1][W-1])] = 0
    dp[H-1][W-1][abs(v-A[H-1][W-1]+B[H-1][W-1])] = 0
for v in dp[H-2][W-1]:
    dp[H-1][W-1][abs(v+A[H-1][W-1]-B[H-1][W-1])] = 0
    dp[H-1][W-1][abs(v-A[H-1][W-1]+B[H-1][W-1])] = 0
ans = min(dp[H-1][W-1])
print(ans)

### FIXED 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)]
D = [[abs(A[h][w]-B[h][w]) for w in range(W)] for h in range(H)]
def cal():
    dp1 = [set() for _ in range(W)]
    dp2 = [set() for _ in range(W)]
    for h in range(H):
        for w in range(W):
            d = D[h][w]
            if h==0 and w==0:
                dp2[0].add(d)
            for v in dp1[w]:
                v1 = v+d
                v2 = v-d if v>=d else -v+d
                dp2[w].add(v1)
                dp2[w].add(v2)
            if 0 < w:
                for v in dp2[w-1]:
                    v1 = v+d
                    v2 = v-d if v>=d else -v+d
                    dp2[w].add(v1)
                    dp2[w].add(v2)
        dp1 = dp2
        dp2 = [set() for _ in range(W)]
    return min(dp1[W-1])
ans = cal()
print(ans)