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

N=int(input())
L=list(map(int,input().split()))
R=sorted(L)[::-1]

count=0
for i in range(0,N-2):
  for j in range(i+1,N-1):
    for k in range(j+1,N):
      if R[k]+R[j] > R[i]:
        count+= 1
print(count)
      

### FIXED CODE ###

import bisect
N=int(input())
L=list(map(int,input().split()))
R=sorted(L)
point=0
for i in range(N-2):
  for j in range(i+1,N-1):
    p = bisect.bisect_right(R,R[i]+R[j]-1,j+1,N)
    point+=p-(j+1)
    
print(point)
### BUGGY CODE ###


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

adj = [list() for _ in range(N)]
for m in range(M):
    x,y,z = map(int,input().split())
    x,y = x-1,y-1
    adj[x].append(y)
    adj[y].append(x)

cnt = 0
unvisited = set(range(N))
while unvisited:
    u0 = next(iter(unvisited))
    unvisited.discard(u0)
    stack = [u0]
    while stack:
        u = stack.pop()
        for v in adj[u]:
            if v in unvisited:
                unvisited.discard(v)
                stack.append(v)
    cnt += 1

print(cnt)

### FIXED CODE ###

import scipy.sparse as sp
import scipy.sparse.csgraph as gp


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

adj = sp.dok_matrix((N,N), dtype=bool)
def it():
    for m in range(M):
        x,y,z = map(int,input().split())
        x,y = x-1,y-1
        adj[x,y] = True
        adj[y,x] = True
it()

res,_ = gp.connected_components(adj, directed=False)
print(res)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    NT=1
    NA=1
    for i in range(N):
        T,A=MI()
        tempT=T
        tempA=A
        while tempT<NT or tempA<NA:
            tempT+=T
            tempA+=A
        NT=tempT
        NA=tempA
    print(NT+NA)
            

main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    NT=1
    NA=1
    for i in range(N):
        T,A=MI()
        xt=(NT+T-1)//T
        xa=(NA+A-1)//A
        x=max(xt,xa)
        NT=T*x
        NA=A*x
    print(NT+NA)
            

main()
### BUGGY CODE ###

n = int(input())
a = []
for _ in range(n):
  a.append(int(input()))

for i in range(n):
  print(max(a[:i] + a[i+1:]))

### FIXED CODE ###

n = int(input())
a = []
for _ in range(n):
  a.append(int(input()))

m = max(a)
s = sorted(a)

for i in range(n):
  if m is a[i]:
    print(s[-2])
  else:
    print(m)
### BUGGY CODE ###

s = input()
q = int(input())
inv = False
for i in range(q):
    a = list(input().split())
    if a[0] == '1':
        inv = not inv
    if a[0] == '2':
        if (a[1] == '1')^inv:
            s = a[2] + s
        else:
            s += a[2]
if inv:
    print(s[::-1])
else:
    print(s)

### FIXED CODE ###

s = str(input())
q = int(input())
inv = False
head = ''
tail = ''

for i in range(q):
    a = input()
    if a == '1':
        inv = not inv
        continue
    a = a.split()
    if (a[1] == '1')^inv:
        head = a[2] + head
    else:
        tail += a[2]
s = head + s + tail
if inv:
    print(s[::-1])
else:
    print(s)
### BUGGY CODE ###

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

if n % k == 0:
    print(0)
    exit()

if k % n == 0:
    print(n)
    exit()

while(True):
    new = abs(n-k)
    if new < n:
        n = new
        continue
    else:
        break

print(n)

### FIXED CODE ###

n, k = list(map(int, input().split()))
if n < k:
    print(min(n, k-n))
else:
    print(min(n%k, k-(n%k)))
### BUGGY CODE ###

import math
from fractions import Fraction
n=int(input())
x=list(map(int,input().split()))
ans=0
for i in range(n):
    ans=(ans+(x[-1]-x[i])*(Fraction(1,i+1)))%(10**9+7)

ans=ans*math.factorial(n-1)%(10**9+7)
print(ans)


### FIXED CODE ###

import math
n=int(input())
a=list(map(int,input().split()))
ans=math.factorial(n-1)%(10**9+7)

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

c=0
for i in range(1,n):
    c+=(a[-1]-a[i-1])*modinv(i, mod=10**9+7)
print(ans*c%(10**9+7))
### BUGGY CODE ###

# from collections import deque
def main():
    N = int(input())
    S = input()

    # d = deque()
    max_len = N // 2
    ans = 0

    for L in reversed(range(1, max_len + 1)):
        found = False
        for i in range(N-L):
            if S[i:i+L] in S[i+L:]:
                found = True
                break
        if found:
            ans = L
            break
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###


def z_algorithm(S):
    # 文字列が与えられた時、各 i について
    # 「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録した配列 A を
    #  O(|S|) で構築するアルゴリズム
    # S: aaabaaaab
    # A: 921034210
    # 例えば、A[5] = 4だが、これは、S[0:4] == S[5:5+4] 
    # (Sの0文字目からと5文字目からは、4文字一致している(aaab)) ことを意味する。

    lenS = len(S)
    A = [0] * lenS
    i = 1; j = 0
    A[0] = lenS
    # i: 調査開始点
    # iを1文字目からlen(S)-1文字目まで左から順に動かしていく
    while i < lenS:
        # j: 何文字目まで一致するか(iからの距離)
        # 一致しなくなるまでjを左から右へ動かしていく
        while i + j < lenS and S[j] == S[i + j]:
            j += 1
        # 1文字も一致しない場合は調査開始点を一つ右にずらす
        if j == 0:
            i += 1
            continue

        A[i] = j

        # 例）S: momomosumomomomo
        # A[1] = 0, A[2] = 4 (A[0:4] == A[2:2+4] = "momo")

        # i=2の調査が終わった段階で、
        # S[3] = S[2 + 1] = S[1] = "o" 
        # で、A[3] = A[1] = 0（Sの1文字目からと3文字目からは一致しない）
        # のは明らかなので、i = 3の結果はi = 1の結果を流用して0とする。
        # つまり、A[3] = A[2 + 1] = A[1] = 0

        # 今回、i + j 文字目まで、一致するか調べたので、
        # A[i + 1] ~ A[i + j - 1] までの間で、計算結果を流用できるところは流用する
        # j <= k + A[k] となるようなkの場合、
        # j文字目以降は今回調べてないので一致するか本当に分からないので、流用をやめる
        # 今回の場合、
        # k = 1: 1 + A[1] = 1 + 0 = 1 < j = 4 なので、流用できる
        # k = 2: 2 + A[2] = 2 + 4 = 6 > j = 4 なので、流用できない
        # つなり、k=2となった瞬間、流用をせずにループを抜ける。
        k = 1
        while k + A[k] < j and i + k < lenS:
            A[i + k] = A[k]
            k += 1
        # 今回 1回 (=k-1回) 流用できた、つまり A[3] = A[2(=i) + 2(=k) - 1] まで確定したので、
        # 次は A[4] = A[i + k] から調べる
        i += k

        # また、k = 2 のとき、k + A[k] >= j となって流用を打ち切られたということは、
        # k + A[i + k] >= j  => A[i + k] >= j - k
        # A[4] は少なくとも j - k = 4 - 2 = 2 以上となることが確定する。
        # つまり、S[4:]とSは、少なくとも最初の2文字 (j-k文字) は一致する。
        # よって、A[4]を調べるときは、j=2から調査を開始すればよい。
        # （つまり、S[6]とS[4:][2]が一致しているか調べるところから始める）

        #             0123456
        # S         = momomosumomomomo
        # S[2:]     =   momosumomomomo   <- 5文字目が違う
        # S[2:][2:] =     mosumomomomo   <- 3文字目が違う
        # S[4:]     =     mosumomomomo   <- 3文字目が違う
        # S[4:][2:] =       sumomomomo   <- 1文字目が違う
        j -= k
    return A

def main():
    N = int(input())
    S = input()

    ans = 0

    # Z-algorithm で、最長共通接頭辞の長さを調べる。
    # Z-algorithm は、「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録するので、
    # S[1]以降の部分文字列同士の長さは、
    # S=S[i:]としてiをずらしながら最長共通接頭辞を調べることで分かる

    for i in range(N-1):
        A = z_algorithm(S[i:])
        # print(A)
        # 例えばS = ababa のとき、
        # A = [5, 0, 3, 0, 1] となる。
        # A[2] = 3 だが、範囲が被ってしまっているので、
        # A[i] > i の場合、一致する文字数はiまでにしておく。
        ans = max(ans, max([min(i, a) for i, a in enumerate(A)]))

    print(ans)

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

A, B, N = map(int,input().split())
bst = -10000000000

for i in range(N+1):
    if((A*i)//B - A*(i//B) > bst):
        bst = (A*i)//B - A*(i//B)

print(bst)

### FIXED CODE ###

A,B,N = map(int, input().split())
p = min(N,B)

if p%B == 0:
    print(int(A*(p-1)//B))
else :
    print(int(A*(p)//B))
### BUGGY CODE ###

import sys
import bisect
n = int(input())
l_ls = [int(i) for i in sys.stdin.readline().split()]
l_ls.sort()
l_dict = { i : j for i, j in enumerate(l_ls)}
_sum_ls = []
cnt = 0
for i in range(1,n-1):
    base = l_dict[i]
    next_base = l_dict[i+1]
    edagiri = -1
    for l in l_ls[:i][::-1]:
        if l + base > next_base:
            bisect.insort_left(_sum_ls, l + base)
    for k, _sum in enumerate(_sum_ls[::-1]):
        if next_base < _sum:
            cnt += 1
        else:
            edagiri = k
            break
    if edagiri > 0:
        _sum_ls = _sum_ls[-edagiri:]
print(cnt)

### FIXED CODE ###

import sys
from itertools import combinations
import bisect
import math
n = int(input())
l_ls = [int(i) for i in sys.stdin.readline().split()]
l_ls.sort()
cnt = 0
for a, b in combinations(l_ls, 2):
    _sum = a + b
    ind = bisect.bisect_left(l_ls, _sum)
    cnt += n - ind
print(int(math.factorial(n) // math.factorial(3) // math.factorial(n-3)) - cnt)
### BUGGY CODE ###

k = int(input())

count = 0
check = 1

def lun(n):
    if len(str(n)) ==1:
        return True
    else:
        m = str(check)
        keta = len(m)
        for i in range(1, keta):
            if int(m[i]) != int(m[i-1]) and int(m[i]) != int(m[i-1]) +1 and int(m[i]) != int(m[i-1]) -1:
                return False
        return True

while count < k:
    if lun(check):
        count +=1
    check += 1
print(check-1)

### FIXED CODE ###

from collections import deque

k = int(input())

count = 1
d= deque([1,2,3,4,5,6,7,8,9])
#ls = []
while count <= k:
    v = d.popleft()
    count += 1
    last = str(v)[-1]
    if last == '0':
        d.append(int(str(v) + '0'))
        d.append(int(str(v)+'1'))
    elif last == '9':
        d.append(int(str(v) + '8'))
        d.append(int(str(v) + '9'))
    else:
        d.append(int(str(v) + str(int(last) - 1)))
        d.append(int(str(v) + str(int(last) )))
        d.append(int(str(v) + str(int(last) + 1)))
    #ls.append(v)

#print(ls)
print(v)
### BUGGY CODE ###

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

res = 1
i = 1

if N == 1:
    print(P)
    exit()

while i ** N <= P:
    if P % i ** N == 0:
        res = i

    i += 1

print(res)


### FIXED CODE ###

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

if N == 1:
    print(P)
    exit()

div = 2
res = 1
R = P

while div * div <= R and div <= P:
    cnt = 0
    while P % div == 0:
        P /= div
        cnt += 1

        if cnt == N:
            res *= div
            cnt = 0
    div += 1

print(res)
### BUGGY CODE ###

a,b,c,d = map(int,input().split(" "))
ans = 0
for i in range(a,b+1):
  if i%c!=0 and i%d!=0:
    ans+=1
    
print(ans)    

### FIXED CODE ###

a,b,c,d = map(int,input().split(" "))
ans = 0
from fractions import gcd
def lcm(x, y):
  return (x * y) // gcd(x, y)
a -= 1
f = lcm(c,d)
ans = (b - a) - ((b//c - a//c) + (b//d - a//d) - (b//f - a//f))

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

import itertools

def comb(n, r):
    return len(list(itertools.combinations(range(n), r)))

def get_runlength(s): # ex) s = 'RRLLLLRLRLRLRR'
    ret = []
    count = 1
    for i in range(len(s)):
        if i == len(s) - 1:
            ret.append((s[i], count))
            continue
        if s[i] == s[i + 1]:
            count += 1
        else:
            ret.append((s[i], count))
            count = 1
    return ret

n = int(input())
s = []
for i in range(n):
    sin = input()
    sin = list(sin)
    sin.sort()
    sin = ''.join(sin)
    s.append(sin)

count = 0
ss = set(s)
for w in ss:
    n = s.count(w)
    count += n * (n - 1) / 2
count = int(count)
print(count)


### FIXED CODE ###

import itertools

def comb(n, r):
    return len(list(itertools.combinations(range(n), r)))

def get_runlength(s): # ex) s = 'RRLLLLRLRLRLRR'
    ret = []
    count = 1
    for i in range(len(s)):
        if i == len(s) - 1:
            ret.append((s[i], count))
            continue
        if s[i] == s[i + 1]:
            count += 1
        else:
            ret.append((s[i], count))
            count = 1
    return ret

n = int(input())
dic = {}
for i in range(n):
    sin = input()
    sin = list(sin)
    sin.sort()
    sin = ''.join(sin)
    try:
        dic[sin] += 1
    except:
        dic[sin] = 1

count = 0
for v in dic.values():
    count += v * (v - 1) / 2
count = int(count)
print(count)
### BUGGY CODE ###

import math

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

def C(N,P):
    if N == 1: return P
    b=int(math.log2(N))
    a=int(P**(1/b))+2

    res=1
    for i in range(2,a):
        c=i**N
        if c > P : break
        if P % c == 0 : res = i

    return res

print(C(n,p))

### FIXED CODE ###

n,p = list(map(int,input().split())) 
i = a = o = 1
m = round(p**(1/n))
for i in range(m,0,-1):
    a = i**n
    if p%a==0:
        print(i)
        exit()
### BUGGY CODE ###

import math
import copy

n = int(input())
l = list(map(int, input().split()))
d = {}
s_sum = {}
s = list(set(l))
m = 0
for i in range(len(s)):
    d[s[i]] = l.count(s[i])
for v in d.values():
    if v > 1:
        m += math.factorial(v) // math.factorial(v -
                                                 2) // math.factorial(2)
for i in range(len(l)):
    if not l[i] in d:
        print(m)
    elif l[i] in s_sum:
        print(s_sum[l[i]])
    else:
        ans = 0
        e = copy.deepcopy(d)
        e[l[i]] -= 1
        for v in e.values():
            if v > 1:
                ans += math.factorial(v) // math.factorial(v -
                                                           2) // math.factorial(2)
        s_sum[l[i]] = ans
        print(ans)

### FIXED CODE ###

import collections

def count_defaultdict(it):
    counter = collections.defaultdict(int)
    for x in it:
        counter[x] += 1
    return dict(counter)

_ = int(input())
l = list(map(int, input().split()))
all_sum = 0
count = count_defaultdict(l)
for _, v in count.items():
    all_sum += v * (v - 1) // 2
for i in range(len(l)):
    if count[l[i]] > 1:
        v = count[l[i]]
        print(all_sum - v * (v-1) // 2 + (v-1) * (v-2)//2)
    else:
        print(all_sum)
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*n
for i in range(1,n):
	dp[i]=dp[i-1]+abs(h[i]-h[i-1])
	for j in range(2,min(k,i)+1):
		dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
print(dp[n-1])

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*n
for i in range(1,n):
	dp[i]=dp[i-1]+abs(h[i]-h[i-1])
	for j in range(2,min(k,i)+1):
		dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
print(dp[n-1])
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
for i in range(N-1):
  for j in range(i+1,N):
    S1 = S[i:j]
    S2 = S[j:]
    tmp = 0
    M = min(j-i,N-j)
    for k in range(M):
      if S1[k] == S2[k]:
        tmp += 1
      else:
        break
    ans = max(tmp,ans)
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
dp = [[0]*(N+1) for i in range(N+1)]
ans = 0
for i in range(N-1,-1,-1):
  for j in range(i,-1,-1):
    if S[i] == S[j]:
      dp[i][j] = dp[i+1][j+1] + 1
      tmp = min(dp[i][j],i-j)
      ans = max(ans,tmp)
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
s = [0]*(n+1)

for i in range(n):
	s[i+1] = a.count(i+1)

for i in range(n):
  	print(s[i+1])

### FIXED CODE ###

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

c = [0]*n
for i in a:
	c[i-1] += 1

for i in range(n):
	print(c[i])
### BUGGY CODE ###

n,k,q = map(int,input().split())
a = [0] * q
for i in range(q):
    a[i] = int(input())

point = [k] * n
for i in range(q):
    for j in range(n):
        if a[i]-1 != j:
            point[j] -= 1
for i in range(n):
    if(point[i] > 0):
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

N,K,Q = map(int, input().split())
List = [int(input()) for i in range(Q)]
PList=[K-Q]*N
for i in range(0,Q):
    PList[(List[i])-1]+=1
for j in range(0,N):
    if PList[j]>0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

#!/usr/bin/env python3

def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


def main():
    n = int(input())
    ans = 0
    for c in range(1, n):
        d = n - c
        ans += len(make_divisors(d))
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    n = int(input())
    li = [1] * (n + 1)
    for i in range(2, n + 1):
        j = 1
        while i * j <= n:
            li[i * j] += 1
            j += 1

    print(sum(li[1:n]))


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

s = input()

for _ in range(int(len(s)/2)):
    s = s.replace('ST', '')
print(len(s))



### FIXED CODE ###

s = list(input())
l = []
for i in range(len(s)):
    if s[i] == 'S':
        l.append('S')
    elif not l:
        l.append('T')
    elif l[-1] == 'T':
        l.append('T')
    else:
        l.pop()
print(len(l))
### BUGGY CODE ###

# AGC011 A Airport Bus
import bisect

n, c, k = map(int, input().split())
t_list = [int(input()) for _ in range(n)]

t_list.sort()
ans = 0

while len(t_list) > 0:
    _tmp = t_list[0] + k
    _idx = bisect.bisect_right(t_list, _tmp)
    if c <= _idx + 1:
        t_list = t_list[c:]
    else:
        t_list = t_list[_idx:]
    ans += 1

print(ans)

### FIXED CODE ###

# AGC011 A Airport Bus
import bisect
from collections import deque

n, c, k = map(int, input().split())
t_list = [int(input()) for _ in range(n)]

t_list.sort()
t_list = deque(t_list)
ans = 0

while len(t_list) > 0:
    _tmp = t_list.popleft() + k
    _idx = bisect.bisect_right(t_list, _tmp)
    if c-1 <= _idx:
        for _ in range(c-1):
            t_list.popleft()
    else:
        for _ in range(_idx):
            t_list.popleft()
    ans += 1

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

# N = int(input())
import sys
from functools import lru_cache

sys.setrecursionlimit(10000000)


N, K = [int(i) for i in input().split()]
h = [0] + [int(i) for i in input().split()]


@lru_cache(maxsize=None)
def solve(n):
    if n <= 1:
        return 0
    min_cost = 10**9
    for i in range(1, K+1):
        if n > i:
            min_cost = min(min_cost, solve(n-i) + abs(h[n] - h[n-i]))
    return min_cost

print(solve(N))




### FIXED CODE ###

# N = int(input())


N, K = [int(i) for i in input().split()]
h = [0] + [int(i) for i in input().split()]
INF = 10 ** 9
dp = [INF for i in range(N+1)]
dp[1] = 0
for j in range(1, N+1):
    for i in range(1, K+1):
        if j > i:
            dp[j] = min(dp[j], dp[j-i] + abs(h[j] - h[j-i]))

print(dp[N])
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy
from operator import itemgetter

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, M = na()
MAX = M // N + 1
ans = 1
for i in range(1, MAX):
    res = M - i * N
    if res % i == 0:
        ans = max(ans, i)
print(ans)

### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy
from operator import itemgetter

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, M = na()
MAX = M // N
ans = 1

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

if M % N == 0:
    print(M // N)
else:
    tmp = make_divisors(M)
    print(tmp[max(bisect.bisect_left(tmp, MAX) - 1, 0)])
### BUGGY CODE ###

n,y=map(int, input().split())
nums=[i for i in range(n+1)]
combi_list = []
for i in range(n+1):
    for j in range(n+1-i):
        combi = [0 for i in range(3)]
        combi[0] = i
        combi[1] = j
        combi[2] = n - i - j
        combi_list.append(combi)
Ans_list = []
judge = 0
for i in range(len(combi_list)):
    price = combi_list[i][0] * 10000 + combi_list[i][1] * 5000 + combi_list[i][2] * 1000
    if y == price:
        judge += 1
        Ans_list.append(combi_list[i][0])
        Ans_list.append(combi_list[i][1])
        Ans_list.append(combi_list[i][2])
        break

if judge>=1:
    print(str(Ans_list[0])+ " " + str(Ans_list[1]) + " " + str(Ans_list[2]))
else:
    print("-1 -1 -1")

### FIXED CODE ###

n,y=map(int, input().split())
nums=[i for i in range(n+1)]
judge = 0
for i in range(n+1):
    for j in range(n+1-i):
        price = i * 10000 + j * 5000 + (n-i-j) * 1000
        if y == price:
            judge += 1
            print(str(i) + " " + str(j) + " " + str(n-i-j))
            break
    if judge == 1:
        break
if judge == 0:
    print("-1 -1 -1")
### BUGGY CODE ###

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

n = int(input())
game = {}

for i in range(1, n+1):
    game[i] = deque((map(int, input().split())))

count = 0
final = n*(n-1)//2
for day in range(1, 1000000):
    finish = [0]*(n+1)
    possible = False
    for me in range(1, n+1):
        if finish[me] == 1 or game[me] == deque([]):
            continue

        you = game[me][0]
        if finish[you] == 1 or game[you] == deque([]):
            continue
        else:
            if game[you][0] == me:
                finish[game[you].popleft()] = 1
                finish[game[me].popleft()] = 1
                possible = True
                count += 1
            else:
                continue

    if not possible:
        print(-1)
        exit()

    if count == final:
        print(day)
        exit()


### FIXED CODE ###

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

n = int(input())
game = {}

for i in range(1, n+1):
    game[i] = deque((map(int, input().split())))

count = 0
final = n*(n-1)//2
done = []

finish = [0] * (n + 1)
for me in range(1, n + 1):
    if finish[me] == 1 or game[me] == deque([]):
        continue

    you = game[me][0]
    if finish[you] == 1:
        continue
    else:
        if game[you][0] == me:
            done.append(you)
            done.append(me)
            finish[game[you].popleft()] = 1
            finish[game[me].popleft()] = 1
            possible = True
            count += 1
        else:
            continue

for day in range(2, 1000000):
    finish = [0]*(n+1)
    possible = False
    new_done = []
    for me in done:
        if finish[me] == 1 or game[me] == deque([]):
            continue

        you = game[me][0]
        if finish[you] == 1:
            continue
        else:
            if game[you][0] == me:
                finish[game[you].popleft()] = 1
                finish[game[me].popleft()] = 1
                new_done.append(me)
                new_done.append(you)
                possible = True
                count += 1
            else:
                continue
    done = new_done
    if not possible:
        print(-1)
        exit()

    if count == final:
        print(day)
        exit()
### BUGGY CODE ###

def search(S):
    cnt = 0
    N = len(S)
    for i in range(N+1):
        for j in range(i+1, N+1):
            num = S[i:j]
            if int(num)%2019==0:
                cnt += 1
            
    return cnt 

if __name__ == "__main__":
    S = input()
    cnt = search(S)
    print(cnt)

### FIXED CODE ###

S = list(map(int, list(input())))[::-1]
N = len(S)
CNT = [0]*2019
CNT[0] = 1
num = 0
d = 0
for i in range(N):
    num += S[i]*pow(10, d, 2019)
    num %= 2019
    CNT[num] += 1
    d += 1
ans = 0 
for cnt in CNT:
    ans += (cnt*(cnt - 1)) // 2
print(ans)
### BUGGY CODE ###

n=int(input())

import math
result=0
for i in range(1,n+1):
    for ii in range(1,n+1):
        for iii in range(1,n+1):
            temp=math.gcd(i,ii)
            result+=math.gcd(temp,iii)
print(result)

### FIXED CODE ###

n=int(input())

import math
result=0
for i in range(1,n+1):
    for ii in range(1,n+1):
        for iii in range(1,n+1):
            temp=math.gcd(i,ii)
            result+=math.gcd(temp,iii)
print(result)