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

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))

    n = 10 ** 6
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    prime_list = [i for i in range(n + 1) if is_prime[i]]

    lcm_dic = {}
    Alist = []

    for a in A:
        a_dic = {}
        for num in prime_list:
            if num > a ** 0.5 + 1:
                if a in a_dic:
                    a_dic[a] += 1
                    break
                else:
                    a_dic[a] = 1
                    break
            while a % num == 0:
                if num in a_dic:
                    a //= num
                    a_dic[num] += 1
                else:
                    a //= num
                    a_dic[num] = 1
        Alist.append(a_dic)
        for k, v in a_dic.items():
            if k not in lcm_dic:
                lcm_dic[k] = v
            else:
                lcm_dic[k] = max(lcm_dic[k], v)

    ans = 0
    for ad in Alist:
        tmpnum = 1
        for k, v in lcm_dic.items():
            if k in ad:
                tmpnum *= k ** (v - ad[k])
                tmpnum %= mod
            else:
                tmpnum *= k ** v
                tmpnum %= mod
        ans += tmpnum
        ans %= mod
    print(ans)




if __name__ == '__main__':
    solve()

### FIXED CODE ###

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))

    lcmnum = 1
    def gcd(a, b):
        if (a == 0):
            return b
        return gcd(b%a, a)

    def lcm(x, y):
        return (x * y) // gcd(x, y)
    for a in A:
        lcmnum = lcm(lcmnum, a)

    ans = 0
    for a in A:
        a = lcmnum // a
        ans += a
    ans %= mod

    print(ans)




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

NK = input().split()
N, K = int(NK[0]), int(NK[1])
#lis_p = list(map(lambda x: int(x), input().split()))
lis_exp = list(map(lambda x: (int(x)+1)/2, input().split()))
dp=0
for i in range(N):
    dp = max(sum(lis_exp[i:i+K]), dp)
print(dp)

### FIXED CODE ###

N, K = map(int, input().split())
lis_p = map(int, input().split())
def calc_exp(x):
    return (int(x) + 1)/2
lis_exp = list(map(calc_exp, lis_p))
dp= sum(lis_exp[0:K])
cumKsum = sum(lis_exp[0:K])
for i in range(1, N-K+1):
    cumKsum = cumKsum - lis_exp[i-1] + lis_exp[i+K-1]
    dp = max(cumKsum, dp)
print(dp)
### BUGGY CODE ###

n=int(input())
l=[[] for _ in range(n)]
cost=[[] for _ in range(n)]
ans=[-1 for _ in range(n)]
ans[0]=0
q=[]
q.append(0)
for iii in range(n-1):
  a,b,w=[int(_) for _ in input().split()]
  a-=1
  b-=1
  l[a].append(b)
  cost[a].append(w)
  l[b].append(a)
  cost[b].append(w)
while not q==[]:
  v=q[0]
  q=q[1:]
  for jjj in range(len(l[v])):
    u = l[v][jjj]
    w = cost[v][jjj]
    if not ans[u]==-1:
      continue
    ans[u]=(ans[v]+w)%2
    q.append(u)
for a in ans:
  print(a)
  
  
    

### FIXED CODE ###

from collections import deque

n=int(input())
l=[[] for _ in range(n)]
cost=[[] for _ in range(n)]
ans=[-1 for _ in range(n)]
ans[0]=0
q=deque([])
q.append(0)
for iii in range(n-1):
  a,b,w=[int(_) for _ in input().split()]
  a-=1
  b-=1
  l[a].append(b)
  cost[a].append(w)
  l[b].append(a)
  cost[b].append(w)
while not q==deque([]):
  v=q.popleft()
  for jjj in range(len(l[v])):
    u = l[v][jjj]
    w = cost[v][jjj]
    if not ans[u]==-1:
      continue
    ans[u]=(ans[v]+w)%2
    q.append(u)
for a in ans:
  print(a)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2*10**5)

n = int(input())
a = list(map(int, input().split()))
# aのindexを前計算
d = {}
for i,j in enumerate(a):
    d[j] = i


# segtree
data = [float("inf")]*(2*n)
# a_k の値を x に更新
def update(k, x):
    k += n-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + n; R = r + n
    s = float("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

# initialize
for i, j in enumerate(a):
    update(i,j)

# 区間[left, right)が与えられた場合の和を求める再帰
def rec(left=0, right=n):
    if left==right:
        return 0
    min_ = query(left, right)
    ind = d[min_]
    res = min_*(right-ind)*(ind+1-left)
    res += rec(left, ind)
    res += rec(ind+1,right)
    return res

print(rec())

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
d = {}
for i,j in enumerate(a):
    d[j] = i

uf = [-1]*n
def root(a):
    if uf[a] < 0:
        return a
    uf[a] = root(uf[a])
    return uf[a]
def unite(a,b):
    ra,rb = root(a),root(b)
    if ra==rb:
        return False
    if uf[ra] > uf[rb]:
        ra,rb = rb,ra
    uf[ra] += uf[rb]
    uf[rb] = ra
    return True

ans = 0
for i in range(n,0,-1):
    left=right=0
    ind = d[i]

    if ind<n-1 and a[ind] < a[ind+1]:
        right -= uf[root(ind+1)]
        unite(ind, ind+1)
    if ind>0 and a[ind] < a[ind-1]:
        left -= uf[root(ind-1)]
        unite(ind, ind-1)
    ans += i*(left+1)*(right+1)

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

k , n = (int(x) for x in input().split())
a = [int(i) for i in input().split()]

b = []
  
for i in range(n-1):
    b.append(a[i+1] - a[i])
    
b.append(a[0] + k -a[n-1])
 
lans=0
ans = 999999999999
 
for i in range(len(b)):
    lans = 0
    for j in range(len(b)):
        if i != j:
            lans = b[j] + lans
    ans = min(ans,lans)
    
print(ans)

### FIXED CODE ###

k , n = (int(x) for x in input().split())
a = [int(i) for i in input().split()]
b = []
 
for i in range(n-1):
    b.append(a[i+1] - a[i])
    
b.append(a[0] + k -a[n-1])

ans=0 
b.sort()
 
for i in range(len(b)-1):
    ans = b[i] + ans

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

N, K = map(int, input().split())
p = list(map(int, input().split()))
ans = 0
for i in range(N-K+1):
    s = sum(p[i : i + K])
    if s > ans:
        ans = s
print((ans + K) / 2)

### FIXED CODE ###

N, K = map(int, input().split())
p = [int(x) for x in input().split()]
s = sum(p[0 : K])
ans = sum(p[0 : K])
f = N-K+1
for i in range(1, f):
    s = s - p[i-1] + p[i + K - 1]
    if ans <= s:
        ans = s
print((ans + K) / 2)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
for i in range(N):
    ans *= A[i]
if ans > 1000000000000000000:
    ans = -1
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 1
for i in range(N):
    ans *= A[i]
    if ans > 1000000000000000000:
        ans = -1
        break
print(ans)
### BUGGY CODE ###

import copy
import collections
import math

def combinations_count(n, r):
    if n <= 1:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N = int(input())
A = [int(i) for i in input().split()] 

maxnum = max(A)
lis = [-1] * maxnum

for i, a in enumerate(A):
  if lis[a-1] < 0:
    newA = copy.deepcopy(A)
    newA.pop(i)
    c = collections.Counter(newA)
    total = 0
    for idx in c:
      total += combinations_count(c[idx], 2)
      
    lis[a-1] = total
    print(total)
  else:
    print(lis[a-1])
    
  

### FIXED CODE ###

import copy
import collections
import math
 
N = int(input())
A = [int(i) for i in input().split()] 
 
maxnum = max(A)
lis = [-1] * maxnum
bigC = collections.Counter(A)
for i, a in enumerate(A):
  if lis[a-1] < 0:
    newA = copy.deepcopy(A)
    newA.pop(i)
    c = collections.Counter(newA)
    total = 0
    for idx in c:
      num = c[idx]
      total += num * (num-1) // 2
      
    lis[a-1] = total
    for x in bigC:
      if bigC[x] == bigC[a]:
        lis[x-1] = total
      
    print(total)
  else:
    print(lis[a-1])
### BUGGY CODE ###

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()))

AB=[]
for i in range(X):
    for j in range(Y):
        AB.append(A[i]+B[j])
        
AB.sort(reverse=True)
tmp=AB[0:min(K,len(AB))]

ABC=[]
for i in range(len(tmp)):
    for j in range(Z):
        ABC.append(tmp[i]+C[j])

ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])

### FIXED CODE ###

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

ABC=[]
for i in range(X):
    for j in range(Y):
        for k in range(Z):
            if (i+1)*(j+1)*(k+1)<=K:
                ABC.append(A[i] + B[j] + C[k])
            else:
                break

ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])
### BUGGY CODE ###

N,D,A = map(int,input().split())
X = []
for _ in range(N):
    x,h = map(int,input().split())
    X.append([x,h])
X.sort()
ans = 0
for i in range(N):
    x = int(X[i][0])
    h = int(X[i][1])
    if h % A == 0:
        count = h // A
    else:
        count = h // A + 1
    ans += count
    dmg = A * count
    #print(ans,dmg)
    for j in range(i+1,N):
        x2 = int(X[j][0])
        h2 = int(X[j][1])
        if  x + (2 * D) < x2:
            break
        else:
            X[j][1] = max(0,h2-dmg)
            #print(X[j])
print(ans)

### FIXED CODE ###

N,D,A = map(int,input().split())
X = []
for _ in range(N):
    x,h = map(int,input().split())
    X.append([x,h])
X.sort()
if X[-1][0] - X[0][0] < 2 * D:
    ans = 0 
    max = 0
    for i in range(N):
        if X[i][1] > max:
            max = X[i][1]
    if max % A == 0:
        ans = max // A
    else:
        ans = max // A + 1
else:
    ans = 0
    for i in range(N):
        h = int(X[i][1])
        if h != 0:
            x = int(X[i][0])
            if h % A == 0:
                count = h // A
            else:
                count = h // A + 1
            ans += count
            dmg = A * count
    #print(ans,dmg)
            for j in range(i+1,N):
                x2 = int(X[j][0])
                h2 = int(X[j][1])
                if  x + (2 * D) < x2:
                    break
                else:
                    X[j][1] = max(0,h2-dmg)
                    #print(X[j])
print(ans)
### BUGGY CODE ###

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

not_in = [0 for i in range(N+1)]
not_in[0] = A[0]
for i in range(1, N+1):
  not_in[i] = not_in[i-1] * 2 + A[i]

if not_in[N] > 2 ** N:
  print(-1)
else:
  in_num = 0
  up = A[N]
  for i in range(N-1,-1,-1):
    in_temp = min(2 ** i - not_in[i], up)
    in_num += in_temp
    up = in_temp + A[i]
  print( in_num + sum(A) )

### FIXED CODE ###

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

not_in = [0 for i in range(N+1)]
not_in[0] = A[0]
for i in range(1, N+1):
  not_in[i] = not_in[i-1] * 2 + A[i]

if not_in[N] > 2 ** N:
  print(-1)
else:
  in_num = 0
  up = A[N]
  for i in range(N-1,-1,-1):
    in_temp = min(2 ** i - not_in[i], up)
    in_num += in_temp
    up = in_temp + A[i]
  print( in_num + sum(A) )
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
*A, = map(int, input().split())
*B, = map(int, input().split())
*C, = map(int, input().split())
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
AB = [A[x]+B[y] for x in range(X) for y in range(Y)]
AB.sort(reverse=True)
AB = AB[:K]
XY = len(AB)
ABC = [AB[xy]+C[z] for xy in range(XY) for z in range(Z)]
ABC.sort(reverse=True)
for k in range(K):
    print(ABC[k])


### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
*A, = sorted(map(int, input().split()), reverse=True)
*B, = sorted(map(int, input().split()), reverse=True)
*C, = sorted(map(int, input().split()), reverse=True)
AB = [A[x] + B[y] for y in range(Y) for x in range(X)]
AB.sort(reverse=True)
AB = AB[:K]
ABC = [AB[x] + C[z] for z in range(Z) for x in range(len(AB))]
ABC.sort(reverse=True)
for k in range(K):
    print(ABC[k])
### BUGGY CODE ###

from sys import stdin
import sys

N = int(input())
A = list(map(int, input().split()))
cnt = 0
for i in range(1, N+1):
    for k in range(i+1, N+1):
        if i != k and A[i-1] < N and A[k-1] < N:
            if abs(i-k) == A[i-1]+A[k-1]:
                cnt += 1
print(cnt)


### FIXED CODE ###

from sys import stdin
import sys

N = int(input())
A = list(map(int, input().split()))
B = {}
C = {}
# B1=[]
# C1=[]
for i in range(len(A)):
    B[i+1-A[i]] = B.get(i+1-A[i], 0)+1
    C[i+1+A[i]] = C.get(i+1+A[i], 0)+1
    # B1.append(i+1-A[i])
    # C1.append(i+1+A[i])
# print(B)
# print(C)
# print(B1)
# print(C1)
cnt1 = 0
for i, v in enumerate(B):
    # print(i, v)
    if v in C.keys():
        # print(v)
        cnt1 += B.get(v)*C.get(v)

# cnt = 0
# for i in range(1, N+1):
#     for k in range(i+1, N+1):
#         if i != k and A[i-1] < N and A[k-1] < N:
#             if abs(i-k) == A[i-1]+A[k-1]:
#                 cnt += 1
print(cnt1)
### BUGGY CODE ###

# https://atcoder.jp/contests/diverta2019/tasks/diverta2019_d

from math import ceil, floor

def divisors(N):
    ans = []
    i = 1
    while i * i <= N:
        if N % i == 0:
            ans.append(i)
            if N // i != i:
                ans.append(N // i)
        i += 1
    ans.sort()
    return ans

N = int(input())
# N = 1000000
fN = divisors(N)
total = 0
for i in range(len(fN) - 1):
    if fN[i + 1] - fN[i] == 1:
        continue
    mp = N // fN[i]
    mpp = N // fN[i + 1]
    # print(fN[i], fN[i + 1], " | [{},{}]".format(mpp, mp))
    for mm in range(mpp, mp):
        for rr in range(1, fN[i] + 1):
            # print(N - rr, floor((N - rr) / mm) == ceil((N - rr) / mm) and rr == mm)
            if floor((N - rr) / mm) == ceil((N - rr) / mm) and rr == mm:
                # print(rr, mm)
                total += (N - rr) // mm
            # print(mm, rr, floor((N - rr) / mm))
print(total)
    
# print()
# total2 = 0
# for m in range(1, N + 1):
#     f1 = floor(N / m)
#     f2 = N % m
#     if f1 == f2:
#         print(m, f1, f2, f1 == f2)
#         total2 += m
# print(total2)

### FIXED CODE ###

# https://atcoder.jp/contests/diverta2019/tasks/diverta2019_d

from math import ceil, floor

def divisors(N):
    ans = []
    i = 1
    while i * i <= N:
        if N % i == 0:
            ans.append(i)
            if N // i != i:
                ans.append(N // i)
        i += 1
    ans.sort()
    return ans

N = int(input())
fN = divisors(N)

total = 0
for m in fN[1:]:
    m -= 1
    if floor(N / m) == N % m:
        total += m
print(total)
### BUGGY CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
max = 0
for i in range(N-K+1):
    temp = sum(p[i:i+K])
    if max < temp:
        max = temp
        maxno = i

exsum = 0

for i in range(K):
    dice = list(range(1, p[i+maxno]+1))
    ex = 0
    p2 = 1/len(dice)

    for x in dice:
        px = p2*x
        ex += px
    exsum += ex
print(exsum)

### FIXED CODE ###

import numpy
N, K = map(int, input().split())
p = numpy.array(list(map(int, input().split())))
max = 0
nowsum = 0
for i in range(N-K+1):
    if i == 0:
        nowsum = numpy.sum(p[i:i+K])
    else:
        nowsum = nowsum - p[i-1] + p[i+K-1]
    if max < nowsum:
        max = nowsum
        maxno = i

exsum = 0

for i in range(K):
    temp = p[i+maxno]
    exsum += (0.5*temp*(temp+1))/temp
print(exsum)
### BUGGY CODE ###

n, q = map(int, input().split())
n = [0]*(n+1)
maxv = winner = 0
for _ in range(q):
    a, v = map(int, input().split())
    n[a] += v
    if v < 0:
        maxv = max(n)
        winner = n.index(maxv)
    elif n[a] > maxv:
            maxv, winner = n[a], a
    elif n[a] == maxv:
            winner = n.index(maxv)
    print(winner, maxv)

### FIXED CODE ###

n, q = map(int, input().split())
n = [0]*(n+1)
maxv = winner = 0
for _ in range(q):
    a, v = map(int, input().split())
    n[a] += v
    if v < 0 and a == winner:
        maxv = max(n)
        winner = n.index(maxv)
    elif n[a] > maxv:
            maxv, winner = n[a], a
    elif n[a] == maxv:
            winner = min(winner, a)
    print(winner, maxv)
### BUGGY CODE ###

# import sys
# import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
#     combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
INF = 1<<29
lINF = 1<<35

def readInt():
    return list(map(int,input().split()))

def main():
    a,b,n = readInt()
    x = min(b-1,n)
    ans = 0
    while x<=n:
        res = a * x // b - a * (x // b)
        ans = max(ans,res)
        x += b-1
    print(ans)
    return

if __name__=='__main__':
    main()

### FIXED CODE ###

# import sys
# import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
#     combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
INF = 1<<29
lINF = 1<<35

def readInt():
    return list(map(int,input().split()))

def main():
    a,b,n = readInt()
    x = min(b-1,n)
    ans = a * x // b - a * (x // b)
    print(ans)
    return

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

from collections import Counter


def enum_divs(n):
    res = []
    for i in range(1, int(n ** .5) + 1):
        if n % i == 0:
            res.append(i)
            if i != n // i:
                res.append(n // i)
    return res


N = int(input())
A = list(map(int, input().split()))
uq_A = [k for k, v in Counter(A).items() if v == 1]
set_A = set(A)
ans = 0
for uq_a in uq_A:
    if any(d in set_A - {uq_a} for d in enum_divs(uq_a)):
        continue
    ans += 1
print(ans)



### FIXED CODE ###

from collections import Counter


LEN = 10 ** 6
is_avl = [0] * (LEN + 1)
N = int(input())
A = Counter(map(int, input().split()))
for a in A:
    is_avl[a] = 1
for a in A:
    for i in range(2 * a, LEN + 1, a):
        is_avl[i] = 0
ans = 0
for a in A:
    if is_avl[a] == 1 and A[a] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

import math
q = int(input())
l = [0 for i in range(q)]
r = [0 for i in range(q)]
for i in range(q):
    l[i], r[i] = list(map(int, input().split()))

def prime(n):
    if n == 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

def like(n):
    if prime(n):
        if prime((n+1)/2):
            return True
    return False

for i in range(q):
    count = 0
    for num in range(l[i], r[i]+1, 2):
        if like(num):
            count += 1
    print (count)


### FIXED CODE ###

f = [False for i in range(100001)]
c = [0 for i in range(100001)]

for i in range(2, 100001):
    if not f[i]:
        for j in range(2*i, 100001, i):
            f[j] = True
for i in range(3, 100001, 2):
    if not f[i] and not f[int((i+1)/2)]:
        c[i] += 1
for i in range(3, 100001):
    c[i] += c[i-1]
    
n = int(input())
while n:
    l, r = list(map(int, input().split()))
    print (c[r]-c[l-1])
    n -= 1
### BUGGY CODE ###

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
import numpy as np
dots = np.asarray(XY[:])

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)


### FIXED CODE ###

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
dots = XY[:]

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)
### BUGGY CODE ###

s=input()
        
ngram=[]
for i in range(4,len(s)):
    for j in range(len(s)-i+1):
         ngram.append(s[j:j+i])

ans=0
for i in range(len(ngram)):
    if int(ngram[i])%2019==0:
        ans+=1
print(ans)

### FIXED CODE ###

s=input()
l=len(s)
amari=[0]*2019
amari[0]=1

d=0
digi=1

for c in s[::-1]:
    d=(int(c)*digi + d)%2019
    amari[d]+=1
    digi=(digi*10)%2019

ans=0
for i in amari:
    ans+=i*(i-1)//2
print(ans)
### BUGGY CODE ###

N,W=map(int,input().split())
weights,profits = [0]*N, [0]*N
def solve_knapsack(capacity):
    # basic checks
    n = len(profits)
 
    dp = [0 for x in range(capacity+1)]
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit

    for i in range(0, n):
        weights[i],profits[i] = map(int,input().split())
        for c in range(capacity, weights[i]-1, -1):
            if weights[i] <= c:
                dp[c] = max(profits[i] + dp[c - weights[i]], dp[c])
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

### FIXED CODE ###

def main():
  n, w = [int(e) for e in input().split()]
  t = [-1 for i in range(w + 1)]
  t[w] = 0
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(nw, w + 1):
      if t[i] == -1:
        continue
      if t[i - nw] < t[i] + nv:
        t[i - nw] = t[i] + nv
  print(max(t))
main()
### BUGGY CODE ###

import bisect
x = int(input())
xx = x//2
a = []
s = 0
for i in range(xx):
	s += i+1
	a.append(s)
	#print (s)

r = bisect.bisect_left(a, x)
print (r+1)


### FIXED CODE ###

import bisect
x = int(input())
xx = x//2
a = []
s = 0
for i in range(x+1):
	if (i * (i+1))/2 >= x:
		print(i)
		exit()
### BUGGY CODE ###

def LIST():
    return list(map(int, input().split()))

n, m = map(int, input().split())

l = list()
la = list()
ln = list()
for i in range(m):
    a, b = map(int, input().split())
    l.append([a, b])
    if 1 in [a, b]:
        la.append(a*b)
    if n in [a, b]:
        ln.append(a*b/n)

for i in la:
    if i in ln:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

### FIXED CODE ###

n, m = map(int, input().split())

l = list()
la = [0] * (n+1)
ln = [0] * (n+1)

for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        la[b] = 1
    elif b == 1:
        la[a] = 1
    if a == n:
        ln[b] = 1
    elif b == n:
        ln[a] = 1

for i in range(n+1):
    if la[i]*ln[i] == 1:
        print("POSSIBLE") 
        exit()

print("IMPOSSIBLE")