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

import collections
N = int(input())
S = []
for i in range(N):
    S.append(input())
S_counter = collections.Counter(S)
S_max = [Sv[0] for Sv in S_counter.items() if Sv[1] == max(S_counter.values())]
S_max_sorted = sorted(S_max)
for ans in S_max_sorted:
    print(ans)

### FIXED CODE ###

import collections
N = int(input())
S = {}
for i in range(N):
    value = input()
    if value not in S:
        S[value] = 1
    else:
        S[value] += 1
S_largest = max(S.values())
S_sorted = sorted(S.items(), key=lambda x:x[1], reverse=True)
ans = []
for i in range(len(S_sorted)):
    if S_sorted[i][1] == S_largest:
        ans.append(S_sorted[i][0])
    else:
        break
ans_sorted = sorted(ans)
for a in ans_sorted:
    print(a)
### BUGGY CODE ###

n,m,k=map(int,input().split())
fr=[input() for i in range(m)]
bl=[input() for i in range(k)]
relfr={i:set() for i in range(n)}
relbl={i:set() for i in range(n)}
for l in fr:
  a,b=map(int,l.split())
  relfr[a-1].add(b-1)
  relfr[b-1].add(a-1)
for l in bl:
  a,b=map(int,l.split())
  relbl[a-1].add(b-1)
  relbl[b-1].add(a-1)
cand={0}
searched=set()
gr=set()
all_gr={i for i in range(n)}
ans=[0]*n
c=0
while True:
  while True:
    now=cand.pop()
    gr.add(now)
    c+=1
    for point in relfr[now].difference(gr,cand):
      cand.add(point)
    if len(cand)==0:
      break
  for i in gr:
    ans[i]=len(gr)-len(relfr[i])-len(relbl[i].intersection(gr))-1
    searched.add(i)
  all_gr=all_gr.difference(searched)
  gr.clear()
  if c!=n:
    cand.add(list(all_gr)[0])
  else:
    break
print(' '.join(map(str,ans)))

### FIXED CODE ###

n,m,k=map(int,input().split())
relfr={i:set() for i in range(n)}
relbl={i:set() for i in range(n)}
for i in range(m):
  a,b=map(int,input().split())
  relfr[a-1].add(b-1)
  relfr[b-1].add(a-1)
for i in range(k):
  a,b=map(int,input().split())
  relbl[a-1].add(b-1)
  relbl[b-1].add(a-1)
blsiz=[0 for i in range(n)]
ans=[0]*n
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)
for i in range(n):
  for j in relfr[i]:
    uf.Unite(i,j)
for i in range(n):
  for j in relbl[i]:
    if uf.isSameGroup(i,j):
      blsiz[i]+=1
for i in range(n):
  ans[i]=uf.Count(i)-len(relfr[i])-blsiz[i]-1

print(' '.join(map(str,ans)))
### BUGGY CODE ###

h, w = map(int, input().split())
grid = [None]*h
cnt = [[0 for _ in range(w+1)] for __ in range(h+1)]
for i in range(h):
    grid[i] = list(input())
for i in range(h):
    done = [0]*w
    for j in range(w):
        if grid[i][j] == "#": continue
        if done[j] == 1: continue
        l = 0
        while j+l < w:
            if grid[i][j+l] == "#": break
            l += 1
        for k in range(l):
            cnt[i][j+k] += l
            done[j+k] = 1
for j in range(w):
    done = [0]*h
    for i in range(h):
        if grid[i][j] == "#": continue
        if done[i] == 1: continue
        l = 0
        while i+l < h:
            if grid[i+l][j] == "#": break
            l += 1
        for k in range(l):
            cnt[i+k][j] += l
            done[i+k] = 1
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, cnt[i][j]-1)
print(ans)


### FIXED CODE ###

h, w = map(int, input().split())
grid = [None]*h
cnt = [[0 for _ in range(w+1)] for __ in range(h+1)]
for i in range(h):
    grid[i] = list(input())
for i in range(h):
    done = [0]*w
    for j in range(w):
        if grid[i][j] == "#": continue
        if done[j] == 1: continue
        l = 0
        while j+l < w:
            if grid[i][j+l] == "#": break
            l += 1
        for k in range(l):
            cnt[i][j+k] += l
            done[j+k] = 1
for j in range(w):
    done = [0]*h
    for i in range(h):
        if grid[i][j] == "#": continue
        if done[i] == 1: continue
        l = 0
        while i+l < h:
            if grid[i+l][j] == "#": break
            l += 1
        for k in range(l):
            cnt[i+k][j] += l
            done[i+k] = 1
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, cnt[i][j]-1)
print(ans)
### BUGGY CODE ###

s=input()
n=len(s)
dp=[[0]*(13) for _ in range(n)]
mod=10**9+7

for i in range(n):
    if i==0:
        if s[i]=='?':
            for j in range(10):
                dp[i][j]=1
        else:
            x=int(s[i])
            dp[i][x]=1
    else:
        if s[i]=='?':
            for k in range(10):
                for j in range(13):
                    dp[i][(j*10+k)%13]+=dp[i-1][j]
        else:
            x=int(s[i])
            for j in range(13):
                dp[i][(j*10+x)%13]+=dp[i-1][j]

print(dp[n-1][5]%mod)

### FIXED CODE ###

s=input()
n=len(s)
dp=[[0]*(13) for _ in range(n)]
mod=10**9+7

for i in range(n):
    if i==0:
        if s[i]=='?':
            for j in range(10):
                dp[i][j]=1
        else:
            x=int(s[i])
            dp[i][x]=1
    else:
        if s[i]=='?':
            for k in range(10):
                for j in range(13):
                    dp[i][(j*10+k)%13]+=dp[i-1][j]
                    dp[i][(j*10+k)%13]%=mod
        else:
            x=int(s[i])
            for j in range(13):
                dp[i][(j*10+x)%13]+=dp[i-1][j]
                dp[i][(j*10+x)%13]%=mod
print(dp[n-1][5]%mod)
### BUGGY CODE ###

import sys
# import numpy as np
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))
# import profile

def solve():
    n, k =read(); arr = read()
    dp = [-1]*n; dp[0] = 0
    for i in range(n):
    	for j in range(1, k+1):
    		if i-j >-1:
    			tem = dp[i-j]+abs(arr[i-j] - arr[i])
    			if dp[i] == -1:
    				dp[i] = tem
    			elif dp[i] > tem:
    				dp[i] = tem
    				# dp[i] = min(dp[i], tem)
    print(dp[-1])

def one():
	l = [0]*10**7
def two():
	l = [0 for i in range(10**7)]

if __name__ == "__main__":
	solve()
	# cProfile.run(solve())
	# profile.run(one())
	# cProfile.run()

### FIXED CODE ###

import sys
# import numpy as np
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))
# import profile

def solve():
    n, k =read(); arr = read()
    dp = [-1]*n; dp[0] = 0
    for i in range(n):
    	for j in range(1, k+1):
    		if i-j >-1:
    			tem = dp[i-j]+abs(arr[i-j] - arr[i])
    			if dp[i] == -1:
    				dp[i] = tem
    			elif dp[i] > tem:
    				dp[i] = tem
    				# dp[i] = min(dp[i], tem)
    print(dp[-1])

def one():
	l = [0]*10**7
def two():
	l = [0 for i in range(10**7)]

if __name__ == "__main__":
	solve()
	# cProfile.run(solve())
	# profile.run(one())
	# cProfile.run()
### BUGGY CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N, M, L = map(int, input().split())
inf = 10**15
d = [[] for _ in range(N)]

for _ in range(M):
    A, B, C = map(int, input().split())
    if C>L:continue
    d[A-1].append((B-1, C))
    d[B-1].append((A-1, C))

dists = []
for j in range(N):
    dist = [(inf,inf)]*N
    dist[j] = (0, 0)
    q = [(0, 0, j)]
    while q:
        charged, used, u = heappop(q)
        if (charged, used) > dist[u]:
            continue
        for v, next_cost in d[u]:
            c = (charged+1, next_cost) if used+next_cost>L else (charged, used+next_cost)
            if dist[v] > c:
                dist[v] = c
                heappush(q, c+(v,))
    dists.append(dist)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = dists[s-1][t-1][0]
    print(ans if ans!=inf else -1)

### FIXED CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N, M, L = map(int, input().split())
inf = 10**15
V = [[] for _ in range(N)]

for _ in range(M):
    A, B, C = map(int, input().split())
    if C>L:continue
    V[A-1].append((B-1, C))
    V[B-1].append((A-1, C))

dists = []
for i in range(N):
    dist = [(inf,inf)] * N
    dist[i] = (0, 0)
    u = [False] * N
    for _ in range(N):
        (charged, used), j = min([(dist[i], i) for i in range(N) if not u[i]])
        u[j] = True
        for k, next_cost in V[j]:
            if j==k: continue
            c = (charged+1, next_cost) if used+next_cost>L else (charged, used+next_cost)
            if dist[k] > c:
                dist[k] = c
    dists.append(dist)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = dists[s-1][t-1][0]
    print(ans if ans!=inf else -1)
### BUGGY CODE ###

from fractions import gcd
from functools import reduce

def main():
    n = int(input())
    A = list(map(int, input().split()))

    gcd_max = 1
    L = A[0]
    for i in range(n):
        if i == 0:
            tempt = reduce(gcd, A[i+1:])
            gcd_max = max(gcd_max, tempt)
        elif i != n-1:
            L = gcd(L,A[i-1])
            tempt = gcd(L,reduce(gcd, A[i+1:]))
            gcd_max = max(gcd_max, tempt)
        else:
            L = gcd(L,A[i-1])
            tempt = L
            gcd_max = max(gcd_max, tempt)
    print(gcd_max)


if __name__ == '__main__':
    main()

### FIXED CODE ###

from fractions import gcd


def main():
    n = int(input())
    A = list(map(int, input().split()))

    L = []
    R = []
    for i in range(n):
        if i == 0:
            L.append(A[0])
            R.append(A[-1])
            continue
        L.append(gcd(L[i-1],A[i]))
        R.append(gcd(R[i-1],A[-i-1]))
    R.reverse()

    for i in range(n):
        if i == 0:
            gcd_max = R[1]
        elif i != n-1:
            gcd_max = max(gcd_max, gcd(L[i-1], R[i+1]))
        else:
            gcd_max = max(gcd_max, L[-2])
    print(gcd_max)


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


if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    ans = A[0]
    for i in A[1:]:
        ans *= i
    if ans > 1000000000000000000:
        ans = -1
    print(ans)


### FIXED CODE ###

import numpy as np

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    ans = A[0]
    if 0 in A:
        ans = 0
    else:
        for i in A[1:]:
            ans *= i
            if ans > 1000000000000000000:
                ans = -1
                break
    print(ans)
### BUGGY CODE ###

from itertools import combinations

N = int(input())
S = input()

idxs = [i for i in range(N)]

ans = 0
for c in combinations(idxs, 3):
    i, j, k = sorted(c)
    s0 = S[i]
    s1 = S[j]
    s2 = S[k]

    if j - i != k - j and s0 != s1 and s1 != s2 and s0 != s2:
        ans += 1

print(ans)


### FIXED CODE ###


N = int(input())
S = input()

ris = [i for i, s in enumerate(S) if s == "R"]
gis = [i for i, s in enumerate(S) if s == "G"]
bis = [i for i, s in enumerate(S) if s == "B"]

all = len(ris) * len(gis) * len(bis)

cnt = 0
for i in range(N):
    for j in range(i+1, N):
        k = 2*j - i
        if 0 <= k < N:
            if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                cnt += 1

ans = all - cnt


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

n,k,q,*a=map(int,open(0).read().split())
points=[k]*n
for i in range(q):
    for j in range(n):
        if a[i]-1!=j:
            points[j]-=1
for i in range(n):
    print('NYoe s'[points[i]>0::2])

### FIXED CODE ###

n,k,q,*a=map(int,open(0).read().split())
import numpy as np
points=np.full(n,k)

for i in range(q):
    points-=1
    points[a[i]-1]+=1

for i in range(n):
    print('NYoe s'[points[i]>0::2])
### BUGGY CODE ###

h,w = map(int,input().split())
f = [input() for _ in range(h)]
ss = []
def bfs(l):
    stack = l
    visited = [[0]*w for i in range(h)]
    dist = [[10**8]*w for i in range(h)]
    vec = [(0,1),(1,0),(-1,0),(0,-1)]
    for sx,sy in l:dist[sx][sy] = 0
    while stack:
        next = []
        for now in stack:
            x,y = now[0],now[1]
            visited[x][y] = 1
            for tx,ty in vec:
                nx,ny = x+tx,y+ty
                if nx < 0 or ny < 0 or nx>h-1 or ny > w-1:continue
                if visited[nx][ny] :continue
                if f[nx][ny] == '#':continue
                next.append((nx,ny))
                dist[nx][ny] = min(dist[nx][ny],dist[x][y] +1)
            stack = next
    res  = 0
    for i in range(h):
        for j in range(w):
            if dist[i][j] == 10**8:continue
            res = max(res,dist[i][j])
    return res


for i in range(h):
    for j in range(w):
        if f[i][j] == '#':ss.append((i,j))
ans  = bfs(ss)
print(ans)



### FIXED CODE ###

h,w = map(int,input().split())
a = list(list(input())for i in range(h))
stack = []
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            stack.append((i,j))
        
vec = ((1,0),(0,1),(-1,0),(0,-1))
move = 0
while stack:
    next = []
    move +=1
    for y,x in stack:
        for ny,nx in vec:
            ty,tx = y+ny,x+nx
            if ty>h-1 or tx>w-1 or ty<0 or tx <0:continue
            if a[ty][tx] == ".":
                a[ty][tx] = move
                next.append((ty,tx))
    stack = next

print(move-1)
### BUGGY CODE ###

from collections import defaultdict

mod = 10**9+7

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
DP = defaultdict(int)
DP[0] = 1
for i in range(n):
    nxt = defaultdict(int)
    for key, value in DP.items():
        for j in range(n):
            mask = 1<<j
            if key & mask == 0 and a[i][j]:
                nxt[key|mask] += value
                nxt[key|mask] %= mod
    DP = nxt
state = (1<<n) - 1
ans = DP[state]
print(ans)

### FIXED CODE ###

mod = 10**9+7

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]

DP = [0]*(1<<n)
DP[0] = 1

pow2 = [1<<i for i in range(n)]
cnt = [0]*(1<<n)
for i in range(1<<(n-1)):
    cnt[2*i] = cnt[i]
    cnt[2*i+1] = cnt[i]+1

for state in range(1, 1<<n):
    k = cnt[state]
    for j in range(n):
        if a[k-1][j] and (state>>j)&1:
            DP[state] += DP[state^pow2[j]]
    DP[state] %= mod
print(DP[-1])
### BUGGY CODE ###

import copy
from collections import deque

####入力
H,W = map(int,input().split())

#gridの定義
grid = []
for i in range(H):
  S = input()
  grid.append( [S[i] for i in range(W) ])
####入力終了


#l_blackの設定
l_black = deque([])
for i in range(H):
  for j in range(W):
    if grid[i][j] == "#":
      l_black.append( [i,j] ) # [行,列]


#探索
cnt = 0

while len(l_black) > 0:

  l_change = deque([])

  #vは黒マスリスト #新たに黒マスになる白マスの座標をl_changeに詰めていく
  while len(l_black) > 0:
    v = l_black.popleft()
    #iはvの上下左右のマスの座標[行,列]
    for i in [ [v[0]+1,v[1]] , [v[0],v[1]+1] , [v[0]-1,v[1]] ,[v[0],v[1]-1] ]:
      #場外アウトの場合はスルー
      if (i[1]<0 or i[0] <0 or i[0]>=H or i[1] >= W ):
        continue
      #移動先がもう黒マスの場合スルー
      if grid[i[0]][i[1]] == "#":
        continue
      #移動先が白マスならばそこの座標をl_changeに追加
      if grid[i[0]][i[1]] == ".":
        l_change.append( i )
        
  #l_blackの中を新たに黒鱒になったやつの座標だけにする
  l_black = copy.deepcopy( l_change )
  #l_changeの中の白マスを黒にする
  while len(l_change) > 0:
    i = l_change.popleft()
    grid[i[0]][i[1]] = "#" 
  if len(l_black) > 0:
    cnt = cnt + 1
print(cnt)  

### FIXED CODE ###

import copy
from collections import deque

####入力
H,W = map(int,input().split())

#gridの定義
grid = []
for i in range(H):
  S = input()
  grid.append( [S[i] for i in range(W) ])
####入力終了

#distの設定
dist = [[0 for i in range(W)] for j in range(H)]

#l_blackの設定
l_black = deque([])
for i in range(H):
  for j in range(W):
    if grid[i][j] == "#":
      l_black.append( [i,j] ) # [行,列]

#探索
max_d = 0

while len(l_black) > 0:
  #vは黒マスの座標 
  while len(l_black) > 0:
    v = l_black.popleft()
    #iはvの上下左右のマスの座標[行,列]
    for i in [ [v[0]+1,v[1]] , [v[0],v[1]+1] , [v[0]-1,v[1]] ,[v[0],v[1]-1] ]:
      #場外アウトの場合はスルー
      if (i[1]<0 or i[0] <0 or i[0]>=H or i[1] >= W ):
        continue
      #移動先がもう黒マスの場合スルー
      if grid[i[0]][i[1]] == "#":
        continue
      #移動先が白マスならばそこの座標を黒マスにして距離を記録する
      if grid[i[0]][i[1]] == ".":
        #黒マスにする
        grid[i[0]][i[1]] = "#"
        #新たに黒鱒となった座標をl_blackに追加
        l_black.append(i)
        #距離の記録
        dist[i[0]][i[1]] = dist[v[0]][v[1]] + 1
        max_d = max(max_d,dist[i[0]][i[1]])
print(max_d)
### BUGGY CODE ###

H, W, M = map(int,input().rstrip().split())
l = [[0 for i in range(H)] for j in range(W)]
r = [0]*H
c = [0]*W
max_r = 0
max_c = 0
r_i = []
c_j = []
for i in range(M):
    h, w = map(int,input().rstrip().split())
    l[w-1][h-1] = 1
    
    r[h-1] += 1
    if r[h-1]>max_r:
        max_r = r[h-1]
        r_i = [h-1]
    elif r[h-1]==max_r:
        r_i.append(h-1)
        
    c[w-1] += 1
    if c[w-1]>max_c:
        max_c = c[w-1]
        c_j = [w-1]
    elif c[w-1]==max_c:
        c_j.append(w-1)
ans = max_r+max_c-1
for i in r_i:
    for j in c_j:
        if l[j][i] == 0:
            ans = max_r+max_c
            break
    else:
        continue
    break
print(ans)

### FIXED CODE ###

H, W, M = map(int,input().rstrip().split())
bomb = []
r = [0]*H
c = [0]*W
max_r = 0
max_c = 0
r_i = []
c_j = []
r_num = 0
c_num = 0
for i in range(M):
    h, w = map(int,input().rstrip().split())
    bomb.append([h-1,w-1])
    r[h-1] += 1
    if r[h-1]>max_r:
        max_r = r[h-1]
        r_i = [h-1]
        r_num = 1
    elif r[h-1]==max_r:
        r_i.append(h-1)
        r_num += 1
    c[w-1] += 1
    if c[w-1]>max_c:
        max_c = c[w-1]
        c_j = [w-1]
        c_num = 1
    elif c[w-1]==max_c:
        c_j.append(w-1)
        c_num += 1
r_set = set(r_i)
c_set = set(c_j)
num = 0
for i in range(M):
    if bomb[i][0] in r_set:
        if bomb[i][1] in c_set:
            num += 1
if num<r_num*c_num:
    ans = max_r+max_c
else:
    ans = max_r+max_c-1
print(ans)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
 
negative_end = bisect_left(A, 0)
positive_start = bisect_right(A, 0)
 
positive_cnt = N - positive_start
negative_cnt = negative_end
zero_cnt = N - (positive_cnt + negative_cnt)
 
negative_pairs_cnt = positive_cnt * negative_cnt
zero_pairs_cnt = zero_cnt * (positive_cnt + negative_cnt) + (zero_cnt * (zero_cnt - 1) // 2)


# 答えが負の場合
if K <= negative_pairs_cnt:
    # にぶたん: X以下になるペアがK個以上あるか？
    ok, ng = 0, -10 ** 18
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2
        or_higher_cnt, r = 0, positive_start
        for l in range(negative_end):
            while (r < N) and (A[l] * A[r] > X):
                r += 1
            or_higher_cnt += positive_cnt - (r - positive_start)
 
        if or_higher_cnt >= K:
            ok = X
        else:
            ng = X
 
    print(ok)

# 答えが0の場合
elif K <= negative_pairs_cnt + zero_pairs_cnt:
    print(0)
 
# 答えが正の場合
else:
    # にぶたん: X以下になるペアがK個以上あるか？
    K -= (negative_pairs_cnt + zero_pairs_cnt)
    ok, ng = 10 ** 18, 0
    while abs(ok - ng) > 1:
        X = (ok + ng) // 2
        or_higher_cnt = 0
 
        r = N - 1
        for l in range(positive_start, N):
            while (r < N) and (A[l] * A[r] > X) and (l < r):
                r -= 1
            or_higher_cnt += max(0, r - l)
 
        l = 0
        for r in range(negative_end - 1, -1, -1):
            while (l < N) and (A[l] * A[r] > X) and (l < r):
                l += 1
 
            or_higher_cnt += max(0, r - l)
 
        if or_higher_cnt >= K:
            ok = X
        else:
            ng = X
 
    print(ok)

### FIXED CODE ###

# -*- coding: utf-8 -*-
#尺取り法

import numpy as np
n, k = map(int,input().split())
a = np.array(list(map(int,input().split())))
a.sort()
posi = a[a>0]
zero = a[a==0]
nega = a[a<0]
#print(posi)
# 2分探索, midより小さいものを数える
l = -10**18-1
r = 10**18+1
while r-l > 1:
    mid = (r+l)//2
    cnt = 0
    if mid >= 0:
        cnt += len(zero)*n

    # a.searchsorted(v, side="left"): a[i-1] < v <= a[i]であるvのindexを返す
    # a.searchsorted(v, side="right"): a[i-1] <= v < a[i]であるvのindexを返す

    cnt += a.searchsorted(mid//posi, side="right").sum()
    cnt += (n - a.searchsorted(-(-mid//nega), side="left")).sum()
    cnt -= np.count_nonzero(a*a <= mid)
    cnt //= 2
    #print("mid:", mid)
    #print("mid//posi:", mid//posi)
    #print("search:", a.searchsorted(mid//posi,side="right"))
    #print("-(-mid//nega):", -(-mid//nega))
    #print("search:", a.searchsorted(-(-mid//nega),side="left"))
    #print("nonzero_count:", np.count_nonzero(a*a<=mid))
    #print("count:", cnt)
    #print('-' * 20)
    if cnt >= k:
        r = mid
    else:
        l = mid
print(r)
### BUGGY CODE ###

def isPrimeNumber(num):
  pn = 2 #素数は2から
  while pn * pn <= num: #√numまで調べる
    if num % pn == 0:
      return False
    pn += 1
  return True

n,m = map(int, input().split())
  
if m % n == 0:
  print(m//n)
  exit()
  
elif isPrimeNumber(m):
  print(1)
  
else:
  i = 1
  ans = 0
  while i  <= m // n:
    tmp = m - i * n
    if tmp % i == 0 and ans < i:
      ans = i
    i += 1

  print(ans)

### FIXED CODE ###

n,m = map(int, input().split()) 

ans = 1

for i in range(1, int(m ** 0.5)+1):
  if m % i == 0:
    if i >= n:
      ans = max(ans, m // i)
    elif m // i >= n:
      ans = max(ans, i)
      
      
print(ans)
### BUGGY CODE ###

from math import sqrt,gcd,ceil 
def ii():return int(input())
def mi():return map(int,input().split())
def li():return list(mi())
def si():return input()

n=ii()
a=li()
s=1
for i in a:
    s*=i
if(s>1e18):
    s=-1
print(s)

### FIXED CODE ###

from math import sqrt,gcd,ceil 
def ii():return int(input())
def mi():return map(int,input().split())
def li():return list(mi())
def si():return input()

n=ii()
a=li()
s=1
if 0 in a:
    print(0)
    exit(0)
for i in a:
    s*=i
    if(s>1e18):
        break
if(s>1e18):
    s=-1
print(s)
### BUGGY CODE ###

from collections import defaultdict
N,Ma,Mb=map(int,raw_input().split())
item=[]
i_sum=0
for i in range(N):
	a,b,c=map(int,raw_input().split())
	i_sum+=c
	item.append( (a,b,c) )

cost=defaultdict(lambda: None)

for i in item:
	x=i[0]
	y=i[1]
	w=i[2]
	if len(cost)==0:
		cost[0]=[(0,0)]
		cost[w]=[(x,y)]
	else:
		for j in cost.items():
			tw=j[0]
			for k in j[1]:
				tx=k[0]
				ty=k[1]
				if cost[tw+w] is None:
					cost[tw+w]=[(x+tx,y+ty)]
				else:
					cost[tw+w]+=[(x+tx,y+ty)]


for i in cost.items():
	w=i[0]
	for x,y in i[1]:
		if x*Mb==y*Ma and x*Mb!=0:
			print w
			quit()
else:
	print -1
			


### FIXED CODE ###

from collections import defaultdict
N,Ma,Mb=map(int,raw_input().split())

dp=defaultdict(lambda: float("inf"))
dp[(0,0)]=0

for i in range(N):
	a,b,c=map(int,raw_input().split())
	for j in dp.items():
		x=j[0][0]
		y=j[0][1]
		z=j[1]
		na, nb, nc = x+a, y+b, z+c 
		dp[(na, nb)]=min( dp[(na, nb)], nc)


ans=float("inf")
for i in dp.items():
	x=i[0][0]
	y=i[0][1]
	z=i[1]
	if x==0 and y==0:
		continue
	if x*Mb==y*Ma:
		ans=min(ans,z)

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