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

# coding: utf-8

#約数列挙
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

#main
X = int(input())
F = make_divisors(X)
#intのみのlistは、直接.join()できない
S = [int(x) for x in F]

if X == 1:
    S.append(2)

for i in range(len(S)):
    tmp = S[i]
    for A in range(S[i+1]):
        B = A - tmp
        if A**5 - B**5 == X:
            print(str(A) + ' ' + str(B))
            break
    else:
        continue
    break

### FIXED CODE ###

# coding: utf-8

#約数列挙
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

#main
X = int(input())
F = make_divisors(X)
#intのみのlistは、直接.join()できない
S = [int(x) for x in F]

for i in range(len(S)):
    tmp = S[i]
    for A in range(-1000, 1001):
        B = A - tmp
        if A**5 - B**5 == X:
            print(str(A) + ' ' + str(B))
            break
    else:
        continue
    break
### BUGGY CODE ###

def solve():
    N = int(input())
    s_lst = [input() for i in range(N)]
    a_lst = []
    s_dict = {}
    for w in s_lst:
        if not w in s_dict.keys():
            s_dict[w] = 1
        else:
            s_dict[w] += 1
    s_max = max(list(s_dict.values()))
    for w in s_lst:
        if s_dict[w] == s_max and not w in a_lst:
            a_lst.append(w)
    a_lst.sort()
    for i in range(len(a_lst)):
        print(a_lst[i])

if __name__ == '__main__':
    solve()


### FIXED CODE ###

def solve():
    N = int(input())
    s_lst = [input() for i in range(N)]
    s_lst.sort()
    a_lst = []
    s_dict = {}
    for w in s_lst:
        if not w in s_dict.keys():
            s_dict[w] = 1
        else:
            s_dict[w] += 1
    s_max = max(list(s_dict.values()))
    i = 0
    while i < len(s_lst):
        w = s_lst[i]
        if s_dict[w] == s_max:
            a_lst.append(w)
        i += s_dict[w]
    for i in range(len(a_lst)):
        print(a_lst[i])

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

N, M = map(int, input().split())
H = list(map(int, input().split()))
S = [[0] * N for _ in range(N)]

for _ in range(M):
    A, B = map(int, input().split())
    S[A-1][B-1] = H[B-1]
    S[B-1][A-1] = H[A-1]
ans = 0
for i in range(N):
    if H[i]>max(S[i]):
        ans+=1
print(ans)

### FIXED CODE ###

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

S = [1]*N
for _ in range(M):
    A, B = map(int, input().split())
    if H[A-1]>H[B-1]:
        S[B-1]=0
    elif  H[A-1]<H[B-1]:
        S[A-1]=0
    else:
        S[B-1]=0
        S[A-1]=0
print(sum(S))
### BUGGY CODE ###

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

for i in range(N):
    m=max(A)
    H-=m
    if(H <= 0):
        print('Yes')
        sys.exit()
    A.remove(m)
print('No')


### FIXED CODE ###

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

sortA=sorted(A)

for i in range(N):
    H-=sortA.pop()
    if(H <= 0):
        print('Yes')
        sys.exit()
print('No')
### BUGGY CODE ###

for _ in range(int(input())):
    X = input()
    Y = input()
    dp = [[0] * (len(Y)+1) for x in range(len(X)+1)]
    for x in range(1, len(X) + 1):
        pre = dp[x-1]
        tmp = dp[x]
        for y in range(1, len(Y) + 1):
            if X[x-1] == Y[y-1]:
                tmp[y] = pre[y-1] + 1
            else:
                tmp[y] = max(tmp[y-1], pre[y])
    print(dp[-1][-1])


### FIXED CODE ###

def ser(X, Y):
    dp = [[0] * (len(Y)+1) for x in range(len(X)+1)]
    for i, x in enumerate(X, 1):
        tmp = dp[i]
        pre = dp[i-1]
        for j, y in enumerate(Y, 1):
            if x == y:
                tmp[j] = pre[j-1] + 1
            elif pre[j] < tmp[j-1]:
                tmp[j] = tmp[j-1]
            else:
                tmp[j] = pre[j]
    return(dp[-1][-1])

for _ in range(int(input())):
    X, Y = input(), input()
    print(ser(X, Y))
### BUGGY CODE ###

from itertools import combinations
n = int(input())
s, h = [], []
p = 0
for _ in range(n):
	s.append(list(map(int, input().split())))

for i in range(len(s)):
	for j in range(i+1, n):
		if s[i][0]*s[j][0] + s[i][1]*s[j][1] == 0: h.append((i, j))

def comb(li):
	count = 0
	if len(li[0]) == 1: return len(li)
	for l in li:
		com = set(list(combinations(l, 2)))
		if len(com & set(h)) == 0:
			count += 1
	return count

for i in range(1, n+1):
	l = list(combinations(range(0, n), i))
	p += comb(l)
print(p % 1000000007)

### FIXED CODE ###

import numpy as np
dic = dict()
mod = 10 ** 9 + 7
p = 0

def reg(a, b):
	if a < 0 or (a == 0 and b < 0):
		a, b = -a, -b
	if b > 0:
		return 0, a, b
	else:
		return 1, -b, a

n = int(input())
for _ in range(n):
	a, b = map(int, input().split())
	if a == 0 and b == 0:
		p += 1
		continue
	ab = np.gcd(a, b)
	a, b = a//ab, b//ab
	idx, a, b = reg(a, b)
	k = (a, b)
	if k not in dic.keys():
		dic[k] = [0, 0]
	dic[k][idx] += 1

not_p = 1
for k in dic.keys():
	a, b = k
	pp, pm = dic[k]
	not_p *= (pow(2, pp, mod) + pow(2, pm, mod) - 1) % mod
	not_p %= mod

print((p + not_p -1) % mod)
### BUGGY CODE ###

#  --*-coding:utf-8-*--


def dsMakeSet(ds, x):
    ds[x] = x


def dsFind(ds, x):
    if ds[x] == x:
        return x

    while ds[x] != x:
        x = ds[x]

    ds[x] = x
    return x


def dsUnion(ds, x, y):
    xRoot = dsFind(ds, x)
    yRoot = dsFind(ds, y)
    
    if xRoot != yRoot:
        ds[yRoot] = xRoot
        return True

    return False


def main():
    N, M = map(int, input().split())
    ds = {}

    for i in range(N):
        dsMakeSet(ds, i+1)

    n = 0
    for i in range(M):
        X,Y,Z = map(int, input().split())
        if dsUnion(ds, X, Y):
            n += 1
        
    print(N - n)
        

if __name__ == '__main__':
    main()


### FIXED CODE ###

#  --*-coding:utf-8-*--


def dsMakeSet(ds, x):
    ds[x] = x


def dsFind(ds, x):
    if ds[x] == x:
        return x

    x0 = x
    while ds[x] != x:
        x = ds[x]

    ds[x0] = x
    return x


def dsUnion(ds, x, y):
    xRoot = dsFind(ds, x)
    yRoot = dsFind(ds, y)
    
    if xRoot != yRoot:
        ds[yRoot] = xRoot
        return True

    return False


def main():
    N, M = map(int, input().split())
    ds = {}

    for i in range(N):
        dsMakeSet(ds, i+1)

    n = 0
    for i in range(M):
        X,Y,Z = map(int, input().split())
        if dsUnion(ds, X, Y):
            n += 1
        
    print(N - n)
        

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

from collections import Counter

N = int(input())

s = [Counter(input()) for _ in range(N)]
  
cnt = 0
for i in range(N):
    for j in range(i + 1, N):
      if s[i] == s[j]:
        cnt += 1
        
print(cnt)

### FIXED CODE ###

import math
from collections import Counter

N = int(input())

s = []
for _ in range(N):
  s.append(''.join(sorted(str(input()))))
  
c = Counter(s) 

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

cnt = 0  
for i in c.values():
  if i >= 2:
    cnt += combinations_count(i, 2)

print(cnt)
### BUGGY CODE ###

n, q = [int(i) for i in input().split()]
s = input()
l =[]
r =[]
for i in range(q):
    l1, r1 = [int(i) for i in input().split()]
    l.append(l1)
    r.append(r1)

memo = []
for i in range(len(s)-1):
    if s[i]=="A" and s[i+1]=="C":
        memo.append(i)

#print(memo)

for i in range(q):
    cnt = 0
    for j in memo:
        if l[i] <= j+1 and j+2 <= r[i]:
            cnt+=1
    print(cnt)


### FIXED CODE ###

n, q = [int(i) for i in input().split()]
s = input()
l =[]
r =[]
for i in range(q):
    l1, r1 = [int(i) for i in input().split()]
    l.append(l1)
    r.append(r1)

Sum = [0]
for i in range(len(s)):
    if s[i-1]=="A" and s[i]=="C":
        Sum.append(Sum[i]+1)
    else:
        Sum.append(Sum[i])

#print(Sum)
for i in range(q):
    print(Sum[r[i]]-Sum[l[i]])
### BUGGY CODE ###

s = input()
mod = 10 ** 9 + 7
# for _ in range(len(s) + 1):
#     l = []
#     for __ in range(13):
#         l.append(0)
#     dp.append(l)
dp = [[0 for _ in range(13)] for __ in range(len(s) + 1)]
dp[0][0] = 1
for i, si in enumerate(s[::-1]):
    if si == '?':
        for n in range(10):
            a = n * (10 ** i) % 13
            for j in range(13):
                dp[i+1][(j + a) % 13] = (dp[i+1][(j + a) % 13] + dp[i][j]) % mod
    else:
        a = int(si) * (10 ** i) % 13
        for j in range(13):
            dp[i+1][(j + a) % 13] = (dp[i+1][(j + a) % 13] + dp[i][j]) % mod
print(dp[len(s)][5])


### FIXED CODE ###

s = input()
mod = 10 ** 9 + 7
memo = [0] * (len(s) + 1)
memo[0] = 1
dp = [[0 for _ in range(13)] for __ in range(len(s) + 1)]
dp[0][0] = 1
for i, si in enumerate(s[::-1]):
    memo[i+1] = memo[i] * 10 % 13
    if si == '?':
        for n in range(10):
            a = n * memo[i]
            for j in range(13):
                dp[i+1][(j + a) % 13] = (dp[i+1][(j + a) % 13] + dp[i][j]) % mod
    else:
        a = int(si) * memo[i]
        for j in range(13):
            dp[i+1][(j + a) % 13] = (dp[i+1][(j + a) % 13] + dp[i][j]) % mod
print(dp[len(s)][5])
### BUGGY CODE ###

x=int(input())
i=1
while not x==0:
    print(f"Case {i}: {x}")
    i=i+1


### FIXED CODE ###

i = 0
while True:
    x = int(input()); i += 1
    if x == 0: break
    print("Case {}: {}".format(i, x))
### BUGGY CODE ###

import itertools
h, w = [int(i) for i in input().split()]
a = [input() for i in range(h)]

for way in itertools.permutations([1 for i in range(h - 1)] + [-1 for i in range(w - 1)]):
    k = 0
    l = 0
    ij_list =[[k, l]]
    for way_route in way:
        k += (way_route == 1)
        l += (way_route == -1)
        ij_list.append([k, l])

    for i, j in itertools.product(range(h), range(w)):
            if [i, j] not in ij_list:
                if a[i][j] != ".":
                    break
            else:
                if a[i][j] != "#":
                    break
    else:
        print("Possible")
        break

else:
    print("Impossible")

### FIXED CODE ###

h, w = [int(i) for i in input().split()]
a = [input().count("#") for i in range(h)]
print(["Impossible", "Possible"][sum(a) == h + w - 1])
### BUGGY CODE ###

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

def cmp(a,b):
    if len(a) > len(b):
        return False
    elif len(a) < len(b):
        return True
    else:
        if int(a) >= int(b):
            return False
        else:
            return True

dp = [""] * (N+100)
l = [0,2,5,5,4,5,6,3,7,6]

for i in range(N+1):
    for s in A:
        if dp[i] == "" and i!=0:
            continue
        if cmp(dp[i + l[int(s)]] , dp[i] + s):
            dp[i + l[int(s)]] = dp[i] + s
            
print(dp[N])


                





### FIXED CODE ###

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

dp = [-1 for i in range(N+10)]
l = [0,2,5,5,4,5,6,3,7,6]
dp[0] = 0
for i in range(N-1):
    for s in A:
        if dp[i] == -1 and i!=0:
            continue
        if dp[i + l[s]] < dp[i]*10+s:
            dp[i + l[s]] = dp[i]*10+s
print(dp[N])
### BUGGY CODE ###

def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
n=int(input())
a=list(map(int,input().split()))
l=[0]*n
id=0
frac=[1]*(10**5+10)
p=10**9+7
for i in range(n+1):
    l[a[i]-1]=l[a[i]-1]+1
for i in range(n):
    if l[i]==2:
        id=i+1
buf=[]
for i in range(1,10**5+10):
    frac[i]=(frac[i-1]*i)%p
#print(frac[:6])
for i in range(n+1):
    if a[i]==id:
        buf.append(i)
#print(a,l,buf)
short=(n+1)-(max(buf)-min(buf))
N=n+1
#print(short,N)

for i in range(1,n+2,1):
    all=(frac[N]*modinv(frac[i],p)*modinv(frac[N-i],p))%p
    sub1=(frac[short]*modinv(frac[i],p)*modinv(frac[short-i],p))%p
    sub2=(frac[short-1]*modinv(frac[i],p)*modinv(frac[short-i-1],p))%p
    if short-i<0:
        sub1=0
    if short-i-1<0:
        sub2=0
    #print(all,sub1,sub2)
    print((all-sub1+sub2)%p)

### FIXED CODE ###

import collections
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
n=int(input())
a=list(map(int,input().split()))
id=0
frac=[1]*(10**5+10)
fracinv=[0]*(10**5+10)
p=10**9+7
c=collections.Counter(a)
id=c.most_common()[0][0]
buf=[]
for i in range(1,10**5+10):
    frac[i]=(frac[i-1]*i)%p
for i in range(0,10**5+10):
    fracinv[i]=modinv(frac[i],p)
#print(frac[:6])
for i in range(n+1):
    if a[i]==id:
        buf.append(i)
#print(a,l,buf)
N=n+1
short=N-(max(buf)-min(buf))

#print(short,N)

for i in range(1,n+2,1):
    if short-i<0:
        sub1=0
    else:
        sub1 = (((frac[short] * fracinv[i]) % p) * fracinv[short-i]) % p

    if short-i-1<0:
        sub2=0
    else:
        sub2 = (((frac[short - 1] * fracinv[i]) % p) * fracinv[short - i - 1]) % p
    all=(((frac[N]*fracinv[i])%p)*fracinv[N-i])%p

    #print(all,sub1,sub2)
    print((all-(sub1-sub2)%p)%p)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = 0
c = 0
ans = sum(a)
for i in range(q):
    b, c = map(int, input().split())
    b_num = a.count(b)
    ans += b_num*(c-b)
    for j in range(b_num):
        a.remove(b)
        a.append(c)
    print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
x = [0]*100001
for i in range(n):
    x[a[i]] += 1
q = int(input())
ans = sum(a)
for i in range(q):
    b, c = map(int, input().split())
    ans += x[b]*(c-b)
    x[c] += x[b]
    x[b] = 0
    print(ans)
### BUGGY CODE ###

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


### FIXED CODE ###

n = int(input())
list_a = list(map(int, input().split()))
from collections import Counter
under = Counter(list_a)

for i in range(1,n+1):
    print(under[i])
### BUGGY CODE ###

n = int(input())
c = 0
c_dict = {}
l = []
for i in range(n):
    s_listed = sorted(list(input()))
    s = ''.join(s_listed)
    if s in l:
        if s in c_dict.keys():
            c_dict[s] += 1
        else:
            c_dict[s] = 1
    l.append(s)
for i in c_dict.values():
    if i == 1:
        c += 1
    else:
        c += i * (i + 1) / 2
print(int(c))


### FIXED CODE ###

n = int(input())
c = 0
c_dict = {}
l = []
for i in range(n):
    s_listed = sorted(list(input()))
    s = ''.join(s_listed)
    if s in c_dict.keys():
        c_dict[s] += 1
        c += c_dict[s] - 1
    else:
        c_dict[s] = 1
print(int(c))
### BUGGY CODE ###

def main():
    import bisect
    B=bisect.bisect_left
    I=10**9+1
    n,q,*t=map(int,open(0).read().split())
    d=tuple(t[-q:])
    t=t[:-q]
    N0=2**(q-1).bit_length()
    data=[I]*2*N0
    for x,l,r in sorted(((x,B(d,s-x)+N0,B(d,t-x)+N0)for s,t,x in zip(t[::3],t[1::3],t[2::3])),reverse=1):
        while l<r:
            if r&1:
                r-=1
                data[r-1]=x
            if l&1:
                data[l-1]=x
                l+=1
            l>>=1
            r>>=1
    for k in range(N0-1,q+N0-1):
        s=I
        while~k:
            if data[k]<s:s=data[k]
            k=(k-1)//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    from bisect import bisect_left
    def update(l,r,v):
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=v
            if L&1:
                data[L-1]=v
                L+=1
            L>>=1
            R>>=1
    def query(k):
        k+=N0-1
        s=10**18
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        return s
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-10**18]+list(map(int,t[n:]))+[10**18]
    N0=2**(q+1).bit_length()
    data=[10**18]*2*N0
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        update(l,r,x)
    for i in range(q):
        a=query(i+1)
        print(-(a==10**18)or a)
if __name__=='__main__':
    main()
### BUGGY CODE ###

#E問題
import bisect

N = int(input())
A = [int(input()) for i in range(N)]
B = []
for i in range(N):
    if len(B) == 0:
        B.append(A[i])
    else:
        if B[0] >= A[i]:
            B.insert(0,A[i])
        else:
            index = bisect.bisect_left(B,A[i])-1
            B[index] = A[i]
print(len(B))

### FIXED CODE ###

#E問題
import heapq
import bisect
N = int(input())
A = [int(input()) for i in range(N)]
A = A[::-1]

C = []
for i in range(N):
    if i == 0:
        C.append(A[i])
    else:
        li = bisect.bisect_right(C,A[i])
        if li == len(C):
            C.append(A[i])
        else:
            C[li] = A[i]
    
print(len(C))
### BUGGY CODE ###

S = input()
N = len(S)

MOD = 10 ** 9 + 7

def nLeftA(S, A):
    """(S[:i]の'A'の選び方, S[:i]の'?'の埋め方)"""
    l = [(0, 1)]
    for s in S:
        a, q = l[-1]
        if s == A:
            a = q + a      # S[i-1]を選ぶ + S[:i]のどれかを選ぶ
        elif s == '?':
            a = q + a * 3  # S[i-1]を選ぶ + S[:i]のどれかを選ぶ(?に3通り)
            q = q * 3
        l.append((a, q))
    return l

l = nLeftA(S, 'A')
r = nLeftA(reversed(S), 'C')
r.reverse()
r = r[1:]

n = 0
for i in range(N):
    if S[i] in 'B?':
        n += l[i][0] * r[i][0] % MOD

print(n % MOD)


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
 
modulo = 10 ** 9 + 7
 
S = input()
 
def nleft(S, c):
    """各位置について，それより左の文字列に含まれる文字 c の総数.
       左に'?'が含まれるときは，それらに文字を入れて得られるすべての
       文字列に渡って，文字 c の個数を合計する. """
 
    # c の個数
    n = [0 for c in S]
    for i in range(1, len(S)):
        n[i] = n[i-1] + (1 if S[i-1] == c else 0)
 
    q = 0      # '?'の個数
    pow3q = 1  # 3 ** q
    for i in range(len(n)):
        if q > 0:
            n[i] *= pow3q         # ?の埋め方の数だけ増やす
            n[i] += pow3q1 * q    # ?に入る'C'の個数
            n[i] %= modulo
        if S[i] == '?':
            q += 1
            pow3q1 = pow3q
            pow3q  = pow3q * 3 % modulo
    return n
 
def nright(S, c):
    # c の個数
    n = [0 for c in S]
    for i in range(len(S) - 1, 0, -1):
        n[i-1] = n[i] + (1 if S[i] == c else 0)
 
    q = 0      # '?'の個数
    pow3q = 1  # 3 ** q
    for i in range(len(n) - 1, -1, -1):
        if q > 0:
            n[i] *= pow3q         # ?の埋め方の数だけ増やす
            n[i] += pow3q1 * q    # ?に入る'C'の個数
            n[i] %= modulo
        if S[i] == '?':
            q += 1
            pow3q1 = pow3q
            pow3q  = pow3q * 3 % modulo
    return n
 
 
left  = nleft (S, 'A')
right = nright(S, 'C')
 
# 各文字が'B'のときのABC数を計算
abc = 0
for i in range(0, len(S)):
    if S[i] in 'B?':
        abc += left[i] * right[i]
 
abc = int(abc) % modulo
print(abc)
### BUGGY CODE ###

s = input()
q = int(input())
q_lists = [input().split() for _ in range(q)]
for i in q_lists:
    if len(i)==1:
        s = s[::-1]
    else:
        f = i[1]
        c = i[2]
        if f=='1':
            s = c + s
        else:
            s = s + c
print(s)        

### FIXED CODE ###

s = input()
q = int(input())
ans_list1 = []
ans_list2 = []
flag = 1
for i in range(q):
    i = input().split()
    if i[0]=="1":
        flag *= -1
    else:
        if i[1]=='1':
            if flag==1:
                ans_list1.append(i[2])
            else:
                ans_list2.append(i[2])
        else:
            if flag==1:
                ans_list2.append(i[2])
            else:
                ans_list1.append(i[2])

if flag==1:
    print(''.join(ans_list1[::-1]) + s +''.join(ans_list2))
else:
    print(''.join(ans_list2[::-1]) + s[::-1] +''.join(ans_list1))
### BUGGY CODE ###

l, r = map(int, input().split())
if l - r >= 2019:
    print(0)
else:
    min = 10 ** 4
    for i in range(l, r + 1):
        for j in range(i + 1, r + 1):
            tmp = (i * j) % 2019
            if tmp < min:
                min = tmp
    print(min)

### FIXED CODE ###

l, r = map(int, input().split())
if r - l >= 2019:
    print(0)
else:
    mi = 2018
    for i in range(l, r):
        for j in range(i + 1, r + 1):
            mi = min((i * j) % 2019, mi)
    print(mi)
### BUGGY CODE ###

h,w,k=map(int,input().split())
dp=[[[0]*4 for _ in range(w+2)] for _ in range(h+2)]
f=[[0]*(w+1) for _ in range(h+1)]
for i in range(1,k+1):
  r,c,v=map(int,input().split())
  f[r][c]=v
for i in range(1,h+1):
  for j in range(1,w+1):
    for k in range(3,-1,-1):
      if k:dp[i][j][k]=max(dp[i][j][k],dp[i][j][k-1]+f[i][j])
      dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][k])
      dp[i][j+1][k]=max(dp[i][j+1][k],dp[i][j][k])
print(max(dp[h][w]))

### FIXED CODE ###

h,w,k=map(int,input().split())
dp=[[[0]*(w+2) for _ in range(h+2)] for _ in range(4)]
f=[[0]*(w+1) for _ in range(h+1)]
for _ in range(k):
  r,c,v=map(int,input().split())
  f[r][c]=v
for i in range(1,h+1):
  for j in range(1,w+1):
    for k in range(3,-1,-1):
      if k:dp[k][i][j]=max(dp[k][i][j],dp[k-1][i][j]+f[i][j])
      dp[0][i+1][j]=max(dp[0][i+1][j],dp[k][i][j])
      dp[k][i][j+1]=max(dp[k][i][j+1],dp[k][i][j])
print(max(dp[k][h][w] for k in range(4)))
### BUGGY CODE ###

import sys
from fractions import gcd

N=input()
A=map(int, sys.stdin.readline().split())

mod=10**9+7
def lcm(a, b):
    return a*b/gcd(a, b)

lc=1
for a in A:
    lc=lcm(lc,a)

ans=0
for a in A:
    b=lc/a
    ans+=b

print ans%mod

### FIXED CODE ###

import sys
from fractions import gcd

N=input()
A=map(int, sys.stdin.readline().split())

mod=10**9+7
def lcm(a, b):
    g=gcd(a, b)
    return a*b/gcd(a, b)

lc=1
for a in A:
    lc=lcm(lc,a)

ans=0
for a in A:
    b=lc*pow(a,mod-2,mod)
    ans+=b

print ans%mod
### BUGGY CODE ###

def bubbleSort(A):
    count = 0
    for i in range(len(A)):
        for j in range(i+1,len(A))[::-1]:
            if A[j] < A[j-1]:
                ret = A[j]
                A[j] = A[j-1]
                A[j-1] = ret
                count +=1
    return count 
input()
print(bubbleSort(list(map(int,input().split()))))

### FIXED CODE ###

from _collections import deque

SENIAL = 1000000000
def mergeSort(A,left,right):
    if left + 1 < right:
        middle = (left + right) // 2
        mergeSort(A, left, middle)
        mergeSort(A, middle, right)
        merge(A,left,right,middle)
    
def merge(A,left,right,middle):
    global count        
    L = deque(A[left:middle])
    R = deque(A[middle:right])
    L.append(SENIAL)
    R.append(SENIAL)
    for i in range(left,right):
        if L[0] < R[0]:
            A[i] = L.popleft()
        else:
            A[i] = R.popleft()
            count += len(L) -1 
count = 0     
input()
A = list(map(int,input().split()))
mergeSort(A,0,len(A))
print(count)
### BUGGY CODE ###

import sys
import os

N = int(input())
T = [0 for _ in range(N)]
A = [0 for _ in range(N)]
for i in range(N):
    t,a = list(map(int,input().split()))
    T[i] = t
    A[i] = a

points = T[0] + A[0]
for i in range(1,N):
    t, a = T[i], A[i]
    t0, a0 = T[i-1], A[i-1]
    while T[i] + A[i] < points or T[i] < t0 or A[i] < a0:
        T[i] += t
        A[i] += a
    points = T[i] + A[i]
print(points)


### FIXED CODE ###

import sys
import os
import math

N = int(input())
T = [0 for _ in range(N)]
A = [0 for _ in range(N)]
for i in range(N):
    t,a = list(map(int,input().split()))
    T[i] = t
    A[i] = a

for i in range(1,N):
    times = max( ( (T[i-1]+T[i]-1) // T[i] ) ,( (A[i-1]+A[i]-1) // A[i] ) )
    T[i] = T[i]*times
    A[i] = A[i]*times
print(T[N-1]+A[N-1])