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

def sol():
    N, Ma, Mb = map(int, input().split())
    items = []
    for _ in range(N):
        a, b, c = map(int, input().split())
        items.append((a, b, c))

    dp = [[set([()]) for _ in range(Ma)] for _ in range(N + 1)]

    for i, (a, _, _) in enumerate(items):
        for mod in range(Ma):
            for prev in dp[i][mod]:
                dp[i + 1][mod].add(prev)
            for prev in dp[i][(mod - a) % Ma]:
                dp[i + 1][mod].add(tuple(list(prev) + [i]))

    maList = filter(lambda A : len(A) > 0, dp[N][0])

    ans = float('inf')
    for addList in maList:
        sumA = 0
        sumB = 0
        cost = 0
        for i in addList:
            sumA += items[i][0]
            sumB += items[i][1]
            cost += items[i][2]
        if sumA * Mb == sumB * Ma:
            ans = min(ans, cost)

    if ans == float('inf'):
        print(-1)
    else:
        print(ans)

sol()

### FIXED CODE ###

def sol():
    N, Ma, Mb = map(int, input().split())

    A = []
    B = []
    cost = []
    sumA = 0
    sumB = 0

    for _ in range(N):
        a, b, c = map(int, input().split())
        A.append(a)
        B.append(b)
        cost.append(c)
        sumA += a
        sumB += b

    dp = [[[float('inf') for _ in range(sumB * 2 + 1)] for _ in range(sumA * 2 + 1)] for _ in range(N + 1)]
    dp[0][0][0] = 0

    for index in range(N):
        for sA in range(sumA + 1):
            for sB in range(sumB + 1):
                dp[index + 1][sA][sB] = min(
                    dp[index + 1][sA][sB],
                    dp[index][sA][sB]
                )
                dp[index + 1][sA + A[index]][sB + B[index]] = min(
                    dp[index + 1][sA + A[index]][sB + B[index]],
                    dp[index][sA][sB] + cost[index]
                )

    ans = float('inf')
    for sA in range(1, sumA):
        for sB in range(1, sumB):
            if sA * Mb == sB * Ma:
                ans = min(ans, dp[N][sA][sB])

    if ans == float('inf'):
        print('-1')
    else:
        print(ans)

sol()
### BUGGY CODE ###

N,M=(int(x) for x in input().split())
a=[int(input()) for i in range(M)]

x=[0]*(N+1)
if len(x)!=0:
    x[0]=1
if len(x) >0:
    x[1]=1 if not 1 in a else 0

for i in range(2,N+1): 
    if not i in a:
        x[i]=x[i-1]+x[i-2]
    else:
        x[i]=0

print(int(x[N]%(1000000007)))

### FIXED CODE ###

N,M=(int(x) for x in input().split())
a=[int(input()) for i in range(M)]

x=[0]*(N+1)
j=0
if N!=0:
    x[0]=1
if N>1 and M!= 0 and a[0]==1:
    j+=1
else:
    x[1]=1

for i in range(2,N+1): 
    if j==M or i!=a[j]:
        x[i]=x[i-1]+x[i-2]
    else:
        x[i]=0
        j+=1
print(int(x[N]%(1000000007)))
### BUGGY CODE ###

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

def inv(k):
    return pow(k, mod - 2, mod)

def comb(n, k):
    bunshi = 1
    bunbo = 1
    for i in range(k):
        bunshi *= (n - i)
        bunbo *= (i + 1)
    return bunshi * inv(bunbo) % mod

mod = 1000000007
all_num = pow(2, n, mod)

ans = all_num - 1 - comb(n, a) - comb(n, b)
print(ans)

### FIXED CODE ###

n, a, b = map(int, input().split())
mod = 1000000007
def inv(y, mod):
    return pow(y, mod - 2, mod)

def comb(n, a, mod):
    x = 1
    y = 1
    for i in range(a):
        x = x * (n - i) % mod
        y = y * (i + 1) % mod
    return (x * inv(y, mod)) % mod
    
print((pow(2, n, mod) - 1 - comb(n, a, mod) - comb(n, b, mod)) % mod)
### BUGGY CODE ###

X, K, L = map(int, input().split())
Distance = []
for p_num in range(K+1):
    dist = L*p_num + (-1)*L*(K-p_num)
    Distance.append(abs(X + dist))


print(min(Distance))


### FIXED CODE ###

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

X = abs(X)

n = X // D
m = K - n

A1 = abs(X - n*D)
A2 = abs(X - (n+1)*D)

Ans = A2

if m > 1:
    if A1 <= A2:
        if m % 2 == 0:
            Ans = A1
    else:
        if m % 2 == 0:
            Ans = A1
else:
    Ans = abs(X - K*D)

print(Ans)
### BUGGY CODE ###

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

res = [(x,y,z) for x in range(K+1)
for y in range(K+1)
for z in range(K+1)
if x+y+z==S]

print(len(res))

### FIXED CODE ###

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

res = [(x) for x in range(K+1)
for y in range(K+1)
if x+y <= S and x+y >= S-K]

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

import math

def f(n):
  max_loop = math.ceil(math.sqrt(n))
  ans = 0

  for x in range(1, max_loop):
    x2 = x ** 2

    for y in range(1, max_loop):
      y2 = y ** 2

      for z in range(1, max_loop):
        z2 = z ** 2

        if x2 + y2 + z2 + x * y + y * z + z * x == n:
          ans += 1

  return ans

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

  for i in range(1, N+1):
    print(f(i))

if __name__ == "__main__":
  main()

### FIXED CODE ###

import math


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

  dp = [0] * N

  lx = math.ceil(math.sqrt(N))

  for x in range(1, lx):
    x2 = x ** 2

    ly = math.ceil(math.sqrt(max(1, N - x2)))

    for y in range(1, ly):
      y2 = y ** 2
      lz = math.ceil(math.sqrt(max(1, N - x2 - y2 - (x * y))))

      for z in range(1, lz):
        z2 = z ** 2

        v = x2 + y2 + z2 + x * y + y * z + z * x
        if(v <= N):
          dp[v-1] += 1

  for v in dp:
    print(v)

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

import heapq

n,m,s,t = map(int,input().split())
inf = 1000000000000000
gyen = [[] for _ in range(n)]
gsnuuk = [[] for _ in range(n)]

for _ in range(m):
        u,v,a,b = map(int,input().split())
        gyen[u-1].append([v-1,a])
        gyen[v-1].append([u-1,a])
        gsnuuk[u-1].append([v-1,b])
        gsnuuk[v-1].append([u-1,b])

def dijkstra(graph, start):
        dist = [inf for _ in range(n)]
        dist[start] = 0
        q = [(0,start)]
        while q:
                du, u = heapq.heappop(q)
                if dist[u] < du:
                        continue
                for i in graph[u]:
                        if dist[i[0]] > du+i[1]:
                                dist[i[0]] = du+i[1]
                                heapq.heappush(q, (dist[i[0]], i[0]))
        return dist

dist_from_start = dijkstra(gyen,s-1)
dist_from_goal = dijkstra(gsnuuk,t-1)

ans = [0 for _ in range(n)]
ans[n-1] = dist_from_start[n-1]+dist_from_goal[n-1]
for i in range(n-1):
        ans[n-2-i] = min(ans[n-1-i],dist_from_start[n-2-i]+dist_from_goal[n-2-i])
for i in range(n):
        print(inf-ans[i])

### FIXED CODE ###

import heapq
import sys
from itertools import accumulate

n,m,s,t = map(int,next(sys.stdin).split(" "))
inf = 1000000000000000
gyen = [dict() for _ in range(n)]
gsnuk = [dict() for _ in range(n)]

for _ in range(m):
        u,v,a,b = map(int,next(sys.stdin).split(" "))
        gyen[u-1][v-1] = gyen[v-1][u-1] = a
        gsnuk[u-1][v-1] = gsnuk[v-1][u-1] = b

def dijkstra(graph, start):
        dist = [inf for _ in range(n)]
        dist[start] = 0
        q = [(0,start)]
        while q:
                du, u = heapq.heappop(q)
                if dist[u] < du:
                        continue
                for v,d in graph[u].items():
                        if dist[v] > du+d:
                                dist[v] = du+d
                                heapq.heappush(q, (dist[v], v))
        return dist

yen = dijkstra(gyen,s-1)
snuke = dijkstra(gsnuk,t-1)

ans = list(accumulate([y+s for y,s in zip(yen,snuke)][::-1],min))
[print(inf-ans[i]) for i in range(n-1,-1,-1)]
### BUGGY CODE ###

import heapq

def main():

    N, M = map(int, input().split())
    AB = []
    for i in range(N):
        a, b = map(int, input().split())
        AB.append([a, b])
        AB.sort(reverse = True)
    q = []
    ans = 0
    for i in range(M-1, -1, -1):
        while AB and AB[-1][0] <= M-i:
            a, b = AB.pop()
            heapq.heappush(q, -b)
        if q:
            v = -heapq.heappop(q)
            ans += v
    return ans


if __name__ == '__main__':
    print(main())

### FIXED CODE ###

import heapq
def main():

    N, M = map(int, input().split())
    task = []
    for _ in range(N):
        A, B = map(int, input().split())
        task.append([A, B])
    task.sort()

    hq = []
    ans = 0
    for i in range(1, M+1):
        while task and task[0][0]<= i:
            _, v = heapq.heappop(task)
            heapq.heappush(hq, -v)
        if hq:
            v = heapq.heappop(hq)
            ans += -v
    return ans

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

N,M=map(int,input().split())
H=[-1]
H.extend(list(map(int,input().split())))

lst=list(range(1,N+1))

left=[]
for h in lst:
    left.append(h)

for _ in range(M):
    A,B=map(int,input().split())
    if H[A]<H[B] and A in left:
        n = left.index(A)
        left.pop(n)
    elif H[A]>H[B] and B in left:
        n = left.index(B)
        left.pop(n)
    elif H[A]==H[B]:
        if A in left:
            n = left.index(A)
            left.pop(n)
        if B in left:
            n = left.index(B)
            left.pop(n)

print(len(left))

### FIXED CODE ###

N,M=map(int,input().split())
H=[-1]
H.extend(list(map(int,input().split())))

lose = set()

for _ in range(M):
    A,B=map(int,input().split())
    if H[A]<H[B]:
        lose.add(A)
    elif H[A]>H[B]:
        lose.add(B)
    elif H[A]==H[B]:
        lose.add(A)
        lose.add(B)

print(N-len(lose))
### BUGGY CODE ###

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

ans = 0
for i in set(a):
  c = a.count(i)
  if c >= i:
    ans += i
print(n - ans)

### FIXED CODE ###

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

ans = 0
for i in set(a):
  if i <= n:
    c = a.count(i)
    if c >= i:
      ans += i
print(n - ans)
### BUGGY CODE ###

n = int(input())
s = input()

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j] and i != j:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        if A[i] >= N - i - 1:
        	return A[i]
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return 0

ans = 0
for i in range(n-1):
	res = z_algo(s[i:])
	#print(res)
	#tmp = max(res[1:])
	ans = max(ans, res)

print(ans)


### FIXED CODE ###

n = int(input())
s = input()

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
        	j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A
ans = 0
for i in range(n-1):
	tmp = z_algo(s[i:])
	for j,zj in enumerate(tmp):
		if j+1 > zj:
			ans = max(ans,zj)

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

A, B, K = map(int, input().split())
l = []
for i in range(A, B+1):
    l.append(i)
    
if B - (A-1) < 2*K:
    for j1 in l:
        print(j1)
else:
    for j2 in range(A, A+K):
        print(j2)
    for j3 in range(B-K+1, B+1):
        print(j3)

### FIXED CODE ###

A, B, K = map(int, input().split())
    
if B - (A-1) < 2*K:
    l = []
    for i in range(A, B+1):
        l.append(i)
    for j1 in l:
        print(j1)
else:
    for j2 in range(A, A+K):
        print(j2)
    for j3 in range(B-K+1, B+1):
        print(j3)
### BUGGY CODE ###

NK = list(map(int, input().split()))
N = NK[0]
K = NK[1]
sumOfAll = 0
for howManyWeChoose in range(K, N+2):
    lastMembers = []
    firstmembers = []
    for i in range(howManyWeChoose):
        lastMembers.append(N-i)
        firstmembers.append(i)
    until = sum(lastMembers)
    start = sum(firstmembers)
#     sumOfAll += howManyWeChoose * (until - start + 1) * (10 ** 100) + sum(range(start, until + 1))
# print(sumOfAll%(7+10**9))
    sumOfAll += len(range(start, until + 1))
print(sumOfAll%(7+10**9))

### FIXED CODE ###

NK = list(map(int, input().split()))
N = NK[0]
K = NK[1]
sumOfAll = 0
for howManyWeChoose in range(K, N+2):
    until = int(N*(N+1)/2 - (N-howManyWeChoose)*(N-howManyWeChoose+1)/2)
    start = int(howManyWeChoose*(howManyWeChoose-1)/2)
    sumOfAll += until-start+1
print(sumOfAll%(7+10**9))
### BUGGY CODE ###

import sys

n, m = map(int, input().split())
INF = 10 ** 9
dp = [INF] * (1 << n)
dp[0] = 0
bits = [0] + [1 << i for i in range(n)]
get_bits = bits.__getitem__

for _ in [0] * m:
  a, b = map(int, sys.stdin.readline().split())
  s = sum(map(get_bits, map(int, sys.stdin.readline().split())))
  for t in range(1 << n):
    if (dp[t] == -1):
      continue
    dp[t | s] = min(dp[t | s], dp[t] + a)

print(dp[-1] if dp[-1] != INF else -1)


### FIXED CODE ###

import sys

n, m = map(int, input().split())
INF = 10 ** 9
dp = [INF] * (1 << n)
dp[0] = 0
bits = [0] + [1 << i for i in range(n)]
get_bits = bits.__getitem__

for _ in [0] * m:
  a, b = map(int, sys.stdin.readline().split())
  s = sum(map(get_bits, map(int, sys.stdin.readline().split())))
  for t in range(1 << n):
    if (dp[t] == -1):
      continue
    dp[t | s] = min(dp[t | s], dp[t] + a)

print(dp[-1] if dp[-1] != INF else -1)
### BUGGY CODE ###

*j, n = map(int, input().split())
j.sort()
a, b, c = j
count = 0
for y in range(n//b+1):
    for z in range(n//c+1):
        x = (n - b*y - c*z) / a
        if int(x) == x and x >= 0:
            count += 1
print(count)

### FIXED CODE ###

*j, n = map(int, input().split())
j.sort()
a, b, c = j
count = 0
for y in range(n//b+1):
    for z in range((n-y*b)//c+1):
        if (n - b*y - c*z) % a == 0:
            count += 1
print(count)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    # emp:0 male:1 female:2
    N = int(input())
    L = [-1] * N

    i = 0
    print(i, flush=True)
    s = str(input())
    if s == 'Vacant':
        print(i, flush=True)
        exit()
    elif s == 'Male':
        L[i] = 1
    else:
        L[i] = 2

    i = N // 2
    print(i, flush=True)
    s = str(input())
    if s == 'Vacant':
        print(i, flush=True)
        exit()
    elif s == 'Male':
        L[i] = 1
    else:
        L[i] = 2

    # リストAをとってkeyのある添字を返す
    # なかったら-1
    def bin_search(pl,pr):

        while pl <= pr:
            pc = (pl + pr) // 2
            print(pc, flush=True)

            s = str(input())
            if s == 'Vacant':
                print(pc, flush=True)
                exit()
            elif s == 'Male':
                L[pc] = 1
            else:
                L[pc] = 2

            if abs(L[pr] - L[pc]) == 0 and (pr-pc)%2==1:
                pr = pc - 1
            else:
                pl = pc + 1

    if abs(L[N // 2] - L[0]) == 0 and (N//2%2==1):
        bin_search(0,N//2)
    else:
        bin_search(N//2+1, N-1)





resolve()

### FIXED CODE ###

N = int(input())


def query(i):
    print(i)
    s = input()
    if s == 'Vacant':
        exit()
    return s


root = query(0)


def is_ok(ind):
    # 左ならTrue
    response = query(ind)
    if ind % 2 == 1:
        return root == response
    else:
        return root != response


def bin_search_meguru():
    """
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng, okは,とり得る最小の値-1,とり得る最大の値+1
    """

    # 適当にいじる
    ng = -1  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()
### BUGGY CODE ###

from operator import itemgetter
import heapq

N = int(input())
pos = [[int(p) for p in input().split()] for _ in range(N)]

pos.sort()
for i in range(N):
    pos[i].append(i)
    
Y = sorted(pos, key=itemgetter(1))
Y_idx = [0]*N
for i in range(N):
    Y_idx[Y[i][2]] = i
    
ans = 0
used = [0]*N
used[0] = 1
h = []
c = 1
idx = Y_idx[0]
heapq.heappush(h, (pos[c][0]-pos[c-1][0], 1))
if idx > 0:
    heapq.heappush(h, (Y[idx][1]-Y[idx-1][1], Y[idx-1][2]))
if idx < N-1:
    heapq.heappush(h, (Y[idx+1][1]-Y[idx][1], Y[idx+1][2]))
    
cnt = 0
while cnt < N-1:
    t = heapq.heappop(h)
    if used[t[1]] == 1:
        continue
    c = t[1]
    used[c] = 1
    cnt += 1
    ans += t[0]
    if c > 0 and used[c-1] == 0:
        heapq.heappush(h, (pos[c][0]-pos[c-1][0], c-1))
    if c < N-1 and used[c+1] == 0:
        heapq.heappush(h, (pos[c+1][0]-pos[c][0], c+1))
    idx = Y_idx[c]
    if idx > 0 and used[Y[idx-1][2]] == 0:
        heapq.heappush(h, (Y[idx][1]-Y[idx-1][1], Y[idx-1][2]))
    if idx < N-1 and used[Y[idx+1][2]] == 0:
        heapq.heappush(h, (Y[idx+1][1]-Y[idx][1], Y[idx+1][2]))
            
print(ans)

### FIXED CODE ###

from operator import itemgetter
import heapq

N = int(input())
X = [[int(p) for p in input().split()] for _ in range(N)]

X.sort()
for i in range(N):
    X[i].append(i)
    
Y = sorted(X, key=itemgetter(1))

h = []
for i in range(N-1):
    heapq.heappush(h, (X[i+1][0]-X[i][0], i+1, i))
    heapq.heappush(h, (Y[i+1][1]-Y[i][1], Y[i+1][2], Y[i][2]))
    
    
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        
    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
        
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1
                
    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)
    
    def count(self, x):
        return -self.root[self.find_root(x)]
    
    
UF = UnionFind(N)
ans = 0
while h:
    t = heapq.heappop(h)
    if UF.isSameGroup(t[1], t[2]):
        continue
    ans += t[0]
    UF.unite(t[1], t[2])
    
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
num = []
for i in range(1,N):
  num.append(abs(sum(A[:i]) - sum(A[i:])))
print(min(num))


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
X = sum(A)
x = 0
result = []
for i in range(N-1):
  x += A[i]
  result.append(abs(X - 2*x))
print(min(result))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(4100000)
import math
import itertools
INF = float('inf')
from heapq import heapify, heappop, heappush


n,m = map(int, input().split())
par = [i for i in range(n)]
rank = [0]*n

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

def main():
    for _ in range(m):
        a,b = map(int, input().split())
        unite(a-1,b-1)
    ans = 0
    for i in range(len(par)):
        tmp = 0
        for j in range(len(par)):
            if par[j] == i:
                tmp += 1
        ans = max(ans, tmp)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(4100000)
import math
import itertools
INF = float('inf')
from heapq import heapify, heappop, heappush
import collections


n,m = map(int, input().split())
par = [i for i in range(n)]
rank = [0]*n

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

def main():
    for _ in range(m):
        a,b = map(int, input().split())
        unite(a-1,b-1)

    count = [0]*n
    for p in par:
        count[find(p)] += 1
    print(max(count))


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

import sys
from operator import mul
from functools import reduce
stdin = sys.stdin

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

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


n = ni()
a = na()
a.sort()
r = a[-1]
ans = -1
for i in range(n):
    num = cmb(r, a[i])
    if ans < num:
        ans = num
    else:
        print(r, a[i-1])
        break



### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter
#from heapq import heappush, heappop
#import numpy as np
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix
#from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

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

n = ni()
a = na()
a.sort(reverse=True)
ans = -1
t = a[0]
target = (a[0] + (2 - 1)) // 2
#print(target)
pre = inf
if n == 2:
    print(max(a), min(a))
    sys.exit()
for i in range(1, n):
    #print(pre)
    dif = abs(target - a[i])
    if pre < dif:
        print(t, a[i-1])
        sys.exit()
    else:
        pre = dif
### BUGGY CODE ###

import collections
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]
dp = [[H+W]*W for i in range(H)]

q = collections.deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            dp[i][j] = 0
            q.append([i, j])


while(q):
    x, y = q.popleft()
    if x > 0:
        if dp[x-1][y] > dp[x][y]+1:
            if A[x-1][y] == ".":
                dp[x-1][y] = dp[x][y]+1
            else:
                dp[x-1][y] = 0
            q.append([x-1, y])
    if x < H-1:
        if dp[x+1][y] > dp[x][y]+1:
            if A[x+1][y] == ".":
                dp[x+1][y] = dp[x][y]+1
            else:
                dp[x+1][y] = 0
            q.append([x+1, y])
    if y > 0:
        if dp[x][y-1] > dp[x][y]+1:
            if A[x][y-1] == ".":
                dp[x][y-1] = dp[x][y]+1
            else:
                dp[x][y-1] = 0
            q.append([x, y-1])
    if y < W-1:
        if dp[x][y+1] > dp[x][y]+1:
            if A[x][y+1] == ".":
                dp[x][y+1] = dp[x][y]+1
            else:
                dp[x][y+1] = 0
            q.append([x, y+1])
ans = 0
for i in range(H):
    ans = max(ans, max(dp[i]))
print(ans)


### FIXED CODE ###

import collections
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]
dp = [[H+W]*W for i in range(H)]

q = collections.deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            dp[i][j] = 0
            q.append([i, j])
            break
    if q:
        break


while(q):
    x, y = q.popleft()
    if x > 0:
        if dp[x-1][y] > dp[x][y]+1:
            if A[x-1][y] == ".":
                dp[x-1][y] = dp[x][y]+1
            else:
                dp[x-1][y] = 0
            q.append([x-1, y])
    if x < H-1:
        if dp[x+1][y] > dp[x][y]+1:
            if A[x+1][y] == ".":
                dp[x+1][y] = dp[x][y]+1
            else:
                dp[x+1][y] = 0
            q.append([x+1, y])
    if y > 0:
        if dp[x][y-1] > dp[x][y]+1:
            if A[x][y-1] == ".":
                dp[x][y-1] = dp[x][y]+1
            else:
                dp[x][y-1] = 0
            q.append([x, y-1])
    if y < W-1:
        if dp[x][y+1] > dp[x][y]+1:
            if A[x][y+1] == ".":
                dp[x][y+1] = dp[x][y]+1
            else:
                dp[x][y+1] = 0
            q.append([x, y+1])
ans = 0
for i in range(H):
    ans = max(ans, max(dp[i]))
print(ans)