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

import numpy as np

def read():
    N, X, Y = list(map(int, input().split()))
    return N, X, Y

def solve(N, X, Y):
    INF = N + N
    X -= 1
    Y -= 1
    e = np.ones((N, N), dtype=np.int32) * INF
    for i in range(N-1):
        e[i, i+1] = 1
        e[i+1, i] = 1
    e[X, Y] = 1
    e[Y, X] = 1

    c = [0 for i in range(N)]

    for i in range(N):
        for j in range(i+1, N):
            if j <= X or Y <= i:
                e[i, j] = j - i
            else:
                e[i, j] = min(abs(j-i), abs(X-i) + 1 + abs(Y-j))
    
    for i in range(N):
        for j in range(i+1, N):
            if e[i, j] < INF:
                c[e[i, j]] += 1

    for i in range(1, N):
        print(c[i])

if __name__ == '__main__':
    inputs = read()
    solve(*inputs)


### FIXED CODE ###

def read():
    N, X, Y = list(map(int, input().split()))
    return N, X, Y

def solve(N, X, Y):
    INF = N + N
    X -= 1
    Y -= 1
    e = [[INF for j in range(N)] for i in range(N)]
    for i in range(N-1):
        e[i][i+1] = 1
        e[i+1][i] = 1
    e[X][Y] = 1
    e[Y][X] = 1

    c = [0 for i in range(N)]

    for i in range(N):
        for j in range(i+1, N):
            if j <= X or Y <= i:
                e[i][j] = j - i
            else:
                e[i][j] = min(abs(j-i), abs(X-i) + 1 + abs(Y-j))
    
    for i in range(N):
        for j in range(i+1, N):
            if e[i][j] < INF:
                c[e[i][j]] += 1

    for i in range(1, N):
        print(c[i])

if __name__ == '__main__':
    inputs = read()
    solve(*inputs)
### BUGGY CODE ###

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix, lil_matrix
import sys
input = sys.stdin.readline
n,m,s,t = map(int, input().split())
money = lil_matrix((n+1, n+1), dtype = int)
snu = lil_matrix((n+1, n+1), dtype = int)
for i in range(m):
    u,v,a,b = map(int, input().split())
    money[u,v] = money[v,u] = a
    snu[u,v] = snu[v,u] = b
money = dijkstra(money)
snu = dijkstra(snu)
start = 10**15
#何年目か？
ans = []
ans_max = 10**15
for j in range(n,-1,-1):
    ans_max = min(ans_max, (money[s][j] + snu[j][t]))
    ans.append(ans_max)
for i in range(n-1,-1,-1):
    print(int(start - ans[i]))

### FIXED CODE ###

import numpy as np
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
def dijkstra(start, mode):
    INF = 10 ** 15
    dist = [INF] * (n+1)
    dist[start] = 0
    q = [(0,start)]
    while q:
        d,v = heappop(q)
        if dist[v] < d:
            continue
        for w,*a in graph[v]:
            d1 = d + a[mode]
            if dist[w] > d1:
                dist[w] = d1
                heappush(q, (d1,w))
    return dist

n,m,s,t = map(int, input().split())
graph = [[] for i in range(n+1)]
for i in range(m):
    u,v,a,b = map(int, input().split())
    graph[u].append([v,a,b])
    graph[v].append([u,a,b])
money = dijkstra(s,0)
snu = dijkstra(t,1)
start = 10**15
#何年目か？
ans = []
ans_max = 10**15
for j in range(n,-1,-1):
    ans_max = min(ans_max, (money[j] + snu[j]))
    ans.append(ans_max)
for i in range(n-1,-1,-1):
    print(int(start - ans[i]))
### BUGGY CODE ###

n = int(input())
S = []
for i in range(n):
    S.append(int(input()))
ans = []
import itertools
for i in itertools.product(range(2), repeat=n):
    scr = 0
    for j in range(n):
        if i[j]:
            scr += S[j]
    if scr%10 == 0:
        scr = 0
    ans.append(scr)
print(max(ans))

### FIXED CODE ###

n = int(input())
S = sorted([int(input()) for _ in range(n)])

if sum(S)%10!=0:
    print(sum(S))
    exit()
for i in range(n):
    if S[i]%10==0:
        continue
    print(sum(S)-S[i])
    exit()
print(0)
### BUGGY CODE ###

N = input()
S=[]
for i in range(int(N)):
    S.append(input())

ls=[]
for i in S:
    if i not in ls:
        ls.append(i)
str_ls =[]
num_ls = []

for i in ls:
    num_ls.append(S.count(i))


for i in range(len(ls)):
    if num_ls[i] == max(num_ls):
        str_ls.append(ls[i])

str_ls.sort()
for i in str_ls:
    print(i)

### FIXED CODE ###

from collections import defaultdict
from collections import OrderedDict
N = int(input())
ans = dict()
for _ in range(N):
    k = str(input())
    if k in ans:
        ans[k]+=1
    else:
        ans.update({k:1})
groupedByValue = defaultdict(list)
for key, value in sorted(ans.items()):
    groupedByValue[value].append(key)
l = groupedByValue[max(groupedByValue)]
for i in l:
    print(i)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
acIdx = []
i = -1
while True:
    i = s.find('AC', i+1)
    if i == -1:
        break
    acIdx.append(i+1)

for i in range(q):
    l, r = map(int, input().split())
    print(len(list(filter(lambda x: l <= x <= (r-1), acIdx))))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
cnt = 0
acIdx = [0]
for i in range(n-1):
    if s[i] == 'A' and s[i+1] == 'C':
        cnt += 1
    acIdx.append(cnt)

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

a = [int(x) for x in input().split()]
weight = a[1]
dp = [0] * weight + [0]
for x in range(a[0]):
    b = [int(x) for x in input().split()]
    for x in range(weight, b[0] - 1, -1):
        dp[x] = max(dp[x], dp[x - b[0]] + b[1])
print(dp[-1])


### FIXED CODE ###

N, W = map(int, input().split())
import numpy as np
dp = np.zeros(W+1, dtype=int)
for i in range(N):
    w, v = map(int, input().split())
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
print(dp.max())
### BUGGY CODE ###

N=int(input())
As=list(map(int,input().split()))
ans=1

if 0 in As:
    print(0)
else:
    for i in range(N):
        ans*=As[i]
    print(ans if ans<=int(1e18) else -1)

### FIXED CODE ###

N=int(input())
As=list(map(int,input().split()))
ans=1

if 0 in As:
    print(0)
else:
    for i in range(N):
        ans*=As[i]
        if ans>int(1e18):
            break
    print(ans if ans<=int(1e18) else -1)
### BUGGY CODE ###

#input
S = str(input())

#output
from collections import Counter
#2019 = 3 * 673
N = len(S)
#上からi桁目までの数を決めた時2019の個数をdp[i]とする。
dp = [0] * (N+1)
dp[1] = int(S[-1])
for i in range(1, N):
    dp[i+1] = (dp[i] + int(S[-(i+1)]) * 10**i) % 2019

T = Counter(dp[1:])

answer = 0
answer += T[0]

for t in T.values():
    answer += t*(t-1)//2

print(answer)

### FIXED CODE ###

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

#output
from collections import Counter
#2019 = 3 * 673
N = len(S)
#上からi桁目までの数を決めた時2019の個数をdp[i]とする。
dp = [0] * (N)
dp[0] = int(S[0])
times =10
for i in range(N-1):
    dp[i+1] = dp[i] + times * int(S[i+1])
    dp[i+1] %= 2019
    times *= 10
    times %= 2019

T = Counter(dp)

answer = T[0]

for t in T.values():
    answer += t*(t-1)//2

print(answer)
### BUGGY CODE ###

# 初期入力
import numpy as np 
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A.sort()
A_np =np.array(A,dtype=np.int64)
A_set =set(A)
count =set()
for i in range(N):
    if np.any(A[i] %A_np[:i] ==0) :
            count.add(A[i])
ans =len(A_set - count)
print(ans)

### FIXED CODE ###


2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

	

from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))
cnt = Counter(A)
A.sort()
ans = 0
MX = 10**6
P = [0] * (MX+1)
for a in A:
    if P[a]==0:
        for i in range(MX+1):
            x = a*i
            if x > MX:
                break
            P[x] = 1
        if cnt[a]==1:
            ans+=1
print (ans)
### BUGGY CODE ###

n = int(input())
p = 1
for i in range(1, n+1):
   p = p * i
print(p%(10**9+7))

### FIXED CODE ###

n = int(input())
p = 1
for i in range(1, n+1):
   p = p * i
   p = p % (10**9+7)
print(p)
### BUGGY CODE ###

def sigma(n):
    return sum([i for i in range(n+1)])

def main():
    N, K = map(int, input().split(' '))
    p = list(map(int, input().split(' ')))

    max_value = 0
    for i in range(N-K+1):
        sum_ = sum(p[i:i+K])
        if sum_ > max_value:
            max_value = sum_
            max_list = p[i:i+K]

    expected = 0
    for v in max_list:
        expected += sigma(v) / v

    print(expected)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    p = list(map(int, input().split()))

    p = [(p_i+1)/2 for p_i in p]
    ans = 0
    for i in range(N-K+1):
        if i == 0:
            sum_ = sum(p[i:i+K])
        else:
            sum_ = sum_ + p[i+K-1] - p[i-1]
        ans = max(ans, sum_)

    print(ans)

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

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

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

# solve
A.sort()
for i in range(M):
    A[-1] = A[-1] // 2
    A.sort()

# output
print(sum(A))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import heapq

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

# solve
ans = [-a for a in A]
heapq.heapify(ans)
for i in range(M):
    tmp = heapq.heappop(ans) * (-1) // 2
    heapq.heappush(ans, tmp * (-1))
ans = [-a for a in ans]

# output
print(sum(ans))
### BUGGY CODE ###

from sys import stdin, setrecursionlimit


def cmb(n, r, mod=10 ** 9 + 7):
    r = min(r, n - r)
    x = y = 1
    for i in range(r):
        x *= n - i
        x %= mod
        y *= i + 1
        y %= mod
    return x * pow(y, mod - 2, mod) % mod


def main():
    mod = 10 ** 9 + 7
    n, k = map(int, stdin.readline().split())
    a = list(map(int, stdin.readline().split()))
    a.sort()
    ans = 0
    a_cmb = [0] * n
    for i in range(n):
        a_cmb[i] = cmb(i, k - 1, mod)
    for i in range(n - k + 1):
        ans -= a[i] * a_cmb[n - 1 - i]
    for i in range(k - 1, n):
        ans += a[i] * a_cmb[i]
    print(ans % mod)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

### FIXED CODE ###

from sys import stdin, setrecursionlimit


def main():
    mod = 10 ** 9 + 7
    n, k = map(int, stdin.readline().split())
    a = list(map(int, stdin.readline().split()))
    a.sort()
    ans = 0

    m = n + 1

    fac = [0] * m
    finv = [0] * m
    inv = [0] * m

    def initialize_cmb(m):
        fac[0] = 1
        finv[0] = 1
        if m > 1:
            fac[1] = 1
            finv[1] = 1
            inv[1] = 1
            for i in range(2, m):
                fac[i] = fac[i-1] * i % mod
                inv[i] = mod - inv[mod % i] * (mod // i) % mod
                finv[i] = finv[i - 1] * inv[i] % mod

    def cmb(n, k, mod=10 ** 9 + 7):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod

    initialize_cmb(m)

    for i in range(n - k + 1):
        ans -= a[i] * cmb(n - 1 - i, k - 1)
        ans %= mod
    for i in range(k - 1, n):
        ans += a[i] * cmb(i, k - 1)
        ans %= mod
    print(ans % mod)


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

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

sum=1

for i in range(a):
    sum = sum*li[i]

if sum <= 10**18:
    print(sum)
else:
    print(-1)


### FIXED CODE ###

#１文字をインプット
a=int(input())
#1行をint型でインプット
li = list(map(int,input().split()))

#初期値をセット
sum=1

#リストに入っている分だけ掛ける
if 0 in li:#もしリストに0が入っていたら合計を0にして、34行目へ
    sum = 0
else:
    for i in range(a):
        sum = sum*li[i]
        if sum > 10**18:
            break

if sum <= 10**18:#10の18乗以下の場合、答えを出力
    print(sum)
else:#10の18乗を超える場合、'-1'を出力
    print(-1)
### BUGGY CODE ###

#C

N,Q =map(int,input().split())
S = input()
List=[[int(j) for j in input().split()] for i in range(1,Q+1)]
for i in range(Q):
    print(S[List[i][0]-1:List[i][1]].count("AC"))

### FIXED CODE ###

#122 C
N,Q= map(int,input().split())
S=input()
ans=[0]*(N+1)

for i in range(2,N+1):
    ans[i]=ans[i-1]
    if S[i-2:i]=='AC':
        ans[i]+=1
    
for i in range(Q):
    l,r=map(int,input().split())
    print(ans[r]-ans[l])
### BUGGY CODE ###

n = int(input())
aa = list(map(int, input().split()))
bb = list(map(int, input().split()))

rates_list = [[],[]]
for i in range(3):
	if aa[i] > bb[i]:
		rates_list[1].append([bb[i], aa[i]])
	else:
		rates_list[0].append([aa[i], bb[i]])

max_d = n
for j in range(2):
	rates = rates_list[j]
	if len(rates) > 0:
		dp = [(d // rates[0][0]) * rates[0][1] + d % rates[0][0] for d in range(max_d + 1)]
		for d in range(1, max_d + 1):
			dp[d] = max([dp[d]] + [dp[d - rates[i][0]] + rates[i][1] if d - rates[i][0] >= 0 else d for i in range(1, len(rates))])
		max_d = dp[-1]
print (max_d)


### FIXED CODE ###

n = int(input())
aa = list(map(int, input().split()))
bb = list(map(int, input().split()))

rates_list = [[],[]]
for i in range(3):
	if aa[i] > bb[i]:
		rates_list[1].append([bb[i], aa[i]])
	else:
		rates_list[0].append([aa[i], bb[i]])

max_d = n
for j in range(2):
	rates = rates_list[j]
	if len(rates) == 1:
		max_d = (max_d // rates[0][0]) * rates[0][1] + max_d % rates[0][0]
	elif len(rates) == 2:
		val = [rates[0][1] * i for i in range(max_d // rates[0][0] + 1)]
		rest = [max_d - rates[0][0] * i for i in range(max_d // rates[0][0] + 1)]
		val = [val[i] + rates[1][1] * (rest[i] // rates[1][0]) + (rest[i] % rates[1][0]) if rest[i] > 0 else val[i] for i in range(len(val))]
		max_d = max(val)
	elif len(rates) == 3:
		dp = [(d // rates[0][0]) * rates[0][1] + d % rates[0][0] for d in range(max_d + 1)]
		for d in range(1, max_d + 1):
			dp[d] = max([dp[d]] + [dp[d - rates[i][0]] + rates[i][1] if d - rates[i][0] >= 0 else d for i in range(1, len(rates))])
		max_d = dp[-1]
print (max_d)
### BUGGY CODE ###

s = str(input())
t = str(input())

dp = [[-1]*3100 for _ in range(3100)]
# dp[i+1][j+1]: s[i], t[j]まで見たときのLCSの長さ

dp[0][0] = 0
for i in range(len(s)):
  for j in range(len(t)):
    if s[i] == t[j]:
      dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
    dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
    dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])
    
i = len(s)
j = len(t)
ans = ''
while i>0 and j>0:
  if dp[i][j] == dp[i-1][j]:
    i -= 1
  elif dp[i][j] == dp[i][j-1]:
    j -= 1
  else:
    ans = s[i-1] + ans
    i -= 1
    j -= 1
print(ans)

### FIXED CODE ###

s = str(input())
t = str(input())

dp = [[0]*3100 for _ in range(3100)]
# dp[i+1][j+1]: s[i], t[j]まで見たときのLCSの長さ

for i in range(len(s)):
  for j in range(len(t)):
    if s[i] == t[j]:
      dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
    dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
    dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])

i = len(s)
j = len(t)
ans = ''
while i>0 and j>0:
  if dp[i][j] == dp[i-1][j]:
    i -= 1
  elif dp[i][j] == dp[i][j-1]:
    j -= 1
  else:
    ans = s[i-1] + ans
    i -= 1
    j -= 1
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
num = 0
while True:
  num = N
  N = abs(N - K)
  if N >= num:
    print(num)
    break

### FIXED CODE ###

N,K = map(int,input().split())
ans1 = N % K
ans2 = abs(ans1 - K)
if ans1 <= ans2:
  print(ans1)
else:
  print(ans2)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from bisect import bisect_left
 
n, m, q = map(int, input().split())
LR = [0]*m
for i in range(m):
    LR[i] = list(map(int, input().split()))
P = [0]*q
Q = [0]*q
for i in range(q):
    P[i], Q[i] = map(int, input().split())
 
LR.sort(key=lambda x: (x[0], x[1]))
L = list(map(lambda x: x[0], LR))
#print(LR)
 
C = [[0]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
    l = bisect_left(L, i)
    r = bisect_left(L, i+1)-1
    R2 = list(map(lambda x: x[1], LR[l:r+1]))
    #print(l, r, R2)
    for j in range(i,n+1):
        C[i][j] = bisect_left(R2, j+1)
    #print(i, C[i])
 
for i in range(q):
    ans = 0
    for j in range(P[i], Q[i]+1):
        ans += C[j][Q[i]]
    print(ans)

### FIXED CODE ###

from bisect import bisect_left
 
n, m, q = map(int, input().split())
LR = [0]*m
for i in range(m):
    LR[i] = list(map(int, input().split()))
P = [0]*q
Q = [0]*q
for i in range(q):
    P[i], Q[i] = map(int, input().split())
 
LR.sort(key=lambda x: (x[0], x[1]))
L = list(map(lambda x: x[0], LR))
#print(LR)
 
C = [[0]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
    l = bisect_left(L, i)
    r = bisect_left(L, i+1)-1
    R2 = list(map(lambda x: x[1], LR[l:r+1]))
    #print(l, r, R2)
    for j in range(i,n+1):
        C[i][j] = bisect_left(R2, j+1)
    #print(i, C[i])
 
for i in range(q):
    ans = 0
    for j in range(P[i], Q[i]+1):
        ans += C[j][Q[i]]
    print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
A = [int(a) for a in input().split()]
OneNum = [0] * 40
for a in A:
    for i in range(40):
        if a & (1 << i) == 2**i: OneNum[-1-i] += 1

def digDP(digit, rem, memo):
    if digit == 39:
        if rem == 0: return OneNum[-1]
        else:
            return max(OneNum[-1], N - OneNum[-1])
    try: return memo[(digit, rem)]
    except KeyError:
        if 2 ** (39 - digit) > rem:
            ans = 2 ** (39-digit) * OneNum[digit] + digDP(digit+1, rem, memo)
            memo[(digit, rem)] = ans
            return ans
        else:
            useDigit = 2 ** (39-digit) * (N-OneNum[digit]) + digDP(digit + 1, rem - (2**(39-digit)), memo)
            notUseDigit = 2 ** (39-digit) * OneNum[digit] + digDP(digit + 1, rem, memo)
            memo[(digit, rem)] = max(useDigit, notUseDigit)
            return max(useDigit, notUseDigit)

memo = {}
print(digDP(0, K, memo))

### FIXED CODE ###

N, K = map(int, input().split())
bitK = format(K, "b").zfill(41)
A = [int(a) for a in input().split()]
DP = [[0, 0] for _ in range(41)] #DP[i][0]は上位i bit目までKと一致、DP[i][1]はK以下
Ones = [0] * 41
for a in A:
    bita = format(a, "b").zfill(41)
    for i in range(41):
        Ones[i] += int(bita[i])

if bitK[0] == "1":
    DP[0][0] = (2 ** 40) * (N - Ones[0])
    DP[0][1] = (2 ** 40) * Ones[0]
else:
    DP[0][0] = (2 ** 40) * Ones[0]
    DP[0][1] = 0

for i in range(1, 41):
    oneNum = Ones[i]
    digit = 2**(40-i)
    if bitK[i] == "1":
        DP[i][0] = DP[i-1][0] + digit * (N - oneNum)
        DP[i][1] = DP[i-1][0] + digit*oneNum
        if DP[i-1][1] > 0:
            DP[i][1] = max(DP[i][1], DP[i-1][1] + digit*max(oneNum, N-oneNum))
    else:
        DP[i][0] = DP[i-1][0] + digit*oneNum
        if DP[i-1][1] > 0:
            DP[i][1] = DP[i-1][1] + digit*max(oneNum, N-oneNum)

print(max(DP[-1]))
### BUGGY CODE ###

N, Q= map(int, input().split())
S = input()
D = []
for i in range(Q):
    l, r = map(int, input().split())
    D.append([l,r])

ans=[]
for l, r in D:
    s = S[l-1:r]
    ans.append(s.count("AC"))

for a in ans:
    print(a)


### FIXED CODE ###

N, Q= map(int, input().split())
S = input()
D = []
for i in range(Q):
    l, r = map(int, input().split())
    D.append([l,r])

c =[0]*N
for i in range(N-1):
    if S[i:i+2] == "AC":
        c[i+1]=c[i]+1
    else:
        c[i+1]=c[i]
for l, r in D:
    print(c[r-1]-c[l-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
h,w=map(int,input().split())
a=[]
for i in range(h):
    a.append(list(map(int,input().split())))
b=[]
for i in range(h):
    b.append(list(map(int,input().split())))
dp=[[set([]) for i in range(w)] for j in range(h)]
dp[0][0].add(a[0][0]-b[0][0])
dp[0][0].add(b[0][0]-a[0][0])
for i in range(h):
    for j in range(w):
        if i==j==0:
            continue
        if i==0:
            for k in dp[i][j-1]:
                dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                dp[i][j].add(abs(k+b[i][j]-a[i][j]))
        elif j==0:
            for k in dp[i-1][j]:
                dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                dp[i][j].add(abs(k+b[i][j]-a[i][j]))
        else:
            for k in (dp[i][j-1]|dp[i-1][j]):
                if k<=80*80*80:
                    dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                    dp[i][j].add(abs(k+b[i][j]-a[i][j]))             
#dp[h-1][w-1]
ans=10**10
for i in dp[h-1][w-1]:
    ans=min(ans,abs(i))
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
H,W=map(int,input().split())
a = [[] for _ in range(H)]
for i in range(H):
    a[i] = list(map(int, input().split()))
b = [[] for _ in range(H)]
for i in range(H):
    b[i] = list(map(int, input().split()))

for i in range(H):
    for j in range(W):
        a[i][j] =abs(a[i][j]-b[i][j])

dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(a[0][0])
for i in range(1,H):
    t = a[i][0]
    tmp = set()
    for k in dp[i-1][0]:
        tmp.add(k+t)
        tmp.add(abs(k-t))
    dp[i][0] = tmp
for j in range(1,W):
    t = a[0][j]
    tmp = set()
    for k in dp[0][j-1]:
        tmp.add(k+t)
        tmp.add(abs(k-t))
    dp[0][j] = tmp
for i in range(1,H):
    for j in range(1,W):
        t = a[i][j]
        tmp = set()
        for k in (dp[i-1][j] | dp[i][j-1]):
            tmp.add(k+t)
            tmp.add(abs(k-t))
        dp[i][j] = tmp
        dp[i-1][j-1] = set()

ls = list(dp[H-1][W-1])
print(min(ls))
### BUGGY CODE ###

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

cnt = 0

if N <= K:
  print(0)
else:
  for i in range(K):
    H.remove(max(H))

  cnt += sum(H)

  print(cnt)


### FIXED CODE ###

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

cnt = 0

if N <= K:
  print(0)
else:
  H.sort(reverse=True)
  H = H[K:]

  cnt += sum(H)

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

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def divisors(n):
    S,T=[],[]
    for i in range(1,int(n**.5)+1):
        if n%i==0:
            S.append(i)
            T.append(n//i)
    T.reverse()
    return S+T if S[-1]!=T[0] else S+T[1:]

def resolve():
    n,m=map(int,input().split())
    D=divisors(m)
    dp={d:0 for d in D}
    dp[1]=1
    for _ in range(n):
        ndp={d:0 for d in D}
        for d in D:
            for d1 in D:
                if(m%(d*d1)!=0): continue
                ndp[d*d1]+=dp[d]
                ndp[d*d1]%=MOD
        dp=ndp
    print(ndp[m])
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def modfact(n):
    fact=[1]*(n+1)
    invfact=[1]*(n+1)
    for i in range(1,n+1):
        fact[i]=i*fact[i-1]%MOD
    invfact[n]=pow(fact[n],MOD-2,MOD)
    for i in range(n-1,-1,-1):
        invfact[i]=invfact[i+1]*(i+1)%MOD
    return fact,invfact

def prime_factorization(n):
    assert(n>=2)
    factor=[]
    sqrt=int(n**.5)
    for d in range(2,sqrt+1):
        while(n%d==0):
            n//=d
            factor.append(d)
    if n!=1: factor.append(n)
    return factor

def resolve():
    from collections import Counter
    n,m=map(int,input().split())
    if(m==1):
        print(1)
        return
        
    P=prime_factorization(m)
    C=Counter(P)
    C=list(C.values())

    N=max(C)
    fact,invfact=modfact(N+n)

    ans=1
    for v in C:
        ans*=fact[v+n-1]*invfact[n-1]*invfact[v]
        ans%=MOD
    print(ans)
resolve()
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0]*(K+1) for i in range(N)]
for i, a in enumerate(A):
  if i == 0:
    for j in range(a+1):
      dp[0][j] = 1
  
  else:
    dp[i][0] = 1
    for j in range(1, K+1):
      dp[i][j] = dp[i][j-1] + dp[i-1][j]
      if j > a:
        dp[i][j] -= dp[i-1][j-a-1]

      dp[i][j] %= MOD

print(dp[N-1][K])

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0]*(K+1) for i in range(N)]
for i, a in enumerate(A):
  if i == 0:
    for j in range(a+1):
      dp[0][j] = 1
  
  else:
    dp[i][0] = 1
    for j in range(1, K+1):
      dp[i][j] = dp[i][j-1] + dp[i-1][j]
      if j > a:
        dp[i][j] -= dp[i-1][j-a-1]

      dp[i][j] %= MOD

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

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

left = [i+A[i] for i in range(n)]
right = [i-A[i] for i in range(n)]

ans = 0

for l in left:
    ans += right.count(l)

print(ans)

### FIXED CODE ###

from collections import Counter

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

left = [i+A[i] for i in range(n)]
right = [i-A[i] for i in range(n)]

r_counter = Counter(right)

ans = 0

for l in left:
    ans += r_counter[l]

print(ans)