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

import sys
readline = sys.stdin.buffer.readline

H, W = list(map(int, readline().split()))
CH, CW = list(map(int, readline().split()))
DH, DW = list(map(int, readline().split()))
S = []
for _ in range(H):
    S.append(list(input()))

# 1-index -> 0-index
CH -= 1
CW -= 1
DH -= 1
DW -= 1

from collections import deque
seen = set()
queue = deque([(0, CH, CW)])
offsets = [(-1, 0), (1, 0), (0, -1), (0, 1)]

while queue:
    move, row, col = queue.popleft()

    # print(row, col, queue)

    if (row, col) in seen:
        continue

    if row == DH and col == DW:
        print(move)
        sys.exit(0)

    seen.add((row, col))

    for r_offset, c_offset in offsets:
        new_row = row + r_offset
        new_col = col + c_offset
        if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
            queue.appendleft((move, new_row, new_col))


    for i in range(-2, 3):
        for j in range(-2, 3):
            new_row = row + i
            new_col = col + j

            if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
                queue.append((move+1, new_row, new_col))

print(-1)

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline

H, W = list(map(int, readline().split()))
CH, CW = list(map(int, readline().split()))
DH, DW = list(map(int, readline().split()))
S = []
for _ in range(H):
    S.append(list(input()))

# 1-index -> 0-index
CH -= 1
CW -= 1
DH -= 1
DW -= 1

from collections import deque
seen = set()
queue = deque([(0, CH, CW)])
offsets = [(-1, 0), (1, 0), (0, -1), (0, 1)]

while queue:
    move, row, col = queue.popleft()

    # print(row, col, queue)

    if (row, col) in seen:
        continue

    if row == DH and col == DW:
        print(move)
        sys.exit(0)

    seen.add((row, col))

    for r_offset, c_offset in offsets:
        new_row = row + r_offset
        new_col = col + c_offset
        if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
            queue.appendleft((move, new_row, new_col))


    for i in range(-2, 3):
        for j in range(-2, 3):
            new_row = row + i
            new_col = col + j

            if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
                queue.append((move+1, new_row, new_col))

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

R, G, B, N = map(int, input().split())
ans = 0
for r in range(N//R+1):
    for g in range((N-r*R)//G+1):
        if N-r*R-g*G < 0:
            break
        if N-r*R-g*G >= 0 and (N-r*R-g*G) % B == 0:
            ans += 1
print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for r in range(N//R+1):
    for g in range((N-r*R)//G+1):
        if (N-r*R-g*G) % B == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

import sys
x,y=map(int,input().split())
if (x+y)%3!=0:
  print(0)
  sys.exit()
n=(x+y)//3
fac=[1 for i in range(n+1)]#fac[i]=i!. fac[0]=1
for i in range(1,n+1):
  fac[i]=fac[i-1]*i

print(fac[n]//fac[x-n]//fac[y-n])

### FIXED CODE ###

import sys
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

x,y=map(int,input().split())
if (x+y)%3!=0:
  print(0)
  sys.exit()
n=(x+y)//3

mod = 10**9+7 #出力の制限
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 )

print(cmb(n,x-n,mod))
### BUGGY CODE ###

n = int(input())
x = list(map(int,input().split()))
y = x.copy()
y.sort()
t1 = y[n//2-1]
t2 = y[n//2]
for i in x:
    t = y.index(i)
    if t<n//2:
        print(t2)
    else:
        print(t1)

### FIXED CODE ###

n = int(input())
x = list(map(int,input().split()))
y = x.copy()
y.sort()
z = set(x)
t1 = y[n//2-1]
t2 = y[n//2]
idx = dict([])
idx[y[0]] = 0
l = y[0]
cnt = 0
for i in y:
    if i == l:
        cnt += 1
        continue
    else:
        idx[i] = cnt
        l = i
        cnt += 1

for i in x:
    t = idx[i]
    if t<n//2:
        print(t2)
    else:
        print(t1)
### BUGGY CODE ###

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

mod = 10**9 + 7

# x ** a をmodで割った余りを、O(log(a))時間で求める。
def power(x, a):
    if a == 0:
        return 1
    elif a == 1:
        return x
    elif a % 2 == 0:
        return power(x, a//2) **2 % mod
    else:
        return power(x, a//2) **2 * x % mod

# xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
# https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
def modinv(x):
    return power(x, mod-2)

# 二項係数の左側の数字の最大値を max_len　とする。nとかだと他の変数と被りそうなので。
# factori_table = [1, 1, 2, 6, 24, 120, ...] 要は factori_table[n] = n!
# 計算時間はO(max_len * log(mod))

max_len = 2 * n - 1 #適宜変更する

factori_table = [1] * (max_len + 1)
factori_inv_table = [1] * (max_len + 1)
for i in range(1, max_len + 1):
    factori_table[i] = factori_table[i-1] * (i) % mod
    factori_inv_table[i] = modinv(factori_table[i])

def binomial_coefficients(n, k):
    # n! / (k! * (n-k)! )
    if k <= 0 or k >= n:
        return 1
    return (factori_table[n] * factori_inv_table[k] * factori_inv_table[n-k]) % mod

if k >= n-1:
    # nHn = 2n-1 C n
    print(binomial_coefficients(2 * n - 1, n))
else:
    # 移動がk回←→ 人数0の部屋がk個以下
    # 人数0の部屋がちょうどj個のものは
    # nCj(人数0の部屋の選び方) * jH(n-j) (余剰のj人を残りの部屋に入れる)
    ans = 0
    for j in range(k+1):
        if j == 0:
            ans += 1
        else:
            ans += binomial_coefficients(n, j) * binomial_coefficients(n-1, j) 
            ans %= mod
    print(ans)


### FIXED CODE ###

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

mod = 10**9 + 7

# xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
def modinv(x):
    return pow(x, mod-2, mod)

# 二項係数の左側の数字の最大値を max_len　とする。nとかだと他の変数と被りそうなので。
# factori_table = [1, 1, 2, 6, 24, 120, ...] 要は factori_table[n] = n!
# 計算時間はO(max_len * log(mod))

max_len = 2 * n - 1 #適宜変更する

factori_table = [1] * (max_len + 1)
factori_inv_table = [1] * (max_len + 1)
for i in range(1, max_len + 1):
    factori_table[i] = factori_table[i-1] * (i) % mod
    factori_inv_table[i] = modinv(factori_table[i])

def binomial_coefficients(n, k):
    # n! / (k! * (n-k)! )
    if k <= 0 or k >= n:
        return 1
    return (factori_table[n] * factori_inv_table[k] * factori_inv_table[n-k]) % mod

if k >= n-1:
    # nHn = 2n-1 C n
    print(binomial_coefficients(2 * n - 1, n))
else:
    # 移動がk回←→ 人数0の部屋がk個以下
    # 人数0の部屋がちょうどj個のものは
    # nCj(人数0の部屋の選び方) * jH(n-j) (余剰のj人を残りの部屋に入れる)
    ans = 0
    for j in range(k+1):
        if j == 0:
            ans += 1
        else:
            ans += binomial_coefficients(n, j) * binomial_coefficients(n-1, j) 
            ans %= mod
    print(ans)
### BUGGY CODE ###

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

from operator import itemgetter
AB.sort(key = itemgetter(1),reverse = True)
AB.sort(key = itemgetter(0),reverse = True)


memo = {}
import sys
sys.setrecursionlimit(10**6 + 1)
def dp(i,j):
        if (i,j) in memo:
                return memo[(i,j)]
        elif i == M or j == N:
                return 0
        a,b = AB[j]
        if i <= M - a:
                memo[(i,j)] =  max(dp(i+1,j+1) + b, dp(i,j+1))
                return memo[(i,j)]
        memo[(i,j)] =  dp(i,j+1)
        return memo[(i,j)]
print(dp(0,0))

### FIXED CODE ###

import heapq
from operator import itemgetter

def main():
    N, M = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    AB.sort(key = itemgetter(0))
    heap = []
    ans = 0
    cnt = 0
    for i in range(1,M + 1):
        while cnt < N and AB[cnt][0] <= i:
            heapq.heappush(heap,-1*AB[cnt][1])
            cnt += 1
        if len(heap) > 0:
            ans += heapq.heappop(heap)*-1
    print(ans)
    return

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

from collections import deque

S = input()
Q = int(input())

reverse = 1 #reverse == 1 -> 正常, reverse == -1 -> 逆から

d = deque(S)

for i in range(Q):
    Query_tmp = list(map(str, input().split()))
    
    if Query_tmp[0] == "1":
        reverse *= -1
        # S = S[::-1]
    else:
        Ci = Query_tmp[2]

        if Query_tmp[1] == "1":
            if reverse == 1:
                d.appendleft(Ci)
            else:
                rev_Ci = Ci[::-1]
                d.append(rev_Ci)
        else:
            if reverse == 1:
                d.append(Ci)
            else:
                rev_Ci = Ci[::-1]
                d.appendleft(rev_Ci)
    
    # if reverse == 1:
    #     print(S)
    # else:
    #     print(S[::-1])

length = len(d)
for i in range(length):
    if reverse == -1:
        i = length - i - 1
    print(d[i], end="")
print()


### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())

reverse = 1 #reverse == 1 -> 正常, reverse == -1 -> 逆から

d = deque(S)

for i in range(Q):
    Query_tmp = list(map(str, input().split()))
    
    if Query_tmp[0] == "1":
        reverse *= -1
        # S = S[::-1]
    else:
        Ci = Query_tmp[2]

        if Query_tmp[1] == "1":
            if reverse == 1:
                d.appendleft(Ci)
            else:
                rev_Ci = Ci[::-1]
                d.append(rev_Ci)
        else:
            if reverse == 1:
                d.append(Ci)
            else:
                rev_Ci = Ci[::-1]
                d.appendleft(rev_Ci)
    
    # if reverse == 1:
    #     print(S)
    # else:
    #     print(S[::-1])

if reverse == -1:
    d.reverse()

print("".join(d))
### BUGGY CODE ###

n = int(input())

s = input()
r=[]
g=[]
b=[]
for i in range(n):
  #print(s[i])
  if s[i] == 'R':
    r.append(i)
  elif s[i] == 'G':
    g.append(i)
  else:
    b.append(i)

#print(r)
#print(g)
#print(b)
sum = 0
for i in r:
  for j in g:
    for k in b:
      wk = [i,j,k]
      wk.sort()
      mm = i + j + k
      if wk[1]*3 != mm :
        sum += 1
print(sum)

### FIXED CODE ###

from collections import defaultdict
d = defaultdict(int)

n = int(input())
s = input()
r=[]
g=[]
b=[]
for i in range(n):
  #print(s[i])
  if s[i] == 'R':
    r.append(i)
  elif s[i] == 'G':
    g.append(i)
  else:
    #b.append(i)
    d[i] = 1

#print(r)
#print(g)
#print(b)
sum = len(r)*len(g)*len(d)
for i in r:
  for j in g:
    ma = max(i,j)
    mi = min(i,j)
    df = ma - mi
    k1 = mi - df
    k2 = ma + df
    k3 = (ma + mi) / 2
    sum -= d[k1]
    sum -= d[k2]
    sum -= d[k3]
print(sum)
### BUGGY CODE ###

n,bod = map(int,input().split())
points = []
x = []
y = []
for i in range(n):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)
    points.append([a,b])

x.sort()
y.sort()


ans = 1e20

for i in range(n):
    for j in range(1,n-i):
        for k in range(n):
            for l in range(1,n-k):
                lef = x[i]
                rig = x[-j]
                bot = y[k]
                top = y[-l]

                cnt = 0
                for m in range(n):
                    if lef <= points[m][0] <= rig and bot <= points[m][1] <= top:
                        cnt += 1
                if cnt >= bod:
                    area = (rig-lef)*(top-bot)
                    if area < ans:
                        ans = area


print(ans)

### FIXED CODE ###

n,bod = map(int,input().split())
points = []
x = []
y = []
for i in range(n):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)
    points.append([a,b])

x.sort()
y.sort()


ans = 1e20

for i in range(n):
    for j in range(1,n-i):
        for k in range(n):
            for l in range(1,n-k):
                lef = x[i]
                rig = x[-j]
                bot = y[k]
                top = y[-l]

                cnt = 0
                for m in range(n):
                    if lef <= points[m][0] <= rig and bot <= points[m][1] <= top:
                        cnt += 1
                if cnt >= bod:
                    area = (rig-lef)*(top-bot)
                    if area < ans:
                        ans = area


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

# 伝搬対象の区間を求める
def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None

# 区間[l, r)をxで更新
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = data[R-1] = x
        if L & 1:
            lazy[L-1] = data[L-1] = x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])

# 区間[l, r)内の最小値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s


from bisect import bisect_left
from sys import stdin

if __name__ == '__main__':
    n, q = map(int, input().split())
    stx = [list(map(int, input().split())) for _ in range(n)]
    l = [int(input()) for _ in range(q)]

    INF = 2**31-1
    N = len(l)
    LV = (N-1).bit_length()
    N0 = 2**LV
    data = [INF]*(2*N0)
    lazy = [None]*(2*N0)

    stx.sort(key=lambda x:x[2], reverse=True)
    for s, t, x in stx:
        i1 = bisect_left(l, s - 0.5 - x)
        i2 = bisect_left(l, t - 0.5 - x)
        update(i1, i2, x)

    for i in range(q):
        tmp = query(i, i+1)
        if tmp == INF:
            print(-1)
        else:
            print(tmp)


### FIXED CODE ###

def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] = v

        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1
# a_iの現在の値を取得
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
# これを呼び出す
def query(k):
    return _query(k)[1]

from bisect import bisect_left
from sys import stdin

if __name__ == '__main__':
    n, q = map(int, stdin.readline().rstrip().split())
    stx = [list(map(int, stdin.readline().rstrip().split())) for _ in range(n)]
    l = [int(stdin.readline().rstrip()) for _ in range(q)]

    INF = (-1, 2**31-1)
    N = len(l)
    N0 = 2**(N-1).bit_length()
    data = [None]*(2*N0)

    stx.sort(key=lambda x:x[2], reverse=True)
    for i, (s, t, x) in enumerate(stx):
        i1 = bisect_left(l, s - 0.5 - x)
        i2 = bisect_left(l, t - 0.5 - x)
        update(i1, i2, (i, x))

    for i in range(q):
        tmp = query(i)
        if tmp == INF[1]:
            print(-1)
        else:
            print(tmp)
### BUGGY CODE ###

N, Q = map(int, input().split())
vws = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(Q)]

anss = []
for v, w in vws:
    while v != w:
        if v > w:
            v = (v-1)//N
        else:
            w = (w-1)//N
    anss.append(v + 1)

print('\n'.join(map(str, anss)))


### FIXED CODE ###

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

anss = []
if N == 1:
    anss = [min(v, w) for v, w in vws]
else:
    for v, w in vws:
        v, w = v-1, w-1
        while v != w:
            if v > w:
                v = (v-1)//N
            else:
                w = (w-1)//N
        anss.append(v + 1)

print('\n'.join(map(str, anss)))
### BUGGY CODE ###

from itertools import accumulate

N, K, *A = map(int, open(0).read().split())

for _ in range(min(K, 41)):
    B = [0] * (N + 1)
    for x, d in enumerate(A):
        B[max(0, x - d)] += 1
        B[min(N, x + d + 1)] -= 1
    A = list(accumulate(B))

print(*A[:-1])

### FIXED CODE ###

from itertools import accumulate

N, K, *A = map(int, open(0).read().split())

for _ in range(min(K, 41)):
    B = [0] * (N + 1)
    for x, d in enumerate(A):
        B[max(0, x - d)] += 1
        B[min(N, x + d + 1)] -= 1
    A = list(accumulate(B))

print(*A[:-1])
### BUGGY CODE ###

n = int(input())

tkhs = 1
aoki = 1

for _ in range(n):
    t, a = map(int, input().split())
    k = 1
    while not(tkhs <= k*t and aoki <= k*a):
        k += 1
    tkhs = k*t
    aoki = k*a

print(tkhs+aoki)


### FIXED CODE ###

n = int(input())
from math import ceil

tkhs = 1
aoki = 1

for _ in range(n):
    t, a = map(int, input().split())
    k = max((tkhs+t-1)//t, (aoki+a-1)//a)
    tkhs = k*t
    aoki = k*a

print(tkhs+aoki)
### BUGGY CODE ###

import sys
import copy
stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


H, W = na()
A_array = naa(H)
B_array = naa(H)
C_array = [[abs(aa-bb) for aa, bb in zip(a, b)]
           for a, b in zip(A_array, B_array)]
# print(C_array)

ans_array = [set() for _ in range(W)]

ans_array[0].add(0)

for i in range(H):
    for j in range(W):
        for s in copy.deepcopy(ans_array[j]):
            ans_array[j].remove(s)
            ans_array[j].add(abs(s + C_array[i][j]))
            ans_array[j].add(abs(s - C_array[i][j]))
        # print(ans_array[j])
        if j != 0:
            for s in ans_array[j-1]:
                ans_array[j].add(abs(s + C_array[i][j]))
                ans_array[j].add(abs(s - C_array[i][j]))
#     print(ans_array)
# print(ans_array)

ans = 10 ** 9
for s in ans_array[W-1]:
    if abs(s) < ans:
        ans = abs(s)
print(ans)


### FIXED CODE ###

import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


H, W = na()
A_array = naa(H)
B_array = naa(H)
C_array = [[abs(aa-bb) for aa, bb in zip(a, b)]
           for a, b in zip(A_array, B_array)]
# print(C_array)

K = 6400

ans_array = [[[0] * (K+1) for _ in range(W)] for _ in range(H)]

ans_array[0][0][C_array[0][0]] = 1

for i in range(H):
    for j in range(W):
        if i != 0:
            for k in range(K+1):
                ans_array[i][j][k] = ans_array[i][j][k] | ((ans_array[i-1][j][abs(k+C_array[i][j])] if abs(
                    k+C_array[i][j]) <= K else 0) | ans_array[i-1][j][abs(k-C_array[i][j])])
        if j != 0:
            for k in range(K+1):
                ans_array[i][j][k] = ans_array[i][j][k] | ((ans_array[i][j-1][abs(k+C_array[i][j])] if abs(
                    k+C_array[i][j]) <= K else 0) | ans_array[i][j-1][abs(k-C_array[i][j])])

# print(ans_array)

for k in range(K+1):
    if ans_array[H-1][W-1][k] == 1:
        print(k)
        exit()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

MOD = 10 ** 9 + 7
def dfs(v, pv):
    dp[v][0] = dp[v][1] = 1
    for nv in edge[v]:
        if nv == pv: continue
        dfs(nv, v)
        dp[v][0] *= dp[nv][0] + dp[nv][1]
        dp[v][0] %= MOD
        dp[v][1] *= dp[nv][0]
        dp[v][1] %= MOD

N = int(input())
edge = [[] for _ in range(N)]

for i in range(N-1):
    x, y = map(lambda x:int(x)-1, input().split())
    edge[x].append(y)
    edge[y].append(x)

dp = [[0] * 2 for _ in range(10**5+10)]
dfs(0,-1)

print((dp[0][1] + dp[0][0]) % MOD)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

MOD = 10 ** 9 + 7
def dfs(v, pv):
    white, black = 1, 1
    for nv in edge[v]:
        if nv == pv: continue
        rw, rb = dfs(nv, v)
        white *= rw + rb
        white %= MOD
        black *= rw
        black %= MOD
    return white, black

N = int(input())
edge = [[] for _ in range(N)]

for i in range(N-1):
    x, y = map(lambda x:int(x)-1, input().split())
    edge[x].append(y)
    edge[y].append(x)

print(sum(dfs(0, -1)) % MOD)
### BUGGY CODE ###

N , W = map(int , input().split())
weight = []
value = []
for _ in range(N):
    w , v = map(int , input().split())
    weight.append(w)
    value.append(v)

def knapsack():
    dp = [[-1] * (W + 1) for _ in range(N + 1)]
    def solve(i,w):
        if dp[i][w] != -1:
            return dp[i][w]
        if N == i:
            ret_val = 0
        elif w - weight[i] < 0:
            ret_val = solve(i + 1,w)
        else:
            ret_val = max(solve(i + 1, w), solve(i + 1,w - weight[i]) + value[i])
        dp[i][w] = ret_val
        return dp[i][w]
    solve(0,W)
    #print(dp)
    return max(dp[0])

if __name__ == "__main__":
    print(knapsack())
    

### FIXED CODE ###

import numpy as np
N , W = map(int, input().split())
goods = np.array([list(map(int , input().split())) for _ in range(N)])
dp = np.zeros((N + 1 , W + 1) , dtype = np.int)

for i in range(0,N):
    w, v = goods[i,:]
    dp[i + 1, w:] = np.maximum(dp[i,w:] , dp[i,:-w] + v)
    dp[i + 1, :] = np.maximum(dp[i + 1,:],dp[i,:])
print(int(dp[N,W]))
### BUGGY CODE ###

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

t = min(a)

dp = [0] * (k+1)

for x in a:
    dp[x] = 1

for i in range(k+1):
    for x in a:
        if i >= x:
            if dp[i] + (dp[i-x] + 1) % 2 > 0:
                dp[i] = 1
            else:
                dp[i] = 0

print("First" if dp[i] == 1 else "Second")

### FIXED CODE ###

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

t = min(a)

dp = [0] * (k+1)

for x in a:
    dp[x] = 1

for i in range(k+1):
    for x in a:
        if i >= x:
            if dp[i] + (dp[i-x] + 1) % 2 > 0:
                dp[i] = 1
            else:
                dp[i] = 0

print("First" if dp[i] == 1 else "Second")
### BUGGY CODE ###

import itertools
import math
import numpy as np
z = []
N = int(input())
for i in range(N):
  z.append(list(map(int,input().split(' '))))
d = 0  
x = []
p = list(itertools.permutations(z, N))
#print(p,N)  
for i in p:
  #print(i)
  #ans = math.sqrt((i[0][0]-i[1][0])**2) + math.sqrt((i[0][1]-i[1][1])**2)
  for j in range(N-1):
    #print(j,i)
    d += np.linalg.norm(np.array([i[j+1][0],i[j+1][1]]) - np.array([i[j][0],i[j][1]]))
    #print(([i[j+1][0],i[j+1][1]]), ([i[j][0],i[j][1]]))
  x.append(d) 
  d = 0
  
  
#  print(ans)
  
#print(x)  
print(sum(x)/len(x))  

### FIXED CODE ###

import itertools
import math
import numpy as np
z = []
N = int(input())
for i in range(N):
  z.append(list(map(int,input().split(' '))))
d = 0  
x = []
p = list(itertools.permutations(z, N))
#print(p,N)  
for i in p:
  #print(i)
  #ans = math.sqrt((i[0][0]-i[1][0])**2) + math.sqrt((i[0][1]-i[1][1])**2)
  for j in range(N-1):
    #print(j,i)
    #d += np.linalg.norm(np.array([i[j+1][0],i[j+1][1]]) - np.array([i[j][0],i[j][1]]))
    d += math.sqrt(((i[j][0]-i[j+1][0])**2) + ((i[j][1]-i[j+1][1])**2))
    #print(([i[j+1][0],i[j+1][1]]), ([i[j][0],i[j][1]]))
  x.append(d) 
  d = 0
  
  
#  print(ans)
  
#print(x)  
print(sum(x)/len(x))
### BUGGY CODE ###

s = input()
d = {}
x = 0
for i in range(len(s)):
  x += int(s[-i-1])*10**i
  r = x%2019
  #r = int(s[i:])%2019
  if r in d:
    d[r] += 1
  else:
    d[r] = 1
ans = 0
if 0 in d:
  ans += d[0]
for k,v in d.items():
  if v >= 2:
    ans += v*(v-1)//2
print(ans)



### FIXED CODE ###

s = list(map(int,input()))
d = [0 for _ in range(2019)]
r = 0
x = 1
for si in reversed(s):
  r += si*x
  r %= 2019
  d[r] += 1
  x *= 10
  x %= 2019
ans = d[0]
for v in d:
  if v >= 2:
    ans += v*(v-1)//2
print(ans)