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

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import numpy as np
import queue

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()

um = [[] for i in range(M)]
for i in range(M):
    um[i] = LI()

S,T = LI()
S -= 1
T -= 1
routes = [[] for i in range(N)]

for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = np.array([[mod,mod,mod] for i in range(N)])

q = queue.Queue()
q.put((S,0))
# Deep First Serch
while q.empty() == False:
    now, cost = q.get()
    state = cost % 3
    if used[now,state] == mod:
        used[now,state] = cost
        for route in routes[now]:
            q.put((route,cost+1))

# print(used)
try:
    ans = used[T, 0]
    if ans == mod:
        ans = -1
    else:
        ans = ans/3
except:
    ans = -1
print(int(ans))


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import numpy as np
import queue

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()

um = [[] for i in range(M)]
for i in range(M):
    um[i] = LI()

S,T = LI()
S -= 1
T -= 1
routes = [[] for i in range(N)]

for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = [[mod,mod,mod] for i in range(N)]

from collections import deque

# q = queue.Queue()
q = deque()
q.append((S,0))
# Deep First Serch
while q:
    now, cost = q.popleft()
    for route in routes[now]:
        n_state = (cost + 1) % 3
        if used[route][n_state] == mod:
            used[route][n_state] = cost + 1
            q.append((route,cost+1))


# print(used)
try:
    ans = used[T][0]
    if ans == mod:
        ans = -1
    else:
        ans = ans/3
except:
    ans = -1
print(int(ans))
### BUGGY CODE ###

import numpy as np

N, K, Q = [int(value) for value in input().split(' ')]
A = [int(input()) for _ in range(Q)]

points = np.full(N, K)

for i in range(Q):
    points = points - 1
    points[A[i] - 1] += 1

for point in points:
    if point > 0:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K, Q = [int(value) for value in input().split(' ')]
A = [int(input()) for _ in range(Q)]

points = [K - Q] * N

for value in A:
    points[value - 1] += 1

for point in points:
    if point <= 0:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

n, m = map(int, input().split())
a_list = list(map(int, input().split()))
a_len = len(a_list)

a_list.sort(reverse=True)

for x in range(m):
    a_list[0] /= 2

    i = 0
    while i+1 < a_len and a_list[i] < a_list[i + 1]:
        a_list[i], a_list[i + 1] = a_list[i + 1], a_list[i]
        i += 1

print(sum([int(x // 1) for x in a_list]))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a_list = []
for i in input().split(): heapq.heappush(a_list, -int(i))

for x in range(m):
	tmp = heapq.heappop(a_list) / 2
	heapq.heappush(a_list, tmp)

print(sum([int(-x // 1) for x in a_list]))
### BUGGY CODE ###

X, K, D = map(int, input().split())
X = abs(X)

if X >= D * K:
  print(X - D * K)
else:
  K -= int(X / D)
  for i in range(0, int(X/D)):
    X -= D
  if K % 2:
    print(D - X)
  else:
    print(X)

### FIXED CODE ###

X, K, D = map(int, input().split())
X = abs(X)

if X >= D * K:
  print(X - D * K)
else:
  K -= int(X / D)
  # for i in range(0, int(X/D)):
  #   X -= D
  X %= D
  if K % 2:
    print(D - X)
  else:
    print(X)
### BUGGY CODE ###

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

la = len(a)
tmp = 1
cnt = 0
for num in range(n):
  for i,ai in enumerate(a):
    if ai == tmp:
      a = a[i:]
      tmp += 1
      cnt += 1
      break
if cnt == 0:
  print(-1)
else:
  print(la - cnt)

### FIXED CODE ###

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

la = len(a)
tmp = 1
cnt = 0
for i in range(n):
  if a[i] == tmp:
    tmp += 1
    cnt += 1
if cnt == 0:
  print(-1)
else:
  print(la - cnt)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
def frog(arr,N):
    if N==0:
        return arr[0]
    elif N==1:
        return abs(arr[1]-arr[0])
    elif N==2:
        return min(frog(arr,N-1)+abs(arr[N]-arr[N-1]),abs(arr[N]-arr[N-2]))
    else:
        return min(frog(arr,N-2)+abs(arr[N]-arr[N-2]),frog(arr,N-1)+abs(arr[N]-arr[N-1]))
if __name__ == "__main__":
    N=int(input())
    h=[int(i) for i in input().split()][:N]
    print(frog(h,N-1))

### FIXED CODE ###

N=int(input())
h=[int(i) for i in input().split()][:N]
dp=[float('inf')]*N
dp[0]=0
for i in range(N-1):
    if i+1<N:
        dp[i+1]=min(dp[i+1],dp[i]+abs(h[i+1]-h[i]))
    if i+2<N:
        dp[i+2]=min(dp[i+2],dp[i]+abs(h[i+2]-h[i]))
print(dp[-1])
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
pushed = [False] * N
pushed[0] = True
button = 0
count = 0
while True:
    count += 1
    button = A[button] - 1
    if button == 1:
        print(count)
        exit()
    if pushed[button]:
        print(-1)
        exit()


### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
pushed = [False] * N
pushed[0] = True
button = 0
count = 0
while True:
    count += 1
    button = A[button] - 1
    if button == 1:
        print(count)
        exit()
    if pushed[button]:
        print(-1)
        exit()
    pushed[button] = True
### BUGGY CODE ###

import math
N, K = map(int, input().split())
P = list(map(int, input().split()))

INDEX = -1
MA = 0
for i in range(N - K + 1):
    M = 0
    for j in range(K):
        M += P[i + j]
    
    if M > MA:
        MA = M
        INDEX = i
# print(i)
ans = 0
for i in range(K):
    # print(P[i+INDEX])
    ans += P[i+INDEX] * (P[i+INDEX]+1) / (2*P[i+INDEX])
    # print(M)
    # print(i)
# print(tmp)
# ans = 0
# for t in tmp:
#     ans += t * (t + 1) / (2 * t)
print("{:.12f}".format(ans))


### FIXED CODE ###

import math
N, K = map(int, input().split())
P = list(map(int, input().split()))

INDEX = 0
total = 0
for i in range(K):
    total += P[i]

tmp = total
for i in range(N - K):
    tmp = tmp - P[i] + P[i + K]
    
    if tmp > total:
        total = tmp
        INDEX = i+1


# MA = 0
# for i in range(N - K + 1):
#     M = 0
#     for j in range(K):
#         M += P[i + j]
    
#     if M > MA:
#         MA = M
#         INDEX = i

ans = 0
for i in range(K):
    ans += P[i+INDEX] * (P[i+INDEX]+1) / (2*P[i+INDEX])

print("{:.12f}".format(ans))
### BUGGY CODE ###

S=input()
Q=int(input())
reverse=False

A,B="",""
for _ in range(Q):
    T=input()
    if T[0]=="1":
        reverse=not reverse
    else:
        _,F,C=T.split()

        if ((not reverse) and F=="1") or (reverse and F=="2"):
            A+=C
        else:
            B+=C

if reverse:
    print(B[::-1]+S[::-1]+A)
else:
    print(A[::-1]+S+B)


### FIXED CODE ###

from collections import deque
H=deque(input())
Q=int(input())
reverse=False

A,B="",""
for _ in range(Q):
    T=input()
    if T[0]=="1":
        reverse=not reverse
    else:
        _,F,C=T.split()

        if ((not reverse) and F=="1") or (reverse and F=="2"):
            H.appendleft(C)
        else:
            H.append(C)

if reverse:
    H.reverse()

for s in H:
    print(s,end="")
print()
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = [K] * N
for q in range(Q):
    answered = int(input())
    A[answered - 1] += 1
    A = [_ - 1 for _ in A]
    #print(A)

for item in A:
    if item <= 0:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

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

answered = [K - Q] * N

for q in range(Q):
    correct = int(input())
    answered[correct - 1] += 1
for item in answered:
    if item <= 0:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

import sys, math, copy
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial

sys.setrecursionlimit(10**7)
H, W = map(int, input().split())
maze = [[c for c in input()] for _ in range(H)]

moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def chkcell(maze_copy, h, w):
    if 0<=h and h<H and 0<=w and w<W and maze_copy[h][w]=='.':
        return True

def count_steps(q, maze_copy):
    steps = -1
    while len(q):
#        print('q:', q)
#        print('maze:')
#        for row in maze_copy:
#            print(row)
        steps += 1
        next_cells = []
        cells = q.pop()
        for cell in cells:
            maze_copy[cell[0]][cell[1]] = '#'
            for move in moves:
                newcell = tuple(i+j for i, j in zip(cell, move))
                if chkcell(maze_copy=maze_copy, h=newcell[0], w=newcell[1]):
                    next_cells.append(newcell)
        if next_cells:
            q.append(next_cells)

#    print('max_step:', steps)
    return steps

def main():
    res = 0
    for i in range(H):
        for j in range(W):
#        print('i, j', i, j)
            if maze[i][j] == '#':
                continue
            q = deque()
            q.append([[i, j]])
#        maze_copy = copy.deepcopy(maze)
            maze_copy = [[c for c in row] for row in maze]
            val = count_steps(q, maze_copy)
            if res < val: res = val

    print(res)

if __name__ == '__main__':
    main()


### FIXED CODE ###

from copy import deepcopy
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

def check(ny, nx, sS):
    if 0<=ny<H and 0<=nx<W:
        if sS[ny][nx]=='.':
            return True
    else:
        return False

def bfs(sy, sx, sS):
    deq = deque()
    deq.append([(sy-1, sx-1)]) # insert indices
    sS[sy-1][sx-1] = '#'
    ddy = [-1, 0, 1, 0]
    ddx = [0, -1, 0, 1]
    step = 0
    while deq[0]:
        #print('deq', deq)
        nqueue = []
        cqueue = deq.popleft()
        for val in cqueue:
            y, x = val
            for dy, dx in zip(ddy, ddx):
                ny, nx = y+dy, x+dx
                if check(ny, nx, sS):
                    sS[ny][nx] = '#'
                    nqueue.append((ny, nx))
        deq.append(nqueue)
        if not(deq[0]):
            break
        step += 1
    return step

res = 0
for i in range(H):
    for j in range(W):
        #print('i, j:', i, j)
        if S[i][j] == '.':
            sS = deepcopy(S)
            val = bfs(i+1, j+1, sS)
            res = max(res, val)

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

n, m, q = [int(i) for i in input().split()]
m_list = [[0 for i in range(n+1)] for j in range(n+1)]
dynamic = [[0 for i in range(n+1)] for j in range(n+1)]

for i in range(m):
    l, r = [int(i) for i in input().split()]
    m_list[l][r] += 1

for i in range(1, n+1):
    for j in range(i, n+1):
        dynamic[i][j] = dynamic[i][j-1]
        for k in range(i, j+1):
            dynamic[i][j] += m_list[k][j]

for i in range(q):
    l, r = [int(i) for i in input().split()]
    print(dynamic[l][r])


### FIXED CODE ###

n, m, q = [int(i) for i in input().split()]
imos = [[0 for r in range(n+1)] for l in range(n+1)]
for i in range(m):
    l, r = [int(i) - 1 for i in input().split()]
    imos[0][r] += 1
    imos[l+1][r] -= 1
#imos法
for l in range(n):
    for r in range(1, n):
        imos[l][r] += imos[l][r-1]
for r in range(n):
    for l in range(1, n):
        imos[l][r] += imos[l-1][r]
for i in range(q):
    l, r = [int(i) - 1 for i in input().split()]
    print(imos[l][r])
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
flag = False
AClist = [0] * N
for i in range(N):
    if S[i] == "A":
        flag = True
    elif S[i] == "C" and flag:
        AClist[i] = -1
        AClist[i-1] = 2
        flag = False
for i in range(Q):
    l , r = map(int, input().split())
    l -= 1
    ans = sum(AClist[l:r])
    if AClist[r-1] == 2:
        ans -= 2
    if AClist[l] == -1:
        ans += 1
    print(ans)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
AClist = [0] 
for i in range(N-1):
    if S[i+1] == "C" and S[i] == "A":
        AClist.append(AClist[-1] + 1)
    else:
        AClist.append(AClist[-1])
for i in range(Q):
    l , r = map(int, input().split())
    print(AClist[r-1] - AClist[l-1])
### BUGGY CODE ###

from sys import stdin, exit

N = int(stdin.readline().rstrip())
work = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(N)]

work.sort(key=lambda x: x[1])
time = 0
for k in range(N):
    if time + work[0][0] > work[0][1]:
        print('No')
        exit()
    time += work.pop(0)[0]
print('Yes')


### FIXED CODE ###

from sys import stdin, exit

N = int(stdin.readline().rstrip())
work = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(N)]

work.sort(key=lambda x: x[1])
time = 0
for k in range(N):
    if time + work[k][0] > work[k][1]:
        print('No')
        exit()
    time += work[k][0]
print('Yes')
### BUGGY CODE ###

k, s = map(int, input().split())
count = 0
for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x + y + z == s:
        count += 1
print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for x in range(k+1):
  for y in range(k+1):
    z = s - x - y
    if 0 <= z and z <= k:
      count += 1
print(count)
### BUGGY CODE ###

n,k,q=map(int,input().split())
a_list=[int(input()) for i in range(q)]
 
for i in range(n):
  if a_list.count(i+1) > q-k:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

n,k,q=map(int,input().split())
li=[0]*n
for i in range(q):
  a=int(input())
  li[a-1]+=1
for i in range(n):
  if li[i]>q-k:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

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

P_total = sum(P)

max_sum = 0

if K < (N/2):
    for i in range(N-K+1):
        tmp_sum = sum(P[i:i+K])
        if tmp_sum > max_sum:
            max_sum = tmp_sum
else:
    for i in range(N-K+1):
        tmp_sum = P_total - sum(P[0:i]) - sum(P[i+K:])
        if tmp_sum > max_sum:
            max_sum = tmp_sum

max_E = (max_sum + K) / 2
print(max_E)

### FIXED CODE ###

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

# 期待値
E = [(p+1)/2 for p in P]
#print(E)

# 累積和
S = [0] * (N+1)
for i in range(N):
    S[i+1] = S[i] + E[i]
#print(S)

# 隣接K個を取り出して足す
max_E = 0
for i in range(N-K+1):
    tmp_E = S[i+K] - S[i]
    #print(tmp_E)
    if tmp_E > max_E:
        max_E = tmp_E

print(max_E)
### BUGGY CODE ###

n,m = map(int,input().split())
a = []
b = []
l = []
ans = 0
count = 0

for i in range(n):
	a_dash,b_dash = map(int,input().split())
	a.append(a_dash)
	b.append(b_dash)

c = zip(a,b)
c = sorted(c)
a,b = zip(*c)
a = list(a)
b = list(b)

for i in reversed(range(m)):
	for j in range(count,len(a)):
		if a[j] + i == m:
			l.append(b[j])
			count += 1
		else:
			break
	if len(l) != 0:
		maximum = max(l)
		ans += maximum
		l.pop(l.index(maximum))

print(ans)


### FIXED CODE ###

import sys
import heapq

s = sys.stdin.readlines()
n,m = map(int,s[0].split())
a = []
b = []
l = []
ans = 0
count = 0

for i in range(1,n+1):
	a_dash,b_dash = map(int,s[i].split())
	a.append(-a_dash)
	b.append(-b_dash)

c = zip(a,b)
c = sorted(c,reverse=True)
a,b = zip(*c)
a_length = len(a)

for i in reversed(range(m)):
	for j in range(count,a_length):
		if -a[j] + i == m:
			heapq.heappush(l,b[j])
			count += 1
		else:
			break
	if len(l) != 0:
		maximum = heapq.heappop(l)
		ans += maximum

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

N=int(input())

li=[]
l=0
m=0

for i in range(N//2+1):
  if N%(i+1)==0:
    l=i
    m=N/(i+1)-1
    li.append(l+m)
  else:
    pass

print(int(min(li)))



### FIXED CODE ###

import math 

N=int(input())

li=[]
l=0
m=0

for i in range(math.floor(math.sqrt(N))):
  if N%(i+1)==0:
    l=i
    m=N/(i+1)-1
    li.append(l+m)
  else:
    pass

print(int(min(li)))
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
for i in range(q):
    tmp = s
    list_q = list(map(int, input().split()))
    tmp = tmp[list_q[0]-1:list_q[1]]
    tmp = tmp.split("AC")
    print(len(tmp) - 1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, Q = map(int,input().split())
S = list(input())[:-1]
list_Sum = [0]*(N+1)
for i in range(1, N):
    list_Sum[i+1] = list_Sum[i]
    if S[i-1] == "A" and S[i] == "C":
        list_Sum[i+1] += 1
for i in range(Q):
    l, r = map(int,input().split())
    print(list_Sum[r]-list_Sum[l])
### BUGGY CODE ###

import itertools
N, M, Q = map(int, input().split())
P = []
LR = [[0] * (N+1) for _ in range(N+1)] 
for m in range(M):
    l, r = map(int, input().split())
    LR[l][r] += 1

for q in range(Q):
    p = list(map(int, input().split()))
    P.append(p)

csum = []
for L in LR:
    a = list(itertools.accumulate(L))
    csum.append(a)

for p in P:
    ans = 0
    l, r = p
    for c in csum[l:r+1]:
        ans += (c[r] - c[l-1])
    print (ans)

### FIXED CODE ###

import itertools
N, M, Q = map(int, input().split())
P = []
LR = [[0] * (N+1) for _ in range(N+1)] 
for m in range(M):
    l, r = map(int, input().split())
    LR[l][r] += 1

for q in range(Q):
    p = list(map(int, input().split()))
    P.append(p)

csum = []
for L in LR:
    a = list(itertools.accumulate(L))
    csum.append(a)

for p in P:
    ans = 0
    l, r = p
    for c in csum[l:r+1]:
        ans += (c[r] - c[l-1])
    print (ans)
### BUGGY CODE ###

def resolve():
    '''
    code here
    '''
    import collections
    H, W, M = [int(item) for item in input().split()]
    targets = [[int(item) -1 for item in input().split()] for _ in range(M)]

    col = [0 for _ in range(H+1)]
    row = [0 for _ in range(W+1)]

    for i,j in targets:
        col[i] += 1
        row[j] += 1

    max_col = max(col)
    max_row = max(row)
    max_col_index = []
    max_row_index = []

    for i in range(H):
        if col[i] == max_col:
            max_col_index.append(i)

    for i in range(W):
        if row[i] == max_row:
            max_row_index.append(i)

    res = 0
    for item in max_col_index:
        for jtem in max_row_index:
            if [item, jtem] in targets:
                res = max(res, max_col + max_row - 1)
            else:
                res = max(res, max_col + max_row)
    print(res)

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    '''
    code here
    '''
    H, W, M = [int(item) for item in input().split()]
    targets = [[int(item) -1 for item in input().split()] for _ in range(M)]

    col = [0 for _ in range(H)]
    row = [0 for _ in range(W)]

    bomb_set = set()
    # 配列で要素を作ると要素数が$10^8$超える場合、setで要素の座標を持っておく


    for i,j in targets:
        col[i] += 1
        row[j] += 1
        bomb_set.add((i,j))

    max_col = max(col)
    max_row = max(row)
    max_col_index = []
    max_row_index = []

    for i in range(H):
        if col[i] == max_col:
            max_col_index.append(i)

    for i in range(W):
        if row[i] == max_row:
            max_row_index.append(i)

    res = 0
    for item in max_col_index:
        for jtem in max_row_index:
            if (item,jtem) not in bomb_set:
                res =max_col + max_row
                break
        else:
            res = max(res, max_col + max_row -1 )
    print(res)

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

import numpy as np

n =	int(input())
nums = [int(input()) for i in range(n)]

num_max = np.max(nums)
next_max = sorted(nums)[-2]


for idx, el in enumerate(nums):
	del nums[idx]
	if num_max == el:
		print(next_max)		
	else:
		print(num_max)
	nums.insert(idx, el)



### FIXED CODE ###

import numpy as np

n =	int(input())
nums = [int(input()) for i in range(n)]

num_max = np.max(nums)
next_max = sorted(nums)[-2]


for idx, el in enumerate(nums):
	if num_max == el:
		print(next_max)		
	else:
		print(num_max)
### BUGGY CODE ###

# coding: utf-8
import re
import math
import fractions
#import numpy as np

mod=int(10**9+7)

def lcm(a,b):
    return a*b//fractions.gcd(a,b)

#main
N=int(input())
A=list(map(int,input().split()))
l=A[0]
for a in A:
    l=lcm(l,a)

ans=0
for a in A:
    ans+=l//a
    ans%=mod
print(ans)

### FIXED CODE ###

# coding: utf-8
import re
import math
import fractions
#import numpy as np

mod=int(10**9+7)


def lcm(a,b):
    ab=a*b
    return ab//fractions.gcd(a,b)

#main
N=int(input())
A=list(map(int,input().split()))
l=A[0]
for a in range(1,N):
    l=lcm(l,A[a])
l%=mod

ans=0
for a in A:
    ans+=l*pow(a,mod-2,mod)
    ans%=mod
print(ans)
### BUGGY CODE ###

import math
import fractions
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
# ans = 1
ans = reduce(fractions.gcd, A[1:])
for i in range(1, N-1):
    left_gcd = reduce(fractions.gcd, A[:i])
    right_gcd = reduce(fractions.gcd, A[i+1:])
    ans = max(ans, fractions.gcd(left_gcd, right_gcd))
left_gcd = reduce(fractions.gcd, A[:-1])
ans = max(ans, left_gcd)
print(ans)


### FIXED CODE ###

import math
import fractions
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
from_left = [0 for i in range(N)]
from_right = [0 for i in range(N)]
from_left[0] = A[0]
from_right[-1] = A[-1]
for i in range(1, N):
    from_left[i] = fractions.gcd(A[i], from_left[i-1])
for i in range(N-2, -1, -1):
    from_right[i] = fractions.gcd(A[i], from_right[i+1])
# print(from_left)
# print(from_right)
ans = max(from_left[-2], from_right[1])
for i in range(1, N-1):
    ans = max(ans, fractions.gcd(from_left[i-1], from_right[i+1]))
print(ans)
### BUGGY CODE ###

x = int(input())

a = 1
b = 0
while True:
    A = pow(a, 5)
    B = pow(b, 5)
    if A-B == x:
        print(a, b)
        break
    if A+B == x:
        print(a, -b)
        break
    a += 1
    b += 1


### FIXED CODE ###

x = int(input())

for a in range(200):
    for b in range(200):
        if pow(a, 5) - pow(b, 5) == x:
            print(a, b)
            exit()
        if pow(-a, 5) - pow(b, 5) == x:
            print(-a, b)
            exit()
        if pow(a, 5) - pow(-b, 5) == x:
            print(a, -b)
            exit()
        if pow(-a, 5) - pow(-b, 5) == x:
            print(-a, -b)
            exit()