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

import sys
from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)  # The number of nodes under the target node.

    def find(self, x):
        if self.root[x] == x:
            return x
        else:
            y = self.find(self.root[x])
            self.root[x] = y
            return self.root[x]

    def unite(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.root[rx] = ry
            self.size[ry] += self.size[rx]
        else:
            self.root[ry] = rx
            self.size[rx] += self.size[ry]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    

def main():
    input = sys.stdin.readline
    N, K, L = map(int, input().split())
    road = UnionFind(N)
    rail = UnionFind(N)

    for _ in range(K):
        p, q = map(int, input().split())
        road.unite(p-1, q-1)

    for _ in range(L):
        r, s = map(int, input().split())
        rail.unite(r-1, s-1)

    road_r = defaultdict(set)
    rail_r = defaultdict(set)
    for i in range(N):
        road_r[road.find(i)].add(i)
        rail_r[rail.find(i)].add(i)

    ans = [0 for _ in range(N)]
    for i in range(N):
        ans[i] = len(road_r[road.root[i]] & rail_r[rail.root[i]])

    return print(*ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    def find(self, x):
        if self.root[x] == x:
            return x
        else:
            y = self.find(self.root[x])
            self.root[x] = y
            return self.root[x]

    def unite(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.root[rx] = ry
        else:
            self.root[ry] = rx
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    

def main():
    input = sys.stdin.readline
    N, K, L = map(int, input().split())
    road = UnionFind(N)
    rail = UnionFind(N)

    for _ in range(K):
        p, q = map(int, input().split())
        road.unite(p-1, q-1)

    for _ in range(L):
        r, s = map(int, input().split())
        rail.unite(r-1, s-1)

    d = defaultdict(lambda: 0)
    for i in range(N):
        n = road.find(i)
        m = rail.find(i)
        d[(n, m)] += 1

    ans = []
    for i in range(N):
        n = road.find(i)
        m = rail.find(i)
        ans.append(d[(n, m)])

    return print(*ans)


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

from collections import deque
n, m = map(int, input().split())
e = [int(input()) for _ in range(m)]
d = deque(i for i in range(1, n+1))
for v in e[::-1]:
    try:
        d.remove(v)
        print(v)
    except ValueError:
        pass
while d:
    print(d.popleft())

### FIXED CODE ###

n, m = map(int, input().split())
e = [int(input()) for _ in range(m)]
b = [1] * (n+1)
for v in e[::-1]:
    if b[v]:
        b[v] = 0
        print(v)
for i in range(1, n+1):
    if b[i]:
        print(i)
### BUGGY CODE ###

def main():
    N,K = map(int, input().split())
    p = list(map(int, input().split()))
    sums = [ sum(p[i:i+K]) for i in range(N-K+1) ]
    print(  ( max(sums)+K)*0.5  )
    return

if __name__=="__main__":
    main()

### FIXED CODE ###

def main():
    N,K = map(int, input().split())
    p = list(map(int, input().split()))
    if N>K:
        esum = [0]*N
        psum = [0]*(N-K)
        esum[0] = p[1]
        for i in range(1,K):
            esum[i] = esum[i-1]+p[i]
        for i in range(K,N):
            esum[i] = esum[i-1]+p[i]
            psum[i-K] = esum[i]-esum[i-K]
        ans = (max(psum)+K)*0.5
    else:
        ans = (sum(p)+K)*0.5

    print(ans)
    return

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

import itertools

# 8通りの方法を調べて最大値　-,-,- から +,+,+
N, M = map(int, input().split())

data = [[0] * 8 for _ in range(M+1)]
p = list(itertools.product([-1, 1], repeat=3))

for i in range(N):
    #print(data)
    x, y, z = map(int, input().split())
    for k in range(M-1, -1, -1):
        for j in range(8):
            tmp = x * p[j][0] + y * p[j][1] + z * p[j][2]
            if data[k+1][j] < data[k][j] + tmp:
                data[k+1][j] = data[k][j] + tmp
answer = 0
for d in data[M]:
    if abs(d) > answer:
        answer = abs(d)
print(answer)

### FIXED CODE ###

import itertools

def main():
    # 8通りの方法を調べて最大値　-,-,- から +,+,+
    N, M = map(int, input().split())

    data = [[] for i in range(8)]
    p = list(itertools.product([-1, 1], repeat=3))

    for i in range(N):
        #print(data)
        x, y, z = map(int, input().split())
        for j in range(8):
            tmp = x * p[j][0] + y * p[j][1] + z * p[j][2]
            data[j].append(tmp)
               
    answer = 0
    for d in data:
        d.sort(reverse=True)
        s = sum(d[:M])
        if abs(s) > answer:
            answer = abs(s)
    print(answer)

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

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

for i in range(M):
  b, c = map(int, input().split())
  A.extend([c]*b)
A.sort(reverse=True)
ans = sum(A[:N])
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
A = [int(i) for i in input().split()]
table = []
for i in range(N):
  table.append((A[i],1))
for i in range(M):
  b,c = map(int, input().split())
  table.append((c,b))
table.sort()
count = 0
ans = 0
while True:
  c, b = table.pop()
  if b <= N - count:
    ans += c*b
    count += b
  else:
    ans += (N-count)*c
    break
print(ans)
### BUGGY CODE ###

n = int(input())
A = sorted(list(map(int, input().split())))
flags = [1] * n
for i in range(1, n):
    for j in range(i):
        if A[i] == A[j]:
            flags[i] = 0
            flags[j] = 0
        if A[i] % A[j] == 0:
            flags[i] = 0
            break
print(sum(flags))

### FIXED CODE ###

n = int(input())
A = sorted(list(map(int, input().split())))
M = 10**6 + 1
L = [0]*M
for a in A:
    L[a] += 1
    if L[a] == 1:
        # k>=2として k*aは全て不適
        for i in range(2*a, M, a):
            L[i] += 2
# flagの数が答え
print(L.count(1))
### BUGGY CODE ###

# coding: utf-8
# Your code here!

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

dp = [9999999999 for i in range(len(h))]
dp[0] = 0

# print(dp)

for i in range(len(h)):
    # print(i)
    for j in range(1, k + 1):
        if i + j < len(dp):
            dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]))
            # print(dp)
        
print(dp[len(dp) - 1])

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    a = [0] * n
    a[0] = 0
    for i in range(1, n):
        a[i] = min([a[j] + abs(h[i] - h[j]) for j in range(max(0, i - k), i)])
    print(a[-1])
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():  
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A = [a - 1 for a in A]
    X = K.bit_length()
    to = [[-1] * X for _ in range(N)]
    for i,a in enumerate(A):
        to[i][0] = a
    for i in range(X - 1):
        for j in range(N):
            to[j][i + 1] = to[to[j][i]][i]
    now = 0
    i = 0
    while K > 0:
        if K&1:
            now = to[now][i]
        i += 1
        K >>= 1
    print(now + 1)
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():  
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A = [a - 1 for a in A]
    visited = {0}
    loop = [0]
    now = 0
    while A[now] not in visited:
        now = A[now]
        visited.add(now)
        loop.append(now)
    
    for i,s in enumerate(loop):
        if s == A[now]:
            X = loop[:i]
            loop = loop[i:]
            break
    if K < len(X):
        print(X[K] + 1)
    else:
        K -= len(X)
        K %= len(loop)
        print(loop[K] + 1)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
l = []
r = []
for i in range(q):
    L,R = map(int,input().split())
    l.append(L)
    r.append(R)
index = []
for i in range(n-1):
    if i != n-2 and s[i:i+2] == "AC":
        index.append(i)
    elif s[i:] == "AC":
        index.append(i)

for i in range(q):
    count = 0
    for j in range(len(index)):
        if l[i]-1 <= index[j] and index[j] + 1 <= r[i]-1:
            count += 1
    print(count)

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
count = 0
index = [0 for i in range(n)]
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        count += 1
    index[i+1] = count
L = []
R = []
for i in range(q):
    l,r = map(int,input().split())
    L.append(l)
    R.append(r)
for i in range(q):
    print(index[R[i]-1]-index[L[i]-1])
### BUGGY CODE ###

N = int(input())

# 昇順にする
g_data_list = list(map(int, input().split()))
data_list = sorted(g_data_list)

cnt = 0
for i in range(N):

	# 同じ数字
	if(data_list.count(data_list[i]) != 1):
		continue

	is_divide = False
	for j in range(i):
		# 割り切れる数がある
		if(data_list[i] % data_list[j] == 0):
			is_divide = True
			break
	if(not is_divide):
		cnt += 1

print(cnt)

### FIXED CODE ###

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

# 0 ~ 10**6に入力値の個数を入れる
# (count()で数えると、o(n**2)になるため)
val_list = [0 for i in range(10**6+1)]
for i in a_l:
	val_list[i] += 1

# 重複削除
a_l = list(set(a_l))

# 0 ~ 10**6のリスト
A_list = [True for i in range(10**6+1)]
# 倍数のところにFalseを入れる
for i in a_l:
	for j in range(i*2, 10**6+1, i):
		A_list[j] = False

# Trueと一致するa_lの個数を数える
cnt = 0
for i in a_l:
	if(val_list[i] != 1):
		continue
	if(A_list[i]):
		cnt += 1

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

r,g,b,n=map(int,input().split())
ctr=0

num_r=n//r+1
num_g=n//g+1

for i in range(num_r):
    for k in range((n-i*r)//g+1):
        if n-r*i-g*k>=0 and (n-r*i-g*k)%b==0:
            ctr+=1
print(ctr)


### FIXED CODE ###

r,g,b,n=map(int,input().split())
ctr=0
l=[r,g,b]
l.sort()
num_1=n//l[2]+1
for i in range(num_1):
    for k in range((n-i*l[2])//l[1]+1):
        if (n-i*l[2]-k*l[1])%l[0]==0:
            ctr+=1
print(ctr)
### BUGGY CODE ###

N,K=[int(i) for i in input().split()]
R,S,P=[int(i) for i in input().split()]
T=list(input())
M={"r":P,"s":R,"p":S}

done=[]
point=0
for i in range(K):
    temp=T.pop(0)
    point+=M[temp]
    done.append(temp)

# print(T)
# print(done)

while T:
    temp=T.pop(0)
    back=done.pop(0)
    # print(temp,back)
    if temp!=back:
        point+=M[temp]
        done.append(temp)
    else:
        done.append('u')

print(point)


### FIXED CODE ###

N,K=[int(i) for i in input().split()]
R,S,P=[int(i) for i in input().split()]
T=list(input())
M={"r":P,"s":R,"p":S}

done=[]
point=0
for i in range(K):
    temp=T[i]
    point+=M[temp]
    done.append(temp)

# print(T)
# print(done)

for j in range(K,N):
    temp=T[j]
    back=done[j-K]
    # print(temp,back)
    if temp!=back:
        point+=M[temp]
        done.append(temp)
    else:
        done.append('u')

print(point)
### BUGGY CODE ###

def main():
    import sys

    input = sys.stdin.readline

    sys.setrecursionlimit(10 ** 7)

    def dfs(v, dist):
        for u in g[v]:
            if dist[u] == -1:
                dist[u] = dist[v] + 1
                dfs(u, dist)

    N, u, v = map(int, input().split())
    u -= 1
    v -= 1

    g = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        g[a].add(b)
        g[b].add(a)

    dist_from_a = [-1] * N
    dist_from_a[v] = 0
    dfs(v, dist_from_a)

    def dfs2(v, d):
        ret = d
        for u in g[v]:
            if dist_from_a[u] > d + 1:
                ret = max(ret, dfs2(u, d + 1))
            elif dist_from_a[u] == d + 1:
                ret = max(ret, d + 1)
        return ret

    print(dfs2(u, 0))


if __name__ == '__main__':
    main()

### FIXED CODE ###

# 解説を見た

def solve(N, t, a, g) -> int:
    import sys

    sys.setrecursionlimit(10 ** 7)

    def calc_dist(init):
        dist = [-1] * N
        dist[init] = 0

        def _calc_dist(curr):
            for next_ in g[curr]:
                if dist[next_] != -1:
                    continue
                dist[next_] = dist[curr] + 1
                _calc_dist(next_)

        _calc_dist(init)
        return dist

    dist_a = calc_dist(a)
    dist_t = calc_dist(t)

    return max(dist_a[v] for v in range(N) if dist_t[v] < dist_a[v]) - 1


if __name__ == '__main__':
    N, t, a = map(int, input().split())
    t -= 1
    a -= 1

    g = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        u, v = (int(x) - 1 for x in input().split())
        g[u].add(v)
        g[v].add(u)

    print(solve(N, t, a, g))

# 青木君からの距離 > 高橋君からの距離 となる頂点Xが目的地の候補
# 青木君と高橋君の共通祖先からの距離は等しいので、
# 共通祖先への距離は、 青木君 > 高橋君 となり、高橋君は必ずXに到達できる
# Xに着いた高橋君は、手前の頂点とXとを行ったり来たりする
# a-t->at-: aが一歩進んだときに高橋君に会う(-は無人のマス目)
# at: tが手前の頂点に移動したときに青木君に会う
# いずれも手前の頂点まで青木君が移動したときにゲームが終わる
# どのXを選んでも、Xの手前でゲームが終わるので、青木君から最も遠いXを選ぶのが最善
# 頂点X: 追いつめられる位置=葉
### BUGGY CODE ###

n,k = map(int,input().split())
h = sorted(list(map(int,input().split())), reverse=True)
if k >= n:
  print(0)
else:
  for i in range(k):
    h.pop(0)
  print(sum(h))

### FIXED CODE ###

n,k = map(int,input().split())
h = sorted(list(map(int,input().split())), reverse=True)
if k >= n:
  print(0)
else:
  del h[:k]
  print(sum(h))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
L = [list(map(int, input().split())) for _ in range(Q)]
for l in L:
  print(S[l[0]-1:l[1]].count("AC"))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
L = [list(map(int, input().split())) for _ in range(Q)]
t, I = 0, [0]
for i in range(1, N):
  if S[i-1]=="A":
    if S[i]=="C":
      t += 1
  I.append(t)
for l in L:
  print(I[l[1]-1]-I[l[0]-1])
### BUGGY CODE ###

from collections import Counter
 
n = int(input())
A = sorted(map(int, input().split()))
c = Counter(A)
flag = [True] * n
for i in range(n):
    if flag[i] == True:
        for j in range(i+1, n):
            if A[j] % A[i] == 0:
                flag[j] = False
    if c[A[i]] > 1:
        flag[i] = False
print(flag.count(True))


### FIXED CODE ###

from collections import Counter
n = int(input())
A = sorted(map(int, input().split()))
M = A[-1]
c = Counter(A)
s = set()
ans = 0
for a in A:
    if a in s:
        continue
    if c[a] == 1:
        ans += 1
    i = 1
    while a * i <= M:
        s.add(a * i)
        i += 1
print(ans)
### BUGGY CODE ###

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

for i in range(N):
    c=0
    for j in range(N):
        if A[i] == A[j]:
            c+=1
    c-=1
    b.append(c)
    a+=c
a /= 2
for i in range(N):
    print(int(a)-b[i])

### FIXED CODE ###

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

cnt = [0] * n
for i in a:
    cnt[i-1] += 1
t=0
for i in cnt:
    t += i * (i-1)
t/=2
for i in a:
    print(int(t-(cnt[i-1]-1)))
### BUGGY CODE ###

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

print(ans)


### FIXED CODE ###

k,s=map(int,input().split())
ans=0

for x in range(k+1):
    for y in range(k+1):
        if s-x-y>=0 and k>=(s-x-y):
            ans+=1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

class Unionfind:

    __slots__ = ['nodes','size']

    def __init__(self, n):
        self.nodes = list(range(n))
        self.size = [1]*n

    def root(self, x):
        if self.nodes[x] == x:
            return x
        else:
            root_x = self.root(self.nodes[x])
            self.nodes[x] = root_x
            return root_x

    def unite(self, x, y):
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.size[x] += self.size[y]
        self.nodes[y] = x

    def same(self, x, y):
        return self.root(x) == self.root(y)

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

uf1 = Unionfind(N)
uf2 = Unionfind(N)

for _ in range(K):
    p,q = map(int,input().split())
    p -= 1; q -= 1
    uf1.unite(p,q)

for _ in range(L):
    r,s = map(int,input().split())
    r -= 1; s -= 1
    uf2.unite(r,s)

set1 = [set() for _ in range(N)]
set2 = [set() for _ in range(N)]

for node in range(N):
    set1[node] = set1[uf1.root(node)]
    set1[node].add(node)
    set2[node] = set2[uf2.root(node)]
    set2[node].add(node)

for node in range(N):
    out = len(set1[node] & set2[node])
    if node == N-1:
        print(out)
    else:
        print(out,end = " ")

### FIXED CODE ###

import sys
input = sys.stdin.readline

class Unionfind:

    __slots__ = ['nodes','size']

    def __init__(self, n):
        self.nodes = list(range(n))
        self.size = [1]*n

    def root(self, x):
        if self.nodes[x] == x:
            return x
        else:
            root_x = self.root(self.nodes[x])
            self.nodes[x] = root_x
            return root_x

    def unite(self, x, y):
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.size[x] += self.size[y]
        self.nodes[y] = x

    def same(self, x, y):
        return self.root(x) == self.root(y)

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

uf1 = Unionfind(N)
uf2 = Unionfind(N)

for _ in range(K):
    p,q = map(int,input().split())
    p -= 1; q -= 1
    uf1.unite(p,q)

for _ in range(L):
    r,s = map(int,input().split())
    r -= 1; s -= 1
    uf2.unite(r,s)

keys = []
dic = {}

for node in range(N):
    key = (uf1.root(node),uf2.root(node))
    keys.append(key)
    if key in dic:
        dic[key] += 1
    else:
        dic[key] = 1

ans = [str(dic[key]) for key in keys]
print(" ".join(ans))
### BUGGY CODE ###

lst=[]
L,R = map(int, input().split())

for i in range(L,R):
    for j in range(i+1,R+1):
        lst.append(int((i*j)%2019))
print(min(lst))

### FIXED CODE ###

lst=[]
L,R = map(int, input().split())

if R-L>=2019:
    print(0)
else:
    for i in range(L,R):
        for j in range(i+1,R+1):
            lst.append(int((i*j)%2019))
    print(min(lst))
### BUGGY CODE ###

import itertools
anslist = []
_ = input()
S = input()
l = [i for i in S]
for c  in itertools.combinations(l, 3):
    
    anslist.append(c)

print(len(set(anslist)))


### FIXED CODE ###

_ = input()
S = input()
counter = 0

for i in range(10):
    for j in range(10):
        for k in range(10):
            idxi = S.find(str(i))
            if idxi ==-1:
                continue
            idxj = S.find(str(j),idxi+1)
            if idxj == -1:
                continue
            idxk = S.find(str(k),idxj+1)
            if idxk == -1:
                continue
            counter+=1
print(counter)
### BUGGY CODE ###

n=int(input())
b=0
c=0
d=0
e=0
list=[]
list2=[]
for i in range(n):
    s=input()
    list.append(s)
for x in list:
    b=list.count(x)
    if b>=c:
        c=b
for x in list:
    if c==list.count(x):
        list2.append(x)
e=len(list2)
for i in range(e):
    if list2.count(list2[d])>=2:
        list2.remove(list2[d])
    else:
        d+=1
list2.sort()
for x in list2:
    print(x)


### FIXED CODE ###

from collections import Counter
n=int(input())
list=[input() for _ in range(n)]
list.sort()
c=Counter(list).most_common()
most=c[0][1]
c.sort()
for i in range(len(c)):
    if c[i][1]==most:
        print(c[i][0])
### BUGGY CODE ###

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

for i in range(n):
    ans = 0
    a_i = a.copy()
    a_i.pop(i)
    for j in range(n-2):
        ans += abs(a_i[j+1] - a_i[j])
    ans += abs(a_i[0])
    ans += abs(a_i[-1])
    

    print(ans)





### FIXED CODE ###

n = int(input())

a = [0] + list(map(int, input().split())) + [0]

s = 0



for i in range(n+1):
    s += abs(a[i+1] - a[i])

for i in range(1,n+1):
    if (a[i] - a[i-1])*(a[i+1] - a[i]) < 0:
        if abs(a[i] - a[i-1]) < abs(a[i+1] - a[i]):
            print(s - 2*abs(a[i] - a[i-1]))
        else:
            print(s - 2*abs(a[i+1] - a[i]))
    else :
        print(s)
### BUGGY CODE ###

def main():
    import sys
    from bisect import bisect_left
    from array import array
    I=10**9+1
    n,*t=sys.stdin.readlines()
    n,q=map(int,n.split())
    *d,=map(int,t[n:])
    z=[]
    for t in t[:n]:
        s,t,x=map(int,t.split())
        z.append((x,bisect_left(d,s-x),bisect_left(d,t-x)))
    z.sort(reverse=1)
    N0=2**(q+1).bit_length()
    data=array('I',[I]*2*N0)
    for x,l,r in z:
        L,R=l+N0,r+N0
        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(q):
        k+=N0-1
        s=I
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//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 ###

from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 6)
Hitpoint, N = map(int, input().split())
magic_damage = []
magic_point = []
dp = [[0] * (N + 1) for _ in range(N)]
for _ in range(N):
    A, B = map(int ,input().split())
    magic_damage.append(A)
    magic_point.append(B)

@lru_cache(maxsize=None)
def solve(i , now_HP):
    if now_HP <= 0:
        retval = 0
    elif i == N:
        retval = float('inf')
    else:
        retval = min(solve(i + 1 , now_HP) , solve(i, now_HP - magic_damage[i]) + magic_point[i])

    return retval
ans = solve(0, Hitpoint)
print(ans)


### FIXED CODE ###

import math
H, N = map(int, input().split())
dp = [[0 for _ in range(H + 1)] for _ in range(N)]
A, B = map(int, input().split())
for i in range(H + 1):
    cnt = math.ceil(i / A)
    dp[0][i] = B * cnt

for i in range(1, N):
    A, B = map(int, input().split())
    for j in range(H + 1):
        dp[i][j] = min(dp[i - 1][j], dp[i][max(j - A, 0)] + B)
# print(*dp, sep='\n')
print(dp[-1][-1])
### BUGGY CODE ###

import math


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


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

ans = 0
a_i = a[0]
a_j = a[1]
for idx in range(1, n):
    if ans < combinations_count(a_i, a[idx]):
        ans = combinations_count(a_i, a[idx])
        a_j = a[idx]

print("%d %d" % (a_i, a_j))


### FIXED CODE ###

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

max_a = max(a)
a.remove(max_a)
da = [abs(ai - max_a / 2) for ai in a]
med_i = da.index(min(da))

print("%d %d" % (max_a, a[med_i]))