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

import bisect

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


class BIT:
    def __init__(self, n):
        # 1-index
        self.n = n
        self.dat = [[0] * self.n for _ in range(2)]
        
    def _add_body(self, p, i, x):
        while i < self.n:
            self.dat[p][i] += x
            i += i & -i

    def add(self, a, b, x):
        # Add x to [a, b)
        self._add_body(0, a, x * -(a - 1))
        self._add_body(1, a, x)
        self._add_body(0, b, x * (b - 1))
        self._add_body(1, b, x * -1)

    def _query_body(self, p, i):
        res = 0
        while i > 0:
            res += self.dat[p][i]
            i -= i & -i
        return res
        
    def query(self, a, b):
        # Return sum of [a, b)
        res = (self._query_body(0, b - 1)
               + self._query_body(1, b - 1) * (b - 1)
               - self._query_body(0, a - 1)
               - self._query_body(1, a - 1) * (a - 1))
        return res

    def __repr__(self):
        return ", ".join([str(self.query(i, i + 1)) for i in range(self.n)])


X, H = zip(*sorted(XH))
bit = BIT(N + 10)

# 初期化
for i, h in enumerate(H):
    bit.add(i + 1, i + 2, h)
    
# 処理
res = 0
for i in range(N):
    cur = bit.query(i + 1, i + 2)
    if cur <= 0:
        continue

    need = -(-cur // A)
    idx = bisect.bisect_right(X, X[i] + 2 * D)
    bit.add(i + 1, idx + 1, -need * A)
    res += need
    
print(res)


### FIXED CODE ###

import bisect

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

XH.sort()
X, H = zip(*XH)

K = [-(-h // A) for h in H]
L = [0] * (N + 2)

ans = 0
for i in range(N):
    L[i + 1] += L[i]
    s = max(K[i] - L[i + 1], 0)
    ans += s
    L[i + 1] += s
    L[bisect.bisect_right(X, X[i] + 2 * D) + 1] -= s

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

from sys import stdin

X, Y, A, B, C = (int(i) for i in input().split())
p = [[int(x), "A"] for x in stdin.readline().rstrip().split()]
q = [[int(x), "B"]  for x in stdin.readline().rstrip().split()]
r = [[int(x), "C"] for x in stdin.readline().rstrip().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]
apples = p+q+r

apples.sort(reverse=True)
#print(apples)
ans = 0
pend = 0

while (X > 0 or Y > 0) and X+Y > pend:
    if apples[0][1] == "C":
        pend += 1
        ans += apples[0][0]
        apples.pop(0)
    elif apples[0][1] == "A":
        if X > 0:
            ans += apples[0][0]
            apples.pop(0)
            X -= 1
        else:
            apples.pop(0)
    elif apples[0][1] == "B":
        if Y>0:
            ans += apples[0][0]
            apples.pop(0)
            Y -= 1
        else:
            apples.pop(0)
    #print(ans)
    #print("XY", X, Y, pend)
#print("XY", X, Y, pend)
print(ans)



### FIXED CODE ###

import sys
input = sys.stdin.readline
X, Y, A, B, C = (int(i) for i in input().split())
p = [[int(x), "A"] for x in input().split()]
q = [[int(x), "B"] for x in input().split()]
r = [[int(x), "C"] for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]
apples = p+q+r


apples.sort(reverse=True)
#print(apples)
ans = 0
pend = 0


for hapi, col in apples:
    if col == "C":
        pend += 1
        ans += hapi
    elif col == "A":
        if X > 0:
            ans += hapi
            X -= 1

    elif col == "B":
        if Y>0:
            ans += hapi
            Y -= 1

    if (X < 1 and Y < 1) or X+Y == pend:
        break
    #print(ans)
    #print("XY", X, Y, pend)
#print("XY", X, Y, pend)
print(ans)
### BUGGY CODE ###

def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = {(i, j):0 for i in range(1, len(S)+1) for j in range(13)}
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[(1, i)] = 1
    else:
        DP_table[(1, int(digit))] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier = multiplier * 10 % 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    DP_table[(i + 1, (j * multiplier + k) % 13)] += DP_table[(i, k)]
        else:
            for k in range(13):
                DP_table[(i + 1, (int(digit) * multiplier + k) % 13)] += DP_table[(i, k)]
        
        for j in range(13):
            DP_table[(i + 1, j)] %= MOD

    print(DP_table[(len(S), 5)])

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = [[0 for i in range(13)] for j in range(len(S))]
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[0][i] = 1
    else:
        DP_table[0][int(digit)] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier = multiplier * 10 % 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    DP_table[i][(j * multiplier + k) % 13] += DP_table[i-1][k]
        else:
            digit = int(digit)
            for k in range(13):
                DP_table[i][(digit * multiplier + k) % 13] += DP_table[i-1][k]
        
        for j in range(13):
            DP_table[i][j] %= MOD

    print(DP_table[len(S)-1][5])

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

n, m = map(int, input().split())
for i in range(m//n, 0, -1):
    if (m-(m//i*i))%i == 0:
        break
print(i)

### FIXED CODE ###

import math
n, m = map(int, input().split())
if m%2 == 0:
    divisor = [1, 2, m//2, m]
else:
    divisor = [1, m]
for i in range(3, int(math.sqrt(m))+1):
    if m%i == 0:
        divisor.append(i)
        divisor.append(m//i)
divisor = sorted(divisor, reverse=True)
a = m//n
for i in divisor:
    if i > a:
        continue
    if (m-(m//i*i))%i == 0:
        break
print(i)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

K = I()
if K % 2 == 0:
    print(-1)
    exit()
if K % 7 == 0:
    K //= 7

a = 1
i = 1
while True:
    if a % K == 0:
        print(i)
        break
    else:
        a += pow(10,i,K)
        a %= K
        i += 1


### FIXED CODE ###

import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

K = I()
if K % 2 == 0 or K % 5 == 0:
    print(-1)
    exit()
if K % 7 == 0:
    K //= 7

A = [1]
for i in range(K+2):
    A.append((A[-1]*10) % K)

a = 1
i = 1
while True:
    if a % K == 0:
        print(i)
        break
    else:
        a += A[i]
        a %= K
        i += 1
### BUGGY CODE ###

h,n = map(int,input().split())
aa = [0]*n
bb = [0]*n
for i in range(n):
    a,b = map(int,input().split())
    aa[i] = a
    bb[i] = b
m = max(aa)

dp = [float("inf") for _ in range(h+m)]
dp[0] = 0
for i in range(1,h+m):
    for j in range(n):
        if i-aa[j] >= 0:
            dp[i] = min(dp[i-aa[j]]+bb[j],dp[i])

print(min(dp[h:]))


### FIXED CODE ###

h,n = map(int,input().split())
aa = [0]*n
bb = [0]*n
for i in range(n):
    a,b = map(int,input().split())
    aa[i] = a
    bb[i] = b
m = max(aa)

dp = [float("inf") for _ in range(h+m)]
dp[0] = 0
for i in range(1,h+m):
    for j in range(n):
        if i-aa[j] >= 0:
            dp[i] = min(dp[i-aa[j]]+bb[j],dp[i])

print(min(dp[h:]))
### BUGGY CODE ###

N = int(input())
S = input()

# 条件1だけを満たす組み合わせの数
ans = S.count('R') * S.count('G') * S.count('B')

# 条件2を満たさないものを、条件1でカウントしたものから減算
for l in range(N): # left
  for r in range(l+1, N): # right
    c = (r - l) // 2 + l # center
    if c - l == r - c: # 条件2を満たさない
      if len(set([S[l], S[c], S[r]])) == 3: # 条件1を満たす
        ans -= 1

print(ans)

### FIXED CODE ###

N = int(input())
S = input()

# 条件1だけを満たす組み合わせの数
ans = S.count('R') * S.count('G') * S.count('B')

# 条件2を満たさないものを、条件1でカウントしたものから減算
for l in range(N): # left
  for r in range(l+1, N): # right
    c = (r - l) // 2 + l # center
    if c - l == r - c: # 条件2を満たさない
      if len(set([S[l], S[c], S[r]])) == 3: # 条件1を満たす
        ans -= 1

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

n = int(input())
s = input()
c_list = [(0, 0, 0) for i in range(n)]
r = 0
g = 0
b = 0
n_list = [0]*n
p = -1
for i in range(n):
  if s[i] == "R":
    r += 1
    p = 0
  elif s[i] == "G":
    g += 1
    p = 1
  else:
    b += 1
    p = 2
  c_list[i] = (r, g, b)
  n_list[i] = p
count = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    c1 = n_list[i]
    c2 = n_list[j]
    if s[i] != s[j]:
      if j+j-i < n and s[j+j-i] != s[i] and s[j+j-i] != s[j]:
        count += c_list[n-1][3-c1-c2] - c_list[j][3-c1-c2] -1
      else:
        count += c_list[n-1][3-c1-c2] - c_list[j][3-c1-c2]
print(count)
        
  

### FIXED CODE ###

n = int(input())
s = input()
c_list = [(0, 0, 0) for i in range(n)]
r = 0
g = 0
b = 0
n_list = [0]*n
p = -1
for i in range(n):
  if s[i] == "R":
    r += 1
    p = 0
  elif s[i] == "G":
    g += 1
    p = 1
  else:
    b += 1
    p = 2
  c_list[i] = (r, g, b)
  n_list[i] = p
count = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    c1 = n_list[i]
    c2 = n_list[j]
    if c1 != c2:
      if j+j-i < n and 3 - n_list[j+j-i] - c1 - c2 == 0:
        count += c_list[n-1][3-c1-c2] - c_list[j][3-c1-c2] -1
      else:
        count += c_list[n-1][3-c1-c2] - c_list[j][3-c1-c2]
print(count)
### BUGGY CODE ###

S = list(input())
Q = int(input())
import time
# L = [input().split() for _ in range(Q)]

count = 0 # ['1']の数
for i in range(Q):
    L = input().split()
    if L[0] == '1':
        count += 1
    if L[0] == '2':
        if (count % 2) == 0:
            count = 0
            if L[1] == '1':
                S = [L[2]] + S
            else:
                S = S + [L[2]]
        else:
            if L[1] == '2':
                S = [L[2]] + S
            else:
                S = S + [L[2]]



# print(L)
if (count % 2) == 0:
    print(''.join(S))
else:
    S.reverse()
    print(''.join(S))

### FIXED CODE ###

s = input()
q = int(input())
query = []
lead = ''
end = ''
inversion_flg = False
 
for j in range(q):
    i = input().split()
    if i[0] == "1":
        if inversion_flg:
            inversion_flg = False 
        else:
            inversion_flg = True
    else:
        if inversion_flg:
            if i[1] == "1":
                i[1] = "2"
            else:
                i[1] = "1"
        if i[1] == "1":
            lead+=i[2]
        else:
            end+=i[2]
 
lead = lead[::-1]
s = lead+s+end
if inversion_flg:
    s = s[::-1]
print(s)
### BUGGY CODE ###

import bisect

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


for distance in range(100000000):
    a = bisect.bisect_left(x, -distance)
    b = bisect.bisect_right(x, distance)
    near_k = b- a
    if near_k == k:
        break
    elif near_k > k:
        if x[a]+1 in x:
            a += 1
            break
        elif x[b-1] - 1 in x:
            b -= 1
            break

if x[b-1] * x[a] < 0:
    semi_final_distance = max(x[b-1], x[a])+ (-2 * min(x[b-1], x[a]))
else:
    semi_final_distance = max(x[b-1], x[a])

a_2 = bisect.bisect_left(x, -semi_final_distance)
b_2 = bisect.bisect_right(x, semi_final_distance)
c = bisect.bisect_left(x, 0)
if b_2 - c > k:
    for distance in range(semi_final_distance):
        b_3 = bisect.bisect_right(x, distance)
        if b_3 - c == k:
            print(distance)
            exit()
elif c - a_2 > k:
    for distance in range(semi_final_distance):
        a_3 = bisect.bisect_left(x, -distance)
        if c - a_3 == k:
            print(distance)
            exit()
else:
    print(semi_final_distance)



### FIXED CODE ###

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


def cal_num(a, b):
    if x[a] * x[b] < 0:
        return min(abs(x[a]), abs(x[b])) * 2 + max(abs(x[a]), abs(x[b]))
    else:
        return max(abs(x[a]), abs(x[b]))

for i in range(n-k+1):
    c = cal_num(i, i+k-1)
    if num >= c:
        num = c

print(num)
### BUGGY CODE ###

from fractions import gcd
# from math import gcd

mod = 10**9 + 7

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

N = int(input())
A = [int(i) for i in input().split()]
num = 1
for n in A:
    num = lcm(num, n)
t = 0
for n in A:
    t =  (t + num//n) % mod
print(t)

### FIXED CODE ###

from fractions import gcd

def main():
    mod = 10**9 + 7

    N = int(input())
    A = input().split()
    AP = set(A)
    num = 1
    for n in AP:
        num = (num*int(n))//gcd(num,int(n))

    t = 0
    for n in A:
        t = (t + num//int(n))
    print(t%mod)


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

N,Q = map(int,input().split())
S = input()
lr = [[int(x) for x in input().split()] for i in range(Q)]

for i in range(Q):
  l = lr[i][0]
  r = lr[i][1]
  tmp = S[l-1:r]
  print(tmp.count('AC'))

### FIXED CODE ###

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

def subset_sum(s, a):
	return subset_rec(0, s, a)
	
def subset_rec(i, s, a):
	if s == 0:
		return True
	if i >= len(a):
		return False
	return subset_rec(i+1, s-a[i], a) or subset_rec(i+1, s, a)	

n = int(input())
a = list(map(int, input().split()))
p = int(input())
q = list(map(int, input().split()))
for i in range(p):
	if subset_sum(q[i], a):
		print('yes')
	else:
		print('no')



### FIXED CODE ###

def subset_sum(n, s, a):
	dp = [[0 for x in range(s+1)] for x in range(n+1)]
	dp[0][0]=1
	for i in range(n):
		v = a[i]
		for j in range(s+1):
			if v > j:
				dp[i+1][j] = dp[i][j]
			else:
				dp[i+1][j] = dp[i][j]+dp[i][j-v]
	return dp[n][s] > 0

n = int(input())
a = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))
for i in range(q):
	if subset_sum(n, m[i], a) == True:
		print('yes')
	else:
		print('no')
### BUGGY CODE ###

import heapq

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

count = 0
candidates = []
heapq.heappush(candidates, (-(A[0] + B[0] + C[0]), 0, 0, 0))
used = set()
while True:
    s, i, j, k = heapq.heappop(candidates)
    s *= -1
    if not (i, j, k) in used:
        print(s)
        count += 1
        if count >= K:
            break
    used.add((i, j, k))
    if i < X - 1:
        heapq.heappush(candidates, (-(A[i+1] + B[j] + C[k]), i+1, j, k))
    if j < Y - 1:
        heapq.heappush(candidates, (-(A[i] + B[j+1] + C[k]), i, j+1, k))
    if k < Z - 1:
        heapq.heappush(candidates, (-(A[i] + B[j] + C[k+1]), i, j, k+1))


### FIXED CODE ###

import heapq

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

candidates = []
heapq.heappush(candidates, (-(A[0] + B[0] + C[0]), 0, 0, 0))
used = {(0, 0, 0)}
for _ in range(K):
    s, i, j, k = heapq.heappop(candidates)
    print(-s)
    if i < X - 1 and (i+1, j, k) not in used:
        heapq.heappush(candidates, (-(A[i+1] + B[j] + C[k]), i+1, j, k))
        used.add((i+1, j, k))
    if j < Y - 1 and (i, j+1, k) not in used:
        heapq.heappush(candidates, (-(A[i] + B[j+1] + C[k]), i, j+1, k))
        used.add((i, j+1, k))
    if k < Z - 1 and (i, j, k+1) not in used:
        heapq.heappush(candidates, (-(A[i] + B[j] + C[k+1]), i, j, k+1))
        used.add((i, j, k+1))
### BUGGY CODE ###

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


b = []
for i in range(n):
    if i%2 == 0: b.insert( 0, a[i] )
    else:        b.append( a[i] )

if n%2 == 0: b.reverse()
print( ' '.join( map(str,b)) )

### FIXED CODE ###

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


if n%2 == 0:
    for i in range(n-1,-1,-2): print( a[i], end=' ' )
    for i in range(  0, n, 2): print( a[i], end=' ' )
else:
    for i in range(n-1,-1,-2): print( a[i], end=' ' )
    for i in range( 1 , n, 2): print( a[i], end=' ' )
### BUGGY CODE ###

N,K=map(int,input().split())
H=list(map(int,input().split()))
H.sort(reverse=True)
for i in range(K):
    if len(H)==0:
        break
    H.pop(0)
print(sum(H))

### FIXED CODE ###

N,K=map(int,input().split())
H=list(map(int,input().split()))
H.sort(reverse=True)
print(sum(H[K:]))
### BUGGY CODE ###

input()
nums = list(map(int,input().split()))

if nums.count(0):
    print(0)
    exit(0)

result=1
for i in nums:
    result *= i

if result > (10**18):
    print(-1)
else:
    print(result)

### FIXED CODE ###

input()
nums = list(map(int,input().split()))

if nums.count(0):
    print(0)
    exit(0)

result=1
for i in nums:
    result *= i
    if result > (10**18):
        print(-1)
        exit(0)
print(result)
### BUGGY CODE ###

from collections import defaultdict

N = int(input())
d = defaultdict(int)
A = list(map(int, input().split()))
for a in A:
    d[a] += 1
Q = int(input())
for _ in range(Q):
    B, C = map(int, input().split())
    d[C] += d[B]
    del d[B]
    ans = 0
    for k, v in d.items():
        ans += k * v
    print(ans)

### FIXED CODE ###

from collections import defaultdict

N = int(input())
d = defaultdict(int)
A = list(map(int, input().split()))
for a in A:
    d[a] += 1
Q = int(input())
ans = 0
for k, v in d.items():
    ans += k * v
for _ in range(Q):
    B, C = map(int, input().split())
    d[C] += d[B]
    ans -= B * d[B]
    ans += C * d[B]
    del d[B]
    print(ans)
### BUGGY CODE ###

n = int(input())
cnt = 0

def divisor(n):
    i = 1
    res = set()
    while i * i <= n:
        if n % i == 0:
            res.add(i)
            res.add(n // i)
        i += 1
    return res


for c in range(1,n+1):
    k = n - c
    #print(k)
    if k >= 0:
        #print(divisor(k))
        l = len(divisor(k))
        cnt +=l

print(cnt)

### FIXED CODE ###

n = int(input())

cnt = 0
for a in range(1,n+1):
    if n%a != 0:
        cnt +=n//a
    else:
        cnt +=n//a-1
    #print(a,n//a,cnt)
print(cnt)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(4100000)
from collections import deque

def main():
    H, W = map(int, input().split())
    S = list(input() for _ in range(H))
    visited = [[float('inf')] * W for _ in range(H)]
    dh = [0,1]
    dw = [1,0]
    if S[0][0] == '#':
        visited[0][0] = 1
        pre = False
    else:
        visited[0][0] = 0
        pre = True
    
    Q = deque([])
    Q.append((0,0,pre))
    while Q:
        h, w, pre = Q.popleft()
        
        if h == H - 1 and w == W - 1:
            break

        for i in range(2):
            nh = h + dh[i]
            nw = w + dw[i]

            if 0 <= nh < H and 0 <= nw < W:
                if S[nh][nw] == '.':
                    visited[nh][nw] = min(visited[nh][nw], visited[h][w])
                    Q.append((nh,nw,True))
                else:
                    if pre:
                        visited[nh][nw] = min(visited[nh][nw], visited[h][w] + 1)
                        Q.append((nh,nw,False))
                    else:
                        visited[nh][nw] = min(visited[nh][nw], visited[h][w])
                        Q.append((nh,nw,False))

    print(visited[H-1][W-1])
        



if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(4100000)
from collections import deque

def main():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    visited = [[float('inf')] * W for _ in range(H)]
    if S[0][0] == '#':
        visited[0][0] = 1
    else:
        visited[0][0] = 0
    
    for h in range(H):
        for w in range(W):
            if h + 1 > H - 1 and w + 1 > W - 1:
                continue
            if S[h][w] == '.':
                if h + 1 > H - 1:
                    if S[h][w + 1] == '.':
                        visited[h][w+1] = min(visited[h][w], visited[h][w+1])
                    else:
                        visited[h][w+1] = min(visited[h][w] + 1,visited[h][w+1])
                elif w + 1 > W - 1:
                    if S[h+1][w] == '.':
                        visited[h+1][w] = min(visited[h][w],visited[h+1][w])
                    else:
                        visited[h+1][w] = min(visited[h][w] + 1,visited[h+1][w])
                else:
                    if S[h + 1][w] == '.':
                        visited[h+1][w] = min(visited[h][w],visited[h+1][w])
                    else:
                        visited[h+1][w] = min(visited[h][w] + 1,visited[h+1][w])

                    if S[h][w + 1] == '.':
                        visited[h][w+1] = min(visited[h][w],visited[h][w+1])
                    else:
                        visited[h][w+1] = min(visited[h][w] + 1,visited[h][w+1])

            else:
                if h + 1 > H - 1:
                    visited[h][w+1] = min(visited[h][w],visited[h][w+1])
                elif w + 1 > W - 1:
                    visited[h+1][w] = min(visited[h][w],visited[h+1][w])
                else:
                    visited[h][w+1] = min(visited[h][w],visited[h][w+1])
                    visited[h+1][w] = min(visited[h][w],visited[h+1][w])

    print(visited[H-1][W-1])


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

S = input()
N = len(S)

dp = [[0]*2019 for _ in [0]*(N+1)]
for i,s in enumerate(S,1):
    s = int(s)
    dp[i][s] += 1
    for j in range(2019):
        dp[i][(j*10+s)%2019] += dp[i-1][j]

ans = sum(dp[i][0] for i in range(N+1))
print(ans)

### FIXED CODE ###

S = input()
N = len(S)

dp = [[0]*2019 for _ in [0]*2]
ans = 0
for i,s in enumerate(S,1):
    s = int(s)
    i %= 2
    dpi = [0]*2019
    dpi1 = dp[1-i]
    dpi[s] += 1
    for j in range(2019):
        dpi[(j*10+s)%2019] += dpi1[j]
    dp[i] = dpi
    ans += dpi[0]

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

import sys
import collections
import itertools
import math
import re
from collections import Counter
from collections import deque
from collections import defaultdict

MOD = 10 ** 9 + 7

N,K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

C = []

s = 0
ma = 0
for i in range(0,N-1):
    for j in range(i, N):
        if j==i:
            C.append(A[i])
        else:
            C.append(C[-1] + A[j])
    ma = max(ma, max(C))

IDX = 0
while ((1 << IDX) < ma):
    IDX += 1


def filterList(list, i):
    retList = []
    cnt = 0
    for l in list:
        if l & (1 << i):
            cnt += 1
            retList.append(l)

    if cnt >= K:
        return retList
    else:
        return list



# 31..0
D = C
for i in range(IDX,-1,-1):
    D = filterList(D,i)


EE = list(itertools.combinations(D, K))

ret = 0
for E in EE:
    r = E[0]
    for e in E:
        r = r & e
    ret = max(ret, r)


print(ret)

sys.exit(0)


### FIXED CODE ###

import sys

N,K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

C = []

for i in range(0,N-1):
    for j in range(i, N):
        if j==i:
            C.append(A[i])
        else:
            C.append(C[-1] + A[j])

D = C
ans = 0
for i in range(40,-1,-1):
    yes = []
    no = []
    for l in D:
        if l & (1 << i):
            yes.append(l)
        else:
            no.append(l)

    if len(yes) >= K:
        ans += 1 << i
        D = yes

print(ans)

sys.exit(0)