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

import copy
N = int(input())
X = list(map(int,input().split()))
length = len(X)


for i in range(N):
    x = copy.copy(X) 
    x.pop(i)
    x.sort()
    print(x[int(length/2)-1])
    # print(x,X)

### FIXED CODE ###

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

sortx = sorted(X)
bef = sortx[N//2-1]
aft = sortx[N//2]
for i in X:
        print(aft if i <= bef else bef)
### BUGGY CODE ###

q = int(input())
d = [[0 for _ in range(1001)] for _ in range(1001)]
for i in range(q):
    x = input()
    y = input()
    n = len(x)
    m = len(y)
    for i in range(1001):
        d[i][0]=0
        d[0][i]=0
    for i in range(n):
        for j in range(m):
            if x[i] == y[j]:
                d[i+1][j+1] = d[i][j]+1
            else:
                d[i+1][j+1] = max(d[i+1][j],d[i][j+1])
    print(d[n][m])


### FIXED CODE ###

def calc(x,y):
    n = len(x)
    m = len(y)
    dp1 = [0]*(m+1)
    for i in range(n):
        s = x[i]
        dp2 = dp1[:]
        for j in range(m):
            if s == y[j]:
                dp1[j+1] = dp2[j]+1
            elif dp1[j+1] < dp1[j]:
                dp1[j+1] = dp1[j]
    return dp1[-1]

q = int(input())
for i in range(q):
    x = input()
    y = input()
    print(calc(x,y))
### BUGGY CODE ###

def main():
    h, w, K = map(int, input().split())
    grid = [list(input()) for _ in [0]*h]
    m = 10**9
    for i in range(2**(h-1)):
        i = (("0"*h)+bin(i)[2:])[-h:]+"2"
        memo = [0]
        ma = memo.append
        [ma(j+1) for j in range(h) if i[j] != i[j+1]]
        ans = len(memo)-1
        ans2 = [0]
        aa = ans2.append
        memo2 = [0]*ans
        j = 0
        flag = False
        while j < w:
            if flag:
                break
            for k in range(ans):
                memo2[k] += [grid[l][j]
                             for l in range(memo[k], memo[k+1])].count("1")
                if memo2[k] > K:
                    aa(j)
                    memo2 = [0]*ans
                    if j == ans2[-2]:
                        flag = True
                    break
            else:
                j += 1
        if not flag:
            m = min(m, ans+(len(ans2)-2))
    print(m)


main()


### FIXED CODE ###

def main():
    from itertools import product
    h, w, K = map(int, input().split())
    grid = [list(input()) for _ in [0]*h]
    m = 10**9
    for i in range(2**h):
        i = (("0"*h)+bin(i)[2:])[-h:]+"2"
        memo = [0]
        for j in range(h):
            if i[j] == i[j+1]:
                pass
            else:
                memo.append(j+1)
        ans = len(memo)-1
        ans2 = [0]
        memo2 = [0]*ans
        j = 0
        flag = False
        while j < w:
            if flag:
                break
            for k in range(ans):
                memo2[k] += [grid[l][j]
                             for l in range(memo[k], memo[k+1])].count("1")
                if memo2[k] > K:
                    ans2.append(j)
                    memo2 = [0]*ans
                    if ans2[-1] == ans2[-2]:
                        flag = True
                    break
            else:
                j += 1
        if flag == False:
            m = min(m, ans+(len(ans2)-2))
    print(m)


main()
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
s = readline().strip()
n = int(readline())
for i in range(n):
    q = readline()
    if q.startswith("1"):
        s = s[::-1]
    else:
        a = q.strip().split(" ")
        if a[1] == "1":
            s = a[2] + s
        if a[1] == "2":
            s = s + a[2]
print(s)


### FIXED CODE ###

import sys
readline = sys.stdin.readline
s = readline().strip()
n = int(readline())
rev = False
h = []
t = []
for i in range(n):
    q = readline()
    if q.startswith("1"):
        rev = not rev
    if q.startswith("2 1"):
        if not rev:
            h.append(q[-2])
        else:
            t.append(q[-2])
    if q.startswith("2 2"):
        if not rev:
            t.append(q[-2])
        else:
            h.append(q[-2])
s = "".join(h[::-1]) + s + "".join(t)
if rev:
    print(s[::-1])
else:
    print(s)
### BUGGY CODE ###

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
Q = 10**9+7
def main():
    N = int( input())
    A = list( map( int, input().split()))
    s = 1
    for a in A:
        s = s*a//gcd(a,s)
    ans = 0
    for a in A:
        ans += s//a
        ans %= Q
    print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

from collections import defaultdict

def prime_factors(d,N): #素因数 1を含まないことに注意
    ret = []
    middle = int( N**(1/2))
    tmp = N
    for i in range(2, middle+1):
        if tmp%i == 0:
            c = 0
            while tmp%i == 0:
                tmp //= i
                c += 1
            if d[i] < c:
                d[i] = c
    if tmp != 1:
        if d[tmp] == 0:
            d[tmp] = 1

Q = 10**9+7
def main():
    N = int( input())
    A = list( map( int, input().split()))
    d = defaultdict( int)
    for a in A:
        prime_factors(d, a)
    s = 1

    for key, value in d.items():
        s *= pow( key, value)
    ans = 0
    for a in A:
        ans += s*pow(a,Q-2,Q)
    print(ans%Q)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
a = []
b = []
for i in range(n):
    c,d = map(int,input().split())
    a.append(c)
    b.append(d)
t = 0
while(1):
    if len(a)==0:
        break
    
    maxa = -1
    ai = -1
    for k in [i for i, x in enumerate(b) if x == max(b)]:
        if maxa <= a[k]:
            maxa = a[k]
            ai = k
    t += maxa
    del a[ai]
    del b[ai]

    if len(b)==0:
        break
    maxb = -1
    bi = -1
    for k in [i for i, x in enumerate(a) if x == max(a)]:
        if maxb <= b[k]:
            maxb = b[k]
            bi = k
    t -= maxb
    del a[bi]
    del b[bi]
print(t)

### FIXED CODE ###

n = int(input())
ab = []
x = 0
for i in range(n):
  a,b = map(int,input().split())
  x -= b
  ab.append(a+b)
ab.sort()
ab.reverse()
for i in range(n):
  if i%2==0:
      x+=ab[i]
print(x)
### BUGGY CODE ###

n, m = map(int, input().split())
x = list(map(int, input().split()))
x.reverse()
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = cum[i] + x[i]
mincost = 2 * n * m + 5 * cum[n]
for k in range(1,n):
    cost = m * (n + k)
    for i in range(n//k):
        cost += (cum[(i+1)*k] - cum[i*k]) * max(5, 3 + i*2)
    cost += (cum[n] - cum[n//k * k]) * max(5, 3 + n//k*2)
    mincost = min(mincost, cost)
print(mincost)

### FIXED CODE ###

n, m = map(int, input().split())
x = list(map(int, input().split()))
x.reverse()
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = cum[i] + x[i]
mincost = 2 * n * m + 5 * cum[n]
for k in range(1,n):
    cost = m * (n + k)
    for i in range(n//k):
        cost += (cum[(i+1)*k] - cum[i*k]) * max(5, 3 + i*2)
    cost += (cum[n] - cum[n//k * k]) * max(5, 3 + n//k*2)
    mincost = min(mincost, cost)
print(mincost)
### BUGGY CODE ###

S = input()

cnt = 0
while 'BW' in S:
    S = S.replace('BW', 'WB', 1)
    cnt += 1

print(cnt)

### FIXED CODE ###

S = input()
b = 0
ans = 0

for s in S:
    if s == 'B':
        b += 1
    else:
        ans += b

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

n = int(input())
a = [ int(input()) for x in range(n) ] 
    
for i in a:
    b = a.copy()
    b.remove(i)
    print( max(b) )
    

### FIXED CODE ###

n = int(input())
a = [ int(input()) for x in range(n) ] 

b = sorted(a, reverse = True)
maximum = b[0]

for i in a:
    if i == maximum:
        print(b[1])
    else:
        print(maximum)
### BUGGY CODE ###

K,S = list(map(int,input().split()))

x=0
count = 0

for i in range(S+1):
	y=0
	while S-x>=0:
		if S-x-y>=0 and x<=K and y<=K and S-x-y<=K: count+=1
		if y>K: break
		y+=1
	x+=1

print(count)


### FIXED CODE ###

K,S = list(map(int,input().split()))

count = 0

if K>S: n=S
else: n=K
x=0
for i in range(n+1):
	if K>S-x: m=S-x
	else: m=K
	y=0
	for j in range(m+1):
		if S-x-y<=K: count +=1
		y+=1
	x+=1

print(count)
### BUGGY CODE ###

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

### FIXED CODE ###

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

def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    E = []

    D = {C[i]: -1 for i in range(N)}
    for i in range(N):
        if D[C[i]] != -1:
            E.append((D[C[i]], i, -1))
        D[C[i]] = i

    for i in range(Q):
        l, r = map(int, input().split())
        E.append((l - 1, r - 1, i))

    def f(tup):
        return tup[0]
    E.sort(key=f, reverse=True)

    # Binary Indexed Tree (Fenwick Tree)
    class BIT:
        def __init__(self, n):
            self.n = n
            self.data = [0] * (n + 1)
            self.el = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.data[i]
                i -= i & -i
            return s

        def add(self, i, x):
            # assert i > 0
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

        def get(self, i, j=None):
            if j is None:
                return self.el[i]
            return self.sum(j) - self.sum(i)

    ANS = [0] * Q
    d = BIT(N)
    for e in E:
        if e[2] == -1:
            d.add(e[1], 1)
        else:
            ANS[e[2]] = e[1] - e[0] + 1 - d.sum(e[1])

    for i in range(Q):
        print(ANS[i])

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict
import sys
def read():
    return sys.stdin.readline().rstrip()
def main():
    N, Q = map(int, read().split())
    C = list(map(int, read().split()))
    E = defaultdict(list)

    D = [-1] * (N + 1)
    for i in range(N):
        D_i = D[C[i]]
        if D_i != -1:
            E[D_i].append((D_i, i))
        D[C[i]] = i

    F = defaultdict(list)
    for i in range(Q):
        l, r = map(int, input().split())
        F[l-1].append((r - 1, i))



    # Binary Indexed Tree (Fenwick Tree)
    class BIT:
        def __init__(self, n):
            self.n = n
            self.data = [0] * (n + 1)
            self.el = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.data[i]
                i -= i & -i
            return s

        def add(self, i, x):
            # assert i > 0
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

        def get(self, i, j=None):
            if j is None:
                return self.el[i]
            return self.sum(j) - self.sum(i)

    ANS = [0] * Q
    d = BIT(N)
    for x in range(N - 1, -1, -1):
        for e in E[x]:
            d.add(e[1], 1)
        for f in F[x]:
            ANS[f[1]] = f[0] - x + 1 - d.sum(f[0])

    for i in range(Q):
        print(ANS[i])

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

n=int(input())
a=list(map(int,input().split()))
al=0
for i in a:
  al=al^i
r=""
for i in a:
  r+=str(i^al)+" "
print(r[:-1])

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
al=0
for i in a:
  al=al^i
r=""
for i in a:
  r+=str(i^al)+" "
print(r[:-1])
### BUGGY CODE ###

from bisect import bisect

n, m = map(int, input().split())
*a, = map(int, input().split())
a.sort()
BC = []
for _ in range(m):
    b, c = map(int, input().split())
    BC.append((b, c))
BC = sorted(BC, key=lambda x: x[1], reverse=True)
ans = 0
num = 0
for b, c in BC:
    idx = bisect(a[num:], c)
    p = min(idx, b)
    num += p
    ans += c * p
print(sum(a[num:])+ans)


### FIXED CODE ###

n, m = map(int, input().split())
a = [(1, int(i)) for i in input().split()]
for _ in range(m):
    b, c = map(int, input().split())
    a.append((b, c))
a = sorted(a, key=lambda x: x[1])
ans = 0
t = 0
while t < n:
    b, c = a.pop()
    p = min(b, n-t)
    ans += p * c
    t += p
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque

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


# 迷路　BFS
def bfs(sx, sy):
    d = deque()
    d.append((sx, sy, distance[sx][sy]))
    ans = distance[sx][sy]
    v = distance[sx][sy]
    check[sx][sy] = 0

    while len(d):
        x, y, dis = d.popleft()
        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

            if 0 <= nx < n and 0 <= ny < n:
                # 更新できるマスは更新
                if distance[nx][ny] > dis:
                    distance[nx][ny] = dis
                    d.append((nx, ny, dis + check[nx][ny]))

    return ans

distance = [[min(i, j, n - i - 1, n - j - 1) for i in range(n)] for j in range(n)]
check = [[1] * n for i in range(n)]
p = [((i-1)//n, (i-1) % n) for i in p]
anss=0
for i,j in p:
    anss+=bfs(j, i)

print(anss)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

distance = [[min(i, j, n - i - 1, n - j - 1) for i in range(n)] for j in range(n)]
check = [[1] * n for i in range(n)]
p = [((i - 1) // n, (i - 1) % n) for i in p]

def move(x,y,nx,ny):
    if distance[nx][ny] > distance[x][y] + check[x][y]:
        distance[nx][ny] = distance[x][y] + check[x][y]
        d.append((nx,ny))

ans = 0
for i, j in p:
    ans += distance[j][i]
    d=[]
    d.append((j,i))
    check[j][i] = 0
    while len(d):
        x, y = d.pop()
        if x!=0:
            move(x,y,x-1,y)
        if x!=n-1:
            move(x,y,x+1,y)
        if y!=0:
            move(x,y,x,y-1)
        if y!=n-1:
            move(x,y,x,y+1)

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

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

limit=10**9+7

ans=0
for i in range(N-1):
    for j in range(i+1,N):
        ans+=A[i]*A[j]
        ans=ans%limit
print(ans)

### FIXED CODE ###

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

limit=10**9+7
S=[0]
for i in range(N):
    A[i]=A[i]%limit
for i in range(1,N):
    S.append((S[i-1]+A[-i])%limit)
ans=0
for i in range(N-1):
    ans+=A[i]*S[-1-i]
    ans=ans%limit
print(ans)
### BUGGY CODE ###

n, m = map(int,input().split())
a = list(map(int,input().split()))
for k in range(m):
  s, t = map(int,input().split())
  for i in range(s):
    a.append(t)
ans = 0
a.sort(reverse=True)
for v in range(n):
  ans += a[v]
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
b = [list(map(int,input().split())) for p in [0]*m]
b.sort(key=lambda q: -q[1])
#print(a)
#print(b)

c = 0
for s in b:
	for t in [0]*s[0]:
		#print(s)
		if c + 1 > n:
			break
		if s[1] <= a[c]:
			break
		a[c] = s[1]
		c += 1
		#print(a)
	else:
		continue
	break
print(sum(a))
### BUGGY CODE ###

nums = [int(x) for x in input().split()]
N = nums[0]
K = nums[1]
arr = []
for i in range(N):
	nums = [int(x) for x in input().split()]
	for j in range(nums[1]):
		arr.append(nums[0])
arr.sort()
print(arr[K-1])

### FIXED CODE ###

nums = [int(x) for x in input().split()]
N = nums[0]
K = nums[1]
arr = []
for i in range(N):
	nums = [int(x) for x in input().split()]
	arr.append(tuple(nums))

arr = sorted(arr, key=lambda x: x[0])

vol = 0
for i in range(len(arr)):
	vol = vol + arr[i][1]
	if vol >= K:
		print(arr[i][0])
		break
### BUGGY CODE ###

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

S = [int(x) if x!="?" else -1 for x in input()]

div_num = 1000000007
arr = np.arange(13, dtype = np.uint64)
dp = np.zeros([2, 13], dtype = np.uint64)

div13_list = [1]
for ii in range(1, len(S)):
    n = div13_list[-1] * 10 % 13
    if n in div13_list:
        break
    else:
        div13_list.append(n)
div13_mat = np.array([div13_list] * 10, dtype = int)
div13_mat = (div13_mat * np.arange(10)[:, None] % 13).T
# print (div13_mat)

if S[-1] == -1:
    dp[0, :10] = 1
else:
    dp[0, S[-1]] = 1

for ii in range(1, len(S)):
    ind = -ii-1
    tmp = div13_mat[ii%6]
    if S[ind] == -1:
        for n in range(10):
            # res = (div13_list[ii] * n + arr) % 13
            res = (tmp[n] + arr) % 13
            dp[1, res] += dp[0, arr]
    else:
        # res = (div13_list[ii] * S[ind] + arr) % 13
        res = (tmp[S[ind]] + arr) % 13
        dp[1, res] += dp[0, arr]
    dp[0] = dp[1] % div_num
    dp[1] = 0


print (dp[0, 5])


### FIXED CODE ###

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

# S = [int(x) if x!="?" else -1 for x in input()]

# print (S)

# div_num = 1000000007
# arr = np.arange(13, dtype = np.uint64)
# # dp = np.zeros([2, 13], dtype = np.uint64)

# div13_list = [1]
# for ii in range(1, len(S)):
#     n = div13_list[-1] * 10 % 13
#     if n in div13_list:
#         break
#     else:
#         div13_list.append(n)
# div13_mat = np.array([div13_list] * 10, dtype = int)
# div13_mat = (div13_mat * np.arange(10)[:, None] % 13).T

# if S[-1] == -1:
#     dp[0, :10] = 1
# else:
#     dp[0, S[-1]] = 1

# for ii in range(1, len(S)):
#     # ind = -ii-1
#     # tmp = div13_mat[ii%6]
#     # if S[ind] == -1:
#     #     for n in range(10):
#     #         res = np.roll(arr, -tmp[n])
#     #         # dp[1, res] += dp[0, arr]
#     # else:
#     #     res = np.roll(arr, -tmp[S[ind]])
#     #     # dp[1, res] += dp[0, arr]
#     dp[0] = dp[1] % div_num
#     dp[1] = 0


# print (dp[0, 5])

#
# 大きい方の桁からやってく方法
#

MOD = 1000000007;

S = [int(x) if x!="?" else -1 for x in input()]
n = len(S)

# r[i]
# 現在考えてる一つ前の桁数で、余りが i になる整数の個数
r = [0] * 13

# まず一つ目の値が１の位とする
s = S[0]
if (s != -1):
    r[s] = 1
else:
    for i in range(10): r[i] = 1

# 桁を進めながら個数をカウント
for i in range(1, n):
    # dp[j]
    # 現在考えている桁(i)を除く、余りが j となる整数の個数
    dp = [0] * 26

    # 桁が一つ上がるので、一つ前の余りが 10 倍になる
    for j in range(13):
        dp[j*10%13] += r[j] % MOD

    # アクセスを高速にするため２倍の長さとる (dp[i] == dp[i + 13])
    dp[13:26] = dp[0:13]

    r = [0]*13

    s = S[i]
    if (s == -1):
        w = sum(dp[4:14])
        for j in range(13):
            r[j] += w
            w += dp[j + 1]-dp[j + 4]
    else:
        for j in range(13):
            r[j] += dp[13-s+j]
print (r[5]%MOD)
### BUGGY CODE ###

N= int(input())
S=input()
r=[]
g=[]
b=[]
A=0
B=0
C=0
for i in range(N):
    if S[i]=="R":
        r.append(i)
        A+=1
    elif S[i]=="G":
        g.append(i)
        B+=1
    else:
        b.append(i)
        C+=1
k=0
for i in r:
    x=i

    for j in g:
        y=j

        if 2*x-y in b:
            k+=1
        if 2*y-x in b:
            k+=1
        if (x+y)/2 in b:
            k+=1

print(A*B*C-k)

### FIXED CODE ###

N= int(input())
S=input()
r=[]
g=[]
b=[]
A=0
B=0
C=0
for i in range(N):
    if S[i]=="R":
        r.append(i)
        A+=1
    elif S[i]=="G":
        g.append(i)
        B+=1
    else:
        b.append(i)
        C+=1
k=0
for i in range(N-2):
    for j in range(i+1,N-1):
        t=2*j-i
        if t<N:
            if S[i]!=S[j] and S[i]!=S[t] and S[t]!=S[j] :
                k+=1

print(A*B*C-k)
### BUGGY CODE ###

r=[0]*3
r[0],r[1],r[2],n=map(int, input().split())
ct=0
r=sorted(r)

for i in range(n//r[2]+1):
    for j in range(min(n//r[1]+1, n-r[2]*i+1)):
        if (n-(i*r[2]+j*r[1]))%r[0]==0 and 0<=(n-(i*r[2]+j*r[1]))<=n+1:
            ct+=1
print(ct)
    

### FIXED CODE ###

r=[0]*3
r[0],r[1],r[2],n=map(int, input().split())
ct=0
r=sorted(r)

for i in range(n//r[2]+1):
    for j in range(min(n//r[1]+1, n-r[2]*i+1)):
        if (n-(i*r[2]+j*r[1]))%r[0]==0 and 0<=(n-(i*r[2]+j*r[1]))<=n+1:
            ct+=1
print(ct)
### BUGGY CODE ###

import itertools

N=int(input())
A = tuple(map(int,input().split(" ")))
ans = 0

for pair in itertools.combinations(A, 2):
    ans += pair[0] * pair[1]


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

### FIXED CODE ###

N=int(input())
A = tuple(map(int,input().split(" ")))
ans = 0

sum_ = sum(A)
for i in range(N):
    sum_ -= A[i]
    ans += sum_ * A[i]

print(ans % ( (10**9)+7) )
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
path = [0 for i in range(n+1)]
for a,b in ab:
  graph[b].append(a)
  path[a] = -1
stack = []
for i in range(1,n+1):
  if path[i] == 0:
    stack.append(i)
    while stack:
      x = stack.pop()
      for y in graph[x]:
        if path[x]+1 > path[y]:
          stack.append(y)
          path[y] = path[x]+1
print(max(path))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
path = [0 for i in range(n+1)]
con = [0 for i in range(n+1)]
for a,b in ab:
  graph[b].append(a)
  path[a] = -1
  con[a] += 1
stack = []
for i in range(1,n+1):
  if path[i] == 0:
    stack.append(i)
    while stack:
      x = stack.pop()
      for y in graph[x]:
        path[y] = max(path[y],path[x]+1)
        con[y] -= 1
        if con[y] == 0:
          stack.append(y)
print(max(path))
### BUGGY CODE ###

#!/usr/bin/env python3
# coding=utf-8

import sys
import random

import functools


@functools.lru_cache(1000000)
def is_prime3(q, k=50):
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False

    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    for i in range(k):
        a = random.randint(1, q - 1)
        t = d
        y = pow(a, t, q)
        while t != q - 1 and y != 1 and y != q - 1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q - 1 and t & 1 == 0:
            return False
    return True


q = int(sys.stdin.readline().strip())
for _ in range(q):
    l, r = sys.stdin.readline().strip().split(" ")
    l = int(l)
    r = int(r)
    ans = 0
    for i in range(l, r + 1, 2):
        if is_prime3(i) and is_prime3((i + 1) // 2):
            ans += 1
    print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
# coding=utf-8

import sys

import numpy as np

num_max = 100000
primes = np.asarray([True for _ in range(num_max + 1)])
for i in range(num_max + 1):
    if i == 0 or i == 1:
        primes[i] = False
    else:
        primes[i * 2::i] = False
primes = set(np.arange(num_max + 1)[primes])
like2017 = [1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(num_max + 1)]
cumsum = np.cumsum(like2017)

q = int(sys.stdin.readline().strip())
for _ in range(q):
    l, r = sys.stdin.readline().strip().split(" ")
    l = int(l)
    r = int(r)
    print(cumsum[r] - cumsum[l - 1])
### BUGGY CODE ###

N = int(input())

devide = 10 ** 9 + 7

power = 1
for i in range(1, N + 1):
    power *= i

print(power % devide)

### FIXED CODE ###

N = int(input())

devide = 10 ** 9 + 7

power = 1
for i in range(1, N + 1):
    power = power * i % devide

#power %= devide
print(power)
### BUGGY CODE ###

s = input()
n = len(s)
#s_cu = [] 
counter = [0] * 2019

counter[0] += 1
temp=""
for i in range(1, n+1):
    temp = s[n-i] + (temp if i != 1 else "")
    #s_cu.append(temp)
    counter[int(temp) % 2019] += 1

ans = 0
for i in counter:
    ans += (i * (i - 1)) // 2

print(ans)

### FIXED CODE ###

#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code
def resolve():
    S=input()
    n=len(S)
    
    S2=[0]*n
    digit=0
    for i in range(n-1,-1,-1):
        s=int(S[i])
        S2[i]=(s*pow(10,digit,2019))%2019
        digit+=1
    #print(S2)

    S3=[0]*n;subsum=0
    for j,s2 in enumerate(S2):
        subsum+=s2;subsum%=2019;S3[j]=subsum
    S3.append(0)
    #print(S3)

    from collections import Counter
    c=Counter(S3).values()
    ans=0
    for k in c:
        if k>1:
            ans+=(k*(k-1))//2
    print(ans)
#%%submit!
resolve()