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

# import math


def trial_division(n):
    # 素因数を格納するリスト
    factor = set()
    # 2から√n以下の数字で割っていく
    # tmp = int(math.sqrt(n)) + 1
    for num in range(2, n+1):
        while n % num == 0:
            n //= num
            factor.add(num)
    # リストが空ならそれは素数
    if not factor:
        return set((1, n))
    else:
        factor.add(n)
        return factor


A, B = map(int, input().split())
# print(trial_division(A))
# print(trial_division(B))
print(len(trial_division(A) & trial_division(B)))


### FIXED CODE ###

import math


def trial_division(n):
    # 素因数を格納するリスト
    factor = set()
    # 2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            factor.add(num)
    # リストが空ならそれは素数
    if not factor:
        return set((1, n))
    else:
        factor.add(n)
        factor.add(1)
        return factor


A, B = map(int, input().split())
# print(trial_division(A))
# print(trial_division(B))
print(len(trial_division(A) & trial_division(B)))
### BUGGY CODE ###

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

A = [0] * N
B = [0] * N

for i in range(N):
  a, b = [int(x) for x in input().split()]
  A[i] = a
  B[i] = b
  
money = 0

while True:
  idx = A.index(min(A))
  a = A.pop(idx)
  b = B.pop(idx)
  if M <= b:
    break
  else:
    money += a * b
    M -= b
money += a * M
print(money)

### FIXED CODE ###

N, M = [int(x) for x in input().split()]
V = [tuple(map(int, input().split())) for i in range(N)]
V.sort()

money = 0
count = 0

for a, b in V:
  if count + b < M:
    count += b
    money += a * b
  else:
    money += (M - count) * a
    break
print(money)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


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


X = readint()
l = make_divisors(X)

ans_A = 0
ans_B = 0
for n in l:
    # n = A - B
    A = 0
    B = A - n
    while A != n:
        if A ** 5 - B ** 5 == X:
            ans_A = A
            ans_B = B
            break
        else:
            A += 1
            B += 1

    if ans_A:
        break


print(ans_A, ans_B)


### FIXED CODE ###

import sys
input = sys.stdin.readline


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)

    divisors.sort()
    return divisors


def check(x, y):
    return x ** 4 + x ** 3 * y + x ** 2 * y ** 2 + x * y ** 3 + y ** 4


X = readint()
l = make_divisors(X)

ans_A = 0
ans_B = 0
for n in l:
    # n = A - B
    A = n // 2
    B = A - n
    while A ** 5 - B ** 5 <= X:
        if check(A, B) == (X // n):
            ans_A = A
            ans_B = B
            break
        else:
            A -= 1
            B -= 1

    if ans_A:
        break


print(ans_A, ans_B)
### BUGGY CODE ###

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
    def main(self):
      return max([len(self.members(r)) for r in self.roots()])
uf = UnionFind(N)

for _ in range(M):
  A, B  = map(int, input().split())
  uf.union(A-1,B-1)
  
#L = list(uf.all_group_members().values())

#ans = max( [ len(l) for l in L ] )
#print(ans)
print(uf.main())

### FIXED CODE ###

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
    def main(self):
      return max([len(self.members(r)) for r in self.roots()])
uf = UnionFind(N)

for _ in range(M):
  A, B  = map(int, input().split())
  uf.union(A-1,B-1)
  
print(-min(uf.parents))
### BUGGY CODE ###

import collections

n = int(input())

f = [1] * (n + 1)
for i in range(2, n + 1):
    if f[i] != 1: continue
    m = i
    while m <= n:
        tmp = m
        cnt = 0
        while tmp % i == 0:
            tmp = tmp // i
            cnt += 1
        f[m] *= cnt + 1
        m += i

ans = 0
for i in range(1, n + 1):
    ans += i * f[i]
print(ans)


### FIXED CODE ###

import collections

n = int(input())

f = [1] * (n + 1)
for i in range(2, n + 1):
    if f[i] != 1: continue
    m = i
    while m <= n:
        tmp = m
        cnt = 0
        while tmp % i == 0:
            tmp = tmp // i
            cnt += 1
        f[m] *= cnt + 1
        m += i

ans = 0
for i in range(1, n + 1):
    ans += i * f[i]
print(ans)
### BUGGY CODE ###

import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], i8, i8), cache=True)
def test(A, keta, n):
    # 10^keta の位を n にできるか
    MOD = 10**(keta + 1)
    I = [(n * 10**keta, (n + 1) * 10**keta)]  # [l, r)
    for x in A:
        if I[0][0] == 0:
            return True
        newI = I.copy()
        x %= MOD
        for l, r in I:
            l, r = l + MOD - x, r + MOD - x
            if l >= MOD:
                l, r = l - MOD, r - MOD
            if r <= MOD:
                newI.append((l, r))
            else:
                newI.append((l, MOD))
                newI.append((0, r - MOD))
        I = newI
        I.sort(key=lambda x: x[1])
        newI = [(0, 0)] * 0
        for x, y in I:
            while newI and newI[-1][1] >= x:  # つなぐ
                x, y = min(x, newI[-1][0]), y
                newI.pop()
            newI.append((x, y))
        I = newI
    return I[0][0] == 0

def main(A):
    N = len(A)
    ans = 0
    for keta in range(18):
        for x in range(9, 0, -1):
            if test(A, keta, x):
                ans += x
                break
    return ans

A = np.array(read().split(), np.int64)[1:]
np.random.shuffle(A)
print(main(A))

### FIXED CODE ###

import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], i8), cache=True)
def solve(A, keta):
    # 10^keta の位を n にできるか
    MOD = 10**(keta + 1)
    B = 10**keta
    nums = [0]
    for x in A:
        x %= MOD
        n = len(nums)
        for i in range(n):
            s = nums[i] + x
            if s >= MOD:
                s -= MOD
            nums.append(s)
        nums.sort()
        # x, y, z とあって、x + z < B ならば、y は捨ててよい
        tmp = []
        for x in nums:
            while len(tmp) >= 2 and tmp[-2] + B > x:
                tmp.pop()
            tmp.append(x)
        nums = tmp
    return nums[-1] // B

def main(A):
    N = len(A)
    ans = 0
    for keta in range(18):
        x = solve(A, keta)
        ans += x
    return ans

A = np.array(read().split(), np.int64)[1:]
np.random.shuffle(A)
print(main(A))
### BUGGY CODE ###

s = input()
k = int(input())
n = len(s)
for i in range(n):
  num = ord(s[i])
  if num == 97 or 123-num > k:
    continue
  k -= (123-num)
  s = bytearray(s.encode())
  s[i] = 97
  s = s.decode()
if k > 0:
  t = k%26
  s = bytearray(s.encode())
  s[n-1] += t
  s = s.decode()
print(s)

### FIXED CODE ###

s = input()
k = int(input())
n = len(s)
for i in range(n):
  num = ord(s[i])
  if num == 97 or 123-num > k:
    continue
  k -= (123-num)
  s = s[:i] + 'a' + s[i+1:]
if k > 0:
  t = k%26
  s = s[:n-1] + chr(ord(s[n-1])+t)
print(s)
### BUGGY CODE ###

n=int(input())
ls=list(map(int,input().split()))
count_ls=[0]*n
answers=[]
m=0

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.remove(n)
    return divisors

for i in range(n,0,-1):
    plus_flag=False
    idx=i-1
    if count_ls[idx]%2!=ls[idx]:
        plus_flag=True
        m+=1
        answers.append(i)
    if plus_flag:
        divisors=set(make_divisors(i))
        for j in divisors:
            j_idx=j-1
            count_ls[j_idx]+=1

print(m)
if m:
    print(" ".join(list(map(str,answers))))

### FIXED CODE ###

n=int(input())
ls=list(map(int,input().split()))
count_ls=[0]*n
answers=[]
m=0

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.remove(n)
    return divisors

for i in range(n,0,-1):
    plus_flag=False
    idx=i-1
    if count_ls[idx]%2!=ls[idx]:
        plus_flag=True
        m+=1
        answers.append(i)
    if plus_flag:
        divisors=set(make_divisors(i))
        for j in divisors:
            j_idx=j-1
            count_ls[j_idx]+=1

print(m)
if m:
    print(" ".join(list(map(str,answers))))
### BUGGY CODE ###

n,m,k=map(int,input().split())
par=[]
rank=[]
friends=[]
anti=[]
friend=[]
for i in range(n):
    par.append(i)
    rank.append(0)
    friends.append(set())
    anti.append(set())
    friend.append(set())
# this par & rank are initialized lists
def find_par(x):
    global par
    if par[x]==x:
        return x
    else:
        par[x]= find_par(par[x])
        return par[x]
def unite(x,y):
    x,y=find_par(x),find_par(y)
    global rank,par
    if x==y:return
    if rank[x]<rank[y]:
        par[x]=y
    else:
        par[y]=x
        if rank[x]==rank[y]:
            rank[x]+=1

for i in range(m):
    a,s=map(int,input().split())
    a-=1;s-=1
    unite(a,s)
    friend[a].add(s)
    friend[s].add(a)
for i in range(k):
    a,b=map(int,input().split())
    a-=1;b-=1
    anti[a].add(b)
    anti[b].add(a)
for i in range(n):
    find_par(i)
    friends[par[i]].add(i)
for i in range(n):
    print(len(friends[par[i]]-anti[i]-friend[i]-set([i])),end=" ")
print()

### FIXED CODE ###

n,m,k=map(int,input().split())
par=[-1]*n

# this par & rank are initialized lists
def find(x):
    global par
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
        
def unite(x,y):
    x,y=find(x),find(y)
    global par
    if x==y:return False
    else:
        if par[x]>par[y]:x,y=y,x
        par[x]+=par[y]
        par[y]=x
        return True

def size(x):
    return -par[find(x)]
def same(x,y):
    return find(x)==find(y)
from sys import stdin 
input=stdin.readline
friend=[0]*n
for i in range(m):
    a,s=map(int,input().split())
    a-=1;s-=1
    unite(a,s)
    friend[a]+=1
    friend[s]+=1
anti=[set() for i in range(n)]
for i in range(k):
    a,b=map(int,input().split())
    a-=1;b-=1
    anti[a].add(b)
    anti[b].add(a)

print(*[size(i)-1-sum(same(i,b) for b in anti[i])-friend[i] for i in range(n)],sep=" ")
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from pprint import pprint

INF = float('inf')

def solve(H: int, W: int, A: "List[str]"):
    count = [[INF] * (W + 2) for _ in range(H + 2)]
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                count[i + 1][j + 1] = 0
            else:
                count[i + 1][j + 1] = min(count[i][j + 1], count[i + 1][j]) + 1

    #pprint(count)
    ret = 0
    for i in range(H, 0, -1):
        for j in range(W, 0, -1):
            count[i][j] = min(count[i][j], min(count[i][j + 1], count[i + 1][j]) + 1)
            ret = max(ret, count[i][j])
    #pprint(count)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [next(tokens) for _ in range(H) ]  # type: "List[str]"
    solve(H, W, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from pprint import pprint

def solve(H: int, W: int, A: "List[str]"):
    used = [[False] * W for _ in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, -1, 0, 1]
    s = set()
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                s.add((i, j))
                used[i][j] = True

    ret = 0
    while True:
        nex = set()
        for x, y in s:
            for j in range(4):
                tx = x + dx[j]
                ty = y + dy[j]
                if 0 <= tx < H and 0 <= ty < W and not used[tx][ty]:
                    nex.add((tx, ty))
                    used[tx][ty] = True
        if len(nex) < 1:
            break
        s = nex
        ret += 1

    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [next(tokens) for _ in range(H) ]  # type: "List[str]"
    solve(H, W, A)

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

N,K=map(int,input().split())
ans=0

A=list(map(int,input().split()))
A=[A[j]%K for j in range(N)]
ans += A.count(1)

B=[(A[j]+A[j+1])%K for j in range(N-1)]
ans += B.count(2)

for i in range(2,min(K+1,N)):
    C = [(B[j]+B[j+1]-A[j+1])%K for j in range(N-i)]
    ans += C.count(i+1)
    A = B
    B = C
    
print(ans)
    


### FIXED CODE ###

import numpy
N,K=map(int,input().split())

if K==1:
    print(0)
    exit(0)

A=list(map(int,input().split()))
S=[0]+list(numpy.cumsum(A)) #累積和
S2=[(S[i]-i)%K for i in range(N+1)]

d = {}
ans = 0
for j in range(1,N+1):
    if j>K-1:
        if S2[j-K] in d:
            d[S2[j-K]] -= 1
        
    if S2[j-1] in d:
        d[S2[j-1]] += 1
    else:
        d[S2[j-1]] = 1
        
    if S2[j] in d:
        ans += d[S2[j]]
print(ans)
### BUGGY CODE ###

from collections import Counter
from fractions import gcd

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

g = gcd(a,b)

def sosuu(a):
    sosuu_list = set()
    sosuu_list.add(1)
    i = 2
    while 1:
        flag = True
        while a > i:
            if a % i == 0:
                # print(a,i)
                a = a//i
                sosuu_list.add(i)
                flag = False
            else:
                i += 1
        if flag:
            sosuu_list.add(a)
            return sosuu_list
        i += 1

a = sosuu(g)
print(len(a))

### FIXED CODE ###

from collections import Counter
from fractions import gcd

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

g = gcd(a,b)

def sosuu(a):
    sosuu_list = set()
    sosuu_list.add(1)
    i = 2
    while 1:
        flag = True
        while a >= i*i:
            if a % i == 0:
                # print(a,i)
                a = a//i
                sosuu_list.add(i)
                flag = False
            else:
                i += 1
        if flag:
            sosuu_list.add(a)
            return sosuu_list
        i += 1

a = sosuu(g)
print(len(a))
### BUGGY CODE ###

n = input()
a_list = input().split(" ")

b = [int(a) for a in a_list]
max = 10**9 + 7

sum = 0
for i in range(0, len(b)-1):
  for j in range(i+1, len(b)):
    sum += b[i] * b[j]
    while sum >= max:
      sum -= max
print(sum)


### FIXED CODE ###

n = input()
 
max = 10**9 + 7
 
a_list = [int(a) % max for a in input().split(" ")]
a_sum = sum(a_list)

total = 0
for i in range(0, len(a_list)-1):
    a_sum -= a_list[i]
    total += a_list[i] * a_sum
total = total % max
print(total)
### BUGGY CODE ###

from fractions import Fraction
from math import ceil, floor

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

def isOk(x):
    cnt = 0
    for a in A:
        cnt += floor(Fraction(a, x))
    return cnt <= K

ok = max(A)
ng = 0
for _ in range(50):
    mid = Fraction(ok + ng, 2)
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ceil(ok))


### FIXED CODE ###

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

def isOk(x):
    cnt = 0
    for a in A:
        cnt += (a - 1) // x
    return cnt <= K

ok = max(A)
ng = 0
while ok - ng > 1:
    mid = (ok + ng) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

from collections import defaultdict
from heapq import *

def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split(sep)))

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def __repr__(self):
        return '({},{})'.format(self.x, self.y)

def dist(p1, p2, p, q):
    if (p1.x,p1.y) == (p2.x, p2.y):
        return float('inf')
    if p1.x == p2.x and abs(p1.y - p2.y) == 1:
        return q[min(p1.y, p2.y)]
    elif p1.y == p2.y and abs(p1.x - p2.x) == 1:
        return p[min(p1.x, p2.x)]
    return float('inf')

def mst(ps, p, q):
    m =  [[dist(ps[i], ps[j], p, q) for i in range(len(ps))] for j in range(len(ps))]

    X = set([0])
    Y = set(range(len(ps))[1:])
    cost = 0
    edges = []
    while len(Y) != 0:
        mcost = float('inf')
        edge = None
        for ex in X:
            for ey in Y:
                if mcost > m[ex][ey]:
                    mcost = m[ex][ey]
                    edge = [ex, ey]
        X.add(edge[1])
        Y.remove(edge[1])

        cost += mcost
        edges.append(edge)
    return cost, edges

def main():
    w, h = reads()
    p = [read() for _ in range(w)]
    q = [read() for _ in range(h)]
    points = []
    for x in range(w+1):
        for y in range(h+1):
            points.append((Point(x,y)))
    print(int(mst(points, p, q)[0]))

main()


### FIXED CODE ###

def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split(sep)))

def main():
    w, h = reads()
    p = sorted([read() for _ in range(w)])[::-1]
    q = sorted([read() for _ in range(h)])[::-1]

    pi = w-1
    qi = h-1
    res = 0
    while 0<=pi and 0<=qi:
        if p[pi] < q[qi]:
            res += p[pi] * (h+1)
            pi -= 1
            w -= 1
        else:
            res += q[qi] * (w+1)
            qi -= 1
            h -= 1
    res += sum(p[:pi+1]) + sum(q[:qi+1])
    print(res)

main()
### BUGGY CODE ###

n = int(input())
s = []
list1 = []
list2 = []

for _ in range(n):
    car = input()
    s.append(car)

for i in range(n):
    if s[i] in list1:
        list2[list1.index(s[i])] += 1
    else:
        list1.append(s[i])
        list2.append(1)

maxs = [i for i in range(len(list2)) if list2[i] == max(list2)]
max_char = [list1[i] for i in maxs]
max_char_jisho = sorted(max_char)

for i in max_char_jisho:
    print(i)

### FIXED CODE ###

import collections

n = int(input())
s = [input() for _ in range(n)]
c_sort = collections.Counter(s).most_common()
list_most = [c_sort[i][0] for i in range(len(c_sort)) if c_sort[i][1] == c_sort[0][1]]
for i in sorted(list_most):
    print(i)
### BUGGY CODE ###

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

S = list(map(int,input().split()))
T = list(map(int,input().split()))

# 累積和参照のために0の行，列を追加
sm = [[0] * (M+1) for _ in range(N+1)]

for i in range(1,N+1) :
    l1 = sm[i-1][:]
    l2 = 0
    s = S[i-1]
    for j in range(1,M+1) :
        new = l1[j] + l2
        if s == T[j-1] :
            new += 1  # dp = sm[i-1][j-1] + 1
        else :
            new -= l1[j-1] # dp = 0
        l2 = new
        sm[i][j] = new

ans = (sm[-1][-1] + 1) % (10**9 + 7)

print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0] * (M + 1) for _ in range(N + 1)]  # dp[s][t]

for i, s in enumerate(S, start=1):
    for j, t in enumerate(T, start=1):
        v = dp[i - 1][j] + dp[i][j - 1]
        if s == t:
            v += 1
        else:
            v -= dp[i - 1][j - 1]
        dp[i][j] = v % MOD

print((dp[-1][-1] + 1) % MOD)
### BUGGY CODE ###

def warshall_floid(d):
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d

n,m,l = map(int,input().split())
d = [[float('inf')]*(n+1) for i in range(n+1)]
for i in range(m):
    a,b,c = map(int,input().split())
    d[a][b] = c
    d[b][a] = c
for i in range(1,n+1):
    d[i][i] = 0
d = warshall_floid(d)
for i in range(1,n+1):
    for j in range(1,n+1):
        if d[i][j] <= l:
            d[i][j] = 1
        else:
            d[i][j] = float('inf')
d = warshall_floid(d)
q = int(input())
for i in range(q):
    s,t = map(int,input().split())
    if d[s][t] == float('inf'):
        print(-1)
    else:
        print(d[s][t]-1)


### FIXED CODE ###

def warshall_floid(d):
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d

n,m,l = map(int,input().split())
d = [[10**13]*(n+1) for i in range(n+1)]
for i in range(m):
    a,b,c = map(int,input().split())
    d[a][b] = c
    d[b][a] = c
for i in range(1,n+1):
    d[i][i] = 0
d = warshall_floid(d)
for i in range(1,n+1):
    for j in range(1,n+1):
        if d[i][j] <= l:
            d[i][j] = 1
        else:
            d[i][j] = 10**13
d = warshall_floid(d)
q = int(input())
for i in range(q):
    s,t = map(int,input().split())
    if d[s][t] >= 10**13:
        print(-1)
    else:
        print(d[s][t]-1)
### BUGGY CODE ###

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

import math

def main():
    n = int(input())
    a = list(map(int, input().split()))
    m = max(a)
    a.remove(m)

    ans = m
    mx = -1
    for num in a:
        tmp = math.factorial(m) / (math.factorial(num) * math.factorial(m - num))
        if tmp > mx:
            mx = tmp
            ans = num

    print(m)
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

import math

def main():
    n = int(input())
    a = list(map(int, input().split()))
    m = max(a)
    a.remove(m)

    ans = m
    h = m / 2
    dif = 9999999999
    for num in a:
        if abs(h - num) < dif:
            ans = num
            dif = abs(h - num)

    print(m)
    print(ans)

if __name__ == '__main__':
    main()