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

#!/usr/bin/env python3
import sys


def sort(A):
    for i in range(1, len(A)):
        insert(A, i)


def insert(A, i):
    temp = A[i]
    for j in range(i - 1, -1, -1):
        if temp < A[j]:
            A[j + 1] = A[j]
        else:
            A[j + 1] = temp
            break
    else:
        A[0] = temp


def solve(N: int, M: int, A: "List[int]"):
    sort(A)
    for i in range(M):
        MD = A[-1]
        A[-1] = MD // 2
        sort(A)
        if A[-1] == 0:
            break
    print(sum(A))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, A: "List[int]"):
    while M > 0:
        A = sorted(A, reverse=True)
        MD = A[0] // 2
        for i, ai in enumerate(A):
            if ai > MD and M > 0:
                A[i] = ai//2
                M -= 1
            else:
                break
        if A[i] == 0:
            break
    print(sum(A))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)


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

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


# total:累計, i:index
def dfs(total, i):
    if i == n:
        if total % 10 != 0:
            return total
        else:
            return 0
    return max(dfs(total, i + 1), dfs(total + s[i], i + 1))


print(dfs(0, 0))


### FIXED CODE ###

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

total = sum(s)
s.sort()
if total % 10 != 0:
    print(total)
else:
    for i in range(n):
        if (total - s[i]) % 10 != 0:
            print(total - s[i])
            exit()
    print(0)
### BUGGY CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
print(0)
l = ns()
r = l
if L == "Vacant":
    exit()

ng = 0
ok = n
while True:
    mid = (ng + ok) // 2
    print(mid)
    q = input()
    if q == "Vacant":
        exit()
    if (q == l) ^ ((mid - ng)%2 == 1):
        ng = mid
        l = q
    else:
        ok = m
        r = q

### FIXED CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = int(input())
print(0)
l = input()
r = l
if l == "Vacant":
    exit()

ng,ok = 0,n
while True:
    mid = (ng + ok) // 2
    print(mid)
    q = input()
    if q == "Vacant":
        exit()
    if (q == l) ^ ((mid - ng)%2 == 1):
        ng = mid
        l = q
    else:
        ok = mid
        r = q
### BUGGY CODE ###

N,W = map(int, input().split())

knap = [0 for i in range(W+1)]
mono = []

for i in range(N):
    w,v = map(int, input().split())
    mono.append([w,v])
    
for w, v in mono:
    for i in range(w, W+1)[::-1]:
        knap[i] = max(knap[i], knap[i-w] + v)
print(knap[W])


### FIXED CODE ###

from itertools import accumulate
n,w=map(int, input().split())
items = {}
for _ in range(n):
    u,v = map(int, input().split())
    if u not in items:
        items[u] = []
    items[u].append(v)
cost = 0
acc = []
minkey = min(items.keys())
for i in range(4):
    if minkey + i in items:
        items[minkey + i].sort(reverse=True)
        acc.append([0] + list(accumulate(items[minkey + i])))
    else:
        acc.append([0])

ans = 0
for i in range(len(acc[0])):
    a = (i) * minkey
    if w < a:
        continue
    for j in range(len(acc[1])):
        b = (j) * (minkey+1)
        if w < a + b:
            continue
        for k in range(len(acc[2])):
            c = (k) * (minkey+2)
            if w < a + b + c:
                continue
            for l in range(len(acc[3])):
                d = (l) * (minkey+3)
                if w < a + b + c + d:
                    continue
                cost = acc[0][i] + acc[1][j] + acc[2][k] + acc[3][l]
                if cost > ans :
                    ans = cost

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

K = int(input())
S = 7
i = 1
if (1 <= K) and (K <= (10 ** 6)):
    while True:

        if int(S) % K != 0:
            S = S * 10 + 7
            i += 1
        elif i > K:
            break
        else:
            break
    print(i)
else:
    print('"K" is out of range!')


### FIXED CODE ###

K = int(input())
if K % 2 == 0:
    print(-1)
elif K % 5 == 0:
    print(-1)
else:
    S = 7
    for i in range(K+1):
        if S % K == 0:
            print(i+1)
            break
        else:
            S = S % K
            S = S * 10 + 7
    else:
        print(-1)
### 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 ###

import heapq

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

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

for x in range(K):
#	print(data)
	raise_queue = []
	down_queue = []
	for i, d in enumerate(data):
		heapq.heappush(raise_queue, (i - d, i + d))
	
	new_data = [0] * N
	height = 0
	ended = 0
	for i in range(N):
		while len(raise_queue) > 0 and raise_queue[0][0] <= i:
			height += 1
			heapq.heappush(down_queue, raise_queue[0][1])
			heapq.heappop(raise_queue)
		while len(down_queue) > 0 and down_queue[0] < i:
			height -= 1
			heapq.heappop(down_queue)
		
		new_data[i] = height
		if height == N:
			ended += 1
	
	data = new_data
	if ended == N:
		#print(x)
		break
	
print(*data)


### FIXED CODE ###

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

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

for x in range(K):
#	print(data)
	raise_data = [0] * (N + 1)
	for i, d in enumerate(data):
		raise_data[max(0, i - d)] += 1
		raise_data[min(N, i + d + 1)] -= 1
	
	height = 0
	ended = 0
	for i in range(N):
		height += raise_data[i]
		data[i] = height
		if height == N:
			ended += 1
	
	if ended == N:
#		print(x)
		break
	
print(*data)
### BUGGY CODE ###

N, point, Q = map(int, input().split())
ans = [int(input()) for i in range(Q)]
ans = [n-1 for n in ans]
# participants = [i for i in range(N)]
points = [point for i in range(N)]

for i in ans:
    points = [n-1 for n in points]
    points[i] += 1

for i in range(N):
    if points[i] > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

N, point, Q = map(int, input().split())
ans = [int(input()) for i in range(Q)]
ans = [n-1 for n in ans]
# participants = [i for i in range(N)]
points = [point for i in range(N)]

points = [n-len(ans) for n in points]

for i in ans:
    points[i] += 1

#print(N, point, Q, ans, points)

for i in range(N):
    if points[i] > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import heapq
import itertools
import sys
input = sys.stdin.readline

n, m, r = [ int(v) for v in input().split() ]
town_list = [ int(v)-1 for v in input().split() ]

road_matrix = [ [ 10**9 for j in range(n) ] for i in range(n) ]


for i in range(m):
	s, e, d = [ int(v) - 1 for v in input().split() ]
	road_matrix[s][e] = d + 1
	road_matrix[e][s] = d + 1


min_dist_matrix = []
for h in range(n):
	min_dist = [ min_dist_matrix[i][h] for i in range(h)] + road_matrix[h][h:]
	searched_point = []
	sarching_point = []
	j = h
	while len(searched_point) < n:
		heapq.heappush(searched_point,j)
		for i in range(n):
			if road_matrix[j][i] != 10**9 and i != h:
				heapq.heappush(sarching_point,(road_matrix[j][i],i))
				min_dist[i] = min(min_dist[i],min_dist[j] + road_matrix[j][i])
		sarching_point.sort()

		for k in range(len(sarching_point)):
			s = heapq.heappop(sarching_point)
			if s[1] not in searched_point:
				j = s[1]
				break

	min_dist_matrix.append(min_dist)


mindist = 10**9
for i in itertools.permutations(town_list,r):
	dist = 0
	for j in range(r-1):
		dist += min_dist_matrix[i[j]][i[j+1]]

	mindist = min(mindist,dist)
print(mindist)

### FIXED CODE ###

import itertools
import sys
input = sys.stdin.readline

n, m, r = [ int(v) for v in input().split() ]
town_list = [ int(v)-1 for v in input().split() ]

road_matrix = [ [ 10**9 for j in range(n) ] for i in range(n) ]


for i in range(m):
	s, e, d = [ int(v) - 1 for v in input().split() ]
	road_matrix[s][e] = d + 1
	road_matrix[e][s] = d + 1


for k in range(n):
	 for i in range(n):
		 for j in range(n):
			 road_matrix[i][j]  = min(road_matrix[i][k] + road_matrix[k][j], road_matrix[i][j])


mindist = 10**9
for i in itertools.permutations(town_list,r):
	dist = 0
	for j in range(r-1):
		dist += road_matrix[i[j]][i[j+1]]

	mindist = min(mindist,dist)
print(mindist)
### BUGGY CODE ###

import sys

h, w = list(map(int, input().split()))
field = [line.rstrip() for line in sys.stdin]

l = [[0] * (w + 2) for _ in [0] * (h + 2)]
r = [[0] * (w + 2) for _ in [0] * (h + 2)]
u = [[0] * (w + 2) for _ in [0] * (h + 2)]
d = [[0] * (w + 2) for _ in [0] * (h + 2)]

for i in range(1, h + 1):
    fi = field[i - 1]
    li = l[i]
    for j in range(1, w + 1):
        c = fi[j - 1]
        u[i][j] = u[i - 1][j] + 1 if c == '.' else 0
        li[j] = li[j - 1] + 1 if c == '.' else 0
for i in range(h, 0, -1):
    fi = field[i - 1]
    ri = r[i]
    for j in range(w, 0, -1):
        c = fi[j - 1]
        d[i][j] = d[i + 1][j] + 1 if c == '.' else 0
        ri[j] = ri[j + 1] + 1 if c == '.' else 0

ans = 0
for i in range(1, h + 1):
    li, ri, ui, di = l[i], r[i], u[i], d[i]
    ans = max(ans, max(li[j] + ri[j] + ui[j] + di[j] for j in range(1, w + 1)))
print(ans - 3)


### FIXED CODE ###

import sys

h, w = list(map(int, input().split()))
field = [line.rstrip() for line in sys.stdin]

l = [[0] * (w + 2) for _ in [0] * (h + 2)]
r = [[0] * (w + 2) for _ in [0] * (h + 2)]
u = [[0] * (w + 2) for _ in [0] * (h + 2)]
d = [[0] * (w + 2) for _ in [0] * (h + 2)]

for i in range(1, h + 1):
    fi = field[i - 1]
    li = l[i]
    for j in range(1, w + 1):
        c = fi[j - 1]
        u[i][j] = u[i - 1][j] + 1 if c == '.' else 0
        li[j] = li[j - 1] + 1 if c == '.' else 0
for i in range(h, 0, -1):
    fi = field[i - 1]
    ri = r[i]
    for j in range(w, 0, -1):
        c = fi[j - 1]
        d[i][j] = d[i + 1][j] + 1 if c == '.' else 0
        ri[j] = ri[j + 1] + 1 if c == '.' else 0

ans = 0
for i in range(1, h + 1):
    li, ri, ui, di = l[i], r[i], u[i], d[i]
    ans = max(ans, max(li[j] + ri[j] + ui[j] + di[j] for j in range(1, w + 1)))
print(ans - 3)
### BUGGY CODE ###

n = int(input())
b = list(map(int, input().split()))
for i in range(n):
  print(b.count(i+1))

### FIXED CODE ###

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

c = collections.Counter(a)
for i in range(n):
  print(c[i+1])
### BUGGY CODE ###

n = int(input())
h = list(map(int, input().split()))
a = 0
for i in range(n-1):
    for j in h[i+1:]:
        if h[i]-j >= 2:
            print('No')
            exit()

print('Yes')


### FIXED CODE ###

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

c = 0
for i in range(n-1):
    if h[i] <= h[i+1]-1:
        h[i+1] = h[i+1]-1
    elif h[i] == h[i+1]:
        continue
    else:
        c = 1
if c == 1:
    print('No')
else:
    print('Yes')
### BUGGY CODE ###

n=int(input())
x=list(map(int,input().split()))
dic={}
for i in range(n):
  if x[i] in dic.keys():
    dic[x[i]]+=1
  else:
    dic[x[i]]=1
s=0
for i in dic.keys():
  s+=dic[i]*(dic[i]-1)//2
for i in range(n):
  print(s-dic[x[i]]+1)

### FIXED CODE ###

n=int(input())
x=list(map(int,input().split()))
dic={}
for i in range(n):
  if x[i] in dic.keys():
    dic[x[i]]+=1
  else:
    dic[x[i]]=1
s=0
for i in dic.keys():
  s+=dic[i]*(dic[i]-1)//2
for i in range(n):
  print(s-dic[x[i]]+1)
### BUGGY CODE ###

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

DPLIST=[[None]*N for i in range(N)]

SUM=[0]
for i in range(N):
    DPLIST[i][i]=0
    SUM.append(SUM[-1]+A[i])

for i in range(1,N):
    for j in range(i,N):

        ANS=float("inf")

        for k in range(j-i,j):

            if ANS>DPLIST[j-i][k]+DPLIST[k+1][j]+SUM[j+1]-SUM[j-i]:
                ANS=DPLIST[j-i][k]+DPLIST[k+1][j]+SUM[j+1]-SUM[j-i]
        
        DPLIST[j-i][j]=ANS

print(DPLIST[0][N-1])

### FIXED CODE ###

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

DPLIST=[[None]*N for i in range(N)]

for i in range(N):
    DPLIST[i][i]=[0,A[i]]

for i in range(1,N):
    for j in range(i,N):
        #print(i,j)
        ANS=float("inf")
        slime=float("inf")

        for k in range(j-i,j):
            sc1,sl1=DPLIST[j-i][k]
            sc2,sl2=DPLIST[k+1][j]

            if ANS>sc1+sc2+sl1+sl2:
                ANS=sc1+sc2+sl1+sl2
                slime=sl1+sl2
        
        DPLIST[j-i][j]=[ANS,slime]

    #print(DPLIST)
    #print()
            

print(DPLIST[0][N-1][0])
### BUGGY CODE ###

from collections import Counter
import re
import sys

s=input()
checked=[]
for i in range(len(s)-1):
    suffix=s[i:]
    f_len=len(suffix)
    for j in range(f_len-1):
        if(j==0):
            fact=suffix
        elif(j>0):
            fact=fact[:-1]
        if(fact in checked):
            continue
        count=Counter(fact)
        count_max=max(count.values())
        moji=[moji for moji,j in count.items() if j==count_max]
        moji=moji[0]
        if(count[moji]>len(fact)/2 and len(fact)>1):
            span=(re.search(fact,s).span())
            print(span[0]+1,span[1])
            sys.exit()
        checked.append(fact)
print(-1,-1)

### FIXED CODE ###

arr = list(input())
tmp1 = arr[0]
tmp2 = arr[1]
 
i = 2
flg = True
if (tmp1 != tmp2):
    while i < len(arr):
        tmp3 = arr[i]
        if (tmp3 == tmp2):
            print(str(i) + " " + str(i + 1))
            flg = False
            break
        if (tmp3 == tmp1):
            print(str(i - 1) + " " + str(i + 1))
            flg = False
            break
 
        tmp1 = arr[i - 1]
        tmp2 = arr[i]
        i = i + 1
else:
    print("1 2")
    flg = False
 
if (flg):
    print("-1 -1")
### BUGGY CODE ###

K,S = map(int,input().split())
answer = 0 

for i in range(K+1):
    for j in range(K+1):
        for q in range(K+1):
            if i+j+q == S:
                answer+=1
print(answer)

### FIXED CODE ###

K,S = map(int,input().split())
answer = 0 

for i in range(K+1):
    for j in range(K+1):
        if 0 <= S-i-j and S-i-j <= K:
            answer+=1
print(answer)
### BUGGY CODE ###

n,k=map(int,input().split())
*a,=map(int,input().split())
l=[]
for i in range(n):
    t=0
    for j in range(i,n):
        t+=a[j]
        l.append(t)
list=[[]for _ in range(50)]
for t in l:
    u=bin(t)[2:][::-1]
    for i,v in zip(range(50),u):
        if int(v):list[i].append(t)
for t in list[::-1]:
    if len(t)>=k:
        import itertools
        m=0
        for v in itertools.combinations(t,k):
            u=v[0]
            for i in v[1:]:
                u&=i
            m=max(m,u)
        print(m)
        exit()

### FIXED CODE ###

n,k,*a=map(int,open(0).read().split())
l=[]
for i in range(n):
    t=0
    for j in range(i,n):
        t+=a[j]
        l.append(t)
for i in range(40,-1,-1):
    j=2**i
    t=[]
    for x in l:
        if x&j:
            t.append(x)
    if len(t)>=k:
        l=t
a,*b=l
for t in b:
    a&=t
print(a)
### BUGGY CODE ###

A,B,C,K = map(int,input().split())
x = 0
while A>0 and K>0:
    A -= 1
    x += 1
    K -= 1
while B>0 and K>0:
    B -= 1
    K -= 1
while C>0 and K>0:
    C -= 1
    x -= 1
    K -= 1
print(x)

### FIXED CODE ###

A,B,C,K = map(int,input().split())
if K<=A:
    print(K)
elif K<=A+B:
    print(A)
elif K<=A+B+C:
    print(A-(K-A-B))
else:
    print(A-C)
### BUGGY CODE ###

import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

ans = INF
for i in range(N-1):
    x = sum(A[:i+1])
    y = sum(A[i+1:])

    tmp = abs(x - y)
    if tmp < ans:
        ans = tmp
print(ans)


### FIXED CODE ###

import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

if N == 2:
    print(abs(A[0] - A[1]))
else:
    ans = INF

    x = A[0]
    y = sum(A[1:])

    for i in range(1, N-2):
        x = x + A[i]
        y = y - A[i]

        tmp = abs(x - y)
        if tmp < ans:
            ans = tmp
    print(ans)
### BUGGY CODE ###

s = input()[::-1]
mod = 2019
cnt = [0] * mod
x = 1
cnt[0] = 1
total = 0
for s in s:
    total += int(s) * x
    total %= mod
    cnt[total] += 1
    x *= 10


ans = sum(i*(i-1)//2 for i in cnt)
print(ans)


### FIXED CODE ###

s = input()[::-1]
m = 2019
ans = 0
x = 1
tot = 0
cnt = [0] * m
cnt[0] = 1
for s in s:
    tot += int(s) * x
    tot %= m
    #ans += cnt[tot]
    x *= 10
    x %= m
    cnt[tot] += 1

print(sum(i*(i-1)//2 for i in cnt))
### BUGGY CODE ###

n, Y = [int(s) for s in input().split(' ')]
 
max_x = int(Y/10000)
for x in range(max_x, -1, -1):
    if Y < x * 10000 or n < x:
        continue
    
    max_y = int((Y-x*10000)/5000)
    for y in range(max_y, -1, -1):
        if Y < x*10000+y*5000 or n < x+y:
            continue
            
        z = int((Y-x*10000-y*5000)/1000)
        if (Y-x*10000-y*5000) % 1000 == 0 and n == x+y+z:
            print('{} {} {}'.format(x, y, z))
            exit()
            
print('-1 -1 -1')

### FIXED CODE ###

n, y = list(map(int, input().split(' ')))
if y % 1000 != 0:
    print('-1 -1 -1')
    exit()
for ten_th in range(min(n, int(y / 10000)), -1, -1):
    if y < ten_th * 10000 or n < ten_th:
        continue
    for five_th in range(min(n - ten_th, int((y - ten_th * 10000) / 5000)), -1, -1):
        if y < ten_th * 10000 + five_th * 5000 or n < ten_th + five_th:
            continue
        if (y - ten_th * 10000 - five_th * 5000) % 1000 == 0:
            th = int((y - ten_th * 10000 - five_th * 5000) / 1000)
            if n == ten_th + five_th + th:
                print('{} {} {}'.format(ten_th, five_th, th))
                exit()
print('-1 -1 -1')
### BUGGY CODE ###

import itertools
n = int(input())


def prime_factorize(n):
    r = []
    while n % 2 == 0:
        r.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            r.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        r.append(n)
    return r


p = prime_factorize(n)
ans = 10**13
pr0 = 1
for pp in p:
    pr0 *= pp

for i in range(1, len(p)+1):
    for P in itertools.combinations(p, i):
        pr = 1
        for pp in P:
            pr *= pp
        ans = min(ans, pr+pr0//pr-2)

print(ans)

### FIXED CODE ###

n = int(input())

ans = 10**13
for i in range(1, int(n**0.5//1)+1):
    if n%i == 0:
        ans = min(ans, i+n//i-2)
print(ans)
### BUGGY CODE ###

S = input()
length = len(S)
count = 0
for j in range(4, length+1, 1):
    for i in range(0,j-4, 1 ):
        subset = S[i:j]
        if(int(subset) % 2019 == 0):
            count = count + 1

print(count)

### FIXED CODE ###

reverse_S = input()[::-1]
n = len(reverse_S)
count = 0
mod = 0
mods = [0] * 2019
mods[0] = 1
x = 1
for s in reverse_S:
    mod = (mod + (int(s) * x)) % 2019
    mods[mod] = mods[mod] + 1
    x = x * 10
    x = x % 2019

for v in mods:
    count = count + v*(v-1)//2

print(count)