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

n = int(input())
ans_t, ans_a = map(int,input().split())
for i in range(n-1):
    t, a = map(int,input().split())
    now_t, now_a = t, a
    q = True
    while q:
        if ans_t <= now_t and ans_a <= now_a:
            q = False
            ans_t = now_t
            ans_a = now_a
        else:
            now_t += t
            now_a += a

print(ans_a + ans_t)

### FIXED CODE ###

n = int(input())
ans_t, ans_a = map(int,input().split())
for i in range(n-1):
    t, a = map(int,input().split())

    if ans_t % t == 0:
        p = ans_t//t
    else:
        p = ans_t//t + 1
    if ans_a % a == 0:
        q = ans_a // a
    else:
        q = ans_a// a + 1

    r = max(p, q)
    ans_a = a * r
    ans_t = t * r


print(ans_a + ans_t)
### BUGGY CODE ###

a,b,c,d = map(int,input().split())
ans = 0
for i in range(a,b+1):
  if i % c != 0:
    if i % d != 0:
      ans += 1
print(ans)

### FIXED CODE ###

import fractions

a,b,c,d = map(int,input().split())
def lcm(x,y):
  return x*y//fractions.gcd(x,y)
def func(n,x,y):
  return n - (n//x + n//y - n//lcm(x,y))
ans = func(b,c,d) - func(a-1,c,d)
print(ans)
### BUGGY CODE ###

def main():
  s, answer = raw_input(), 0
  while len(set(s)) > 1:
    char, pos = "", 0
    for i in xrange(len(s)-1,-1,-1):
      if s[i] != s[-1]:
        pos, char = i, s[i]
        break
    s = s[0:pos]+char
    answer += 1
  print(answer)


main()

### FIXED CODE ###

def main():
  raw = raw_input()
  s = raw[0]
  for x in xrange(1, len(raw)):
      if raw[x] == s[-1]:
          continue
      s += raw[x]
  print(len(s)-1)


main()
### BUGGY CODE ###

"""
    Author: _YL_
"""
s = input()
n = int(input())

i = 0
while i < n:
    lst = input().split()

    if lst[0] == "1":
        s = s[::-1]
    elif lst[1] == "1":
        s = lst[2] + s
    else:
        s += lst[2]

    i += 1

print(s)

### FIXED CODE ###

str = input()
Q = int(input())
left = []
right = []
flag = 1
for _ in range(Q):
    line = input().split()
    op1 = int(line[0])
    if op1 == 1:
        flag = -flag
    else:
        op2 = int(line[1])
        char = line[2]
        if (op2 == 1 and flag == 1) or (op2 == 2 and flag == -1) :
            left.append(char)
        else:
            right.append(char)

if flag == -1:
    right.reverse()
    str = str[::-1]
    str = "".join(right) + str
    str += "".join(left)
else:
    left.reverse()
    str = "".join(left) + str
    str += "".join(right)

print(str)
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline
h, w = map(int, input().split())
g = []
for i in range(h):
    g.append(input())

move = ((0, 1), (1, 0), (-1, 0), (0, -1))
ans = 0

for start in  [[i, j] for i in range(h) for j in range(w)]:
    if g[start[0]][start[1]] == "#":
        continue
    dp = [[0 for i in range(w)] for i in range(h)]
    pre = [-1, -1]
    cur = start
    cnt = 0
    queue = deque([[cur, pre, cnt]])
    while queue:
        cur, pre, cnt = queue.pop()
        c_x, c_y = cur
        if g[c_x][c_y] == '#':
          continue
        if not dp[c_x][c_y] or (dp[c_x][c_y] and dp[c_x][c_y] > cnt):
            dp[c_x][c_y] = cnt

            for x, y in move:
                next = [cur[0] + x, cur[1] + y]
                if next == start:
                    continue
                if next != pre and next[0] >= 0 and next[0] < h and next[1] >= 0 and next[1] < w:
                    queue.append([next, cur, cnt + 1])
    ans= max(max([dp[i][j] for i in range(h) for j in range(w)]), ans)


print(ans)


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
h, w = map(int, input().split())
g = []
for i in range(h):
    g.append(input())

move = ((0, 1), (1, 0), (-1, 0), (0, -1))
ans = 0

for start in  [[i, j] for i in range(h) for j in range(w)]:
    if g[start[0]][start[1]] == "#":
        continue
    dp = [[0 for i in range(w)] for i in range(h)]
    pre = [-1, -1]
    cur = start
    cnt = 0
    queue = deque([[cur, pre, cnt]])
    while queue:
        cur, pre, cnt = queue.popleft()
        c_x, c_y = cur
        if g[c_x][c_y] == '#':
          continue
        if not dp[c_x][c_y] or (dp[c_x][c_y] and dp[c_x][c_y] > cnt):
            dp[c_x][c_y] = cnt

            for x, y in move:
                next = [cur[0] + x, cur[1] + y]
                if next == start:
                    continue
                if next != pre and next[0] >= 0 and next[0] < h and next[1] >= 0 and next[1] < w:
                    queue.append([next, cur, cnt + 1])
    ans= max(max([dp[i][j] for i in range(h) for j in range(w)]), ans)


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

# 定数
INF = float("inf")
MOD = int(1e9 + 7)

# エントリーポイント
def main():
    H, W = map(int, input().split())
    S = tuple(tuple(input()) for _ in range(H))

    hstage = []
    for n in range(H):
        line, c = [], 0
        for m in range(W):
            if S[n][m] == "#":
                line += [c] * c + [0]
                c = 0
            else:
                c += 1
        else:
            line += [c] * c
        hstage += [line]

    vstage = []
    for m in range(W):
        line, c = [], 0
        for n in range(H):
            if S[n][m] == "#":
                line += [c] * c + [0]
                c = 0
            else:
                c += 1
        else:
            line += [c] * c
        vstage += [line]

    max_lumps = 0
    for y in range(H):
        for x in range(W):
            if max_lumps < (hstage[y][x] + vstage[x][y] - 1):
                max_lumps = hstage[y][x] + vstage[x][y] - 1
    print(max_lumps)

main()


### FIXED CODE ###

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

sum_s = [[], []]

for y in range(H):
	count, line = 0, []
	for x in range(W):
		if STAGE[y][x] == ".":
			count += 1
		else:
			if 0 < count:
				line += [count] * count
			line += [0]
			count = 0
	else:
		if 0 < count:
			line += [count] * count
	sum_s[0] += [line]

for x in range(W):
	count, line = 0, []
	for y in range(H):
		if STAGE[y][x] == ".":
			count += 1
		else:
			if 0 < count:
				line += [count] * count
			line += [0]
			count = 0
	else:
		if 0 < count:
			line += [count] * count
	sum_s[1] += [line]
"""
for line in sum_s[0]:
	print(*line)
print()
for line in sum_s[1]:
	print(*line)
"""
max_score = 0
for y in range(H):
	for x in range(W):
		max_score = max(max_score, sum_s[0][y][x] + sum_s[1][x][y] - 1)

print(max_score)
### BUGGY CODE ###

import sys
from collections import Counter

n = int(sys.stdin.readline())
battle_dict = dict()
cur_stage = Counter([])
for i in range(n):
    inp = [int(i) for i in sys.stdin.readline().split()]
    battle_dict[i + 1] = inp
    new = tuple(sorted([i + 1, inp[0]]))
    cur_stage.update([new])

cnt = 0
while True:
    flg = 0
    for v, c in cur_stage.items():
        if c > 1:
            i, j = v
            if len(battle_dict[i]) > 0:
                battle_dict[i].pop(0)
            if len(battle_dict[j]) > 0:
                battle_dict[j].pop(0)
            cur_stage[v] = 0
            flg = 1
    if flg == 0:
        break
    else:
        cnt += 1
    cur_stage.clear()
    for i, j in battle_dict.items():
        if len(j) > 0:
            new = tuple(sorted([i, j[0]]))
            cur_stage.update([new])
if len(cur_stage) > 0:
    print(-1)
else:
    print(cnt)

### FIXED CODE ###

import sys
from collections import Counter
import copy

n = int(sys.stdin.readline())
ct = Counter()
a_ls = dict()
for i in range(n):
    inp = [int(i) - 1 for i in sys.stdin.readline().split()]
    a_ls[i] = inp
cnt = 0
candidate = list(range(n))
rest = n * (n - 1) / 2
combis = set()
while rest:
    no_ls = []
    next_candidate = []
    flg = False
    for i in candidate:
        if len(a_ls[i]) == 0:
            continue
        target = a_ls[i][0]
        if (i, target) in combis or (target, i) in combis:
            next_candidate.append(i)
            next_candidate.append(target)
            rest -= 1
            if len(a_ls[i]) > 0:
                a_ls[i].pop(0)
            if len(a_ls[target]) > 0:
                a_ls[target].pop(0)
            flg = True
        else:
            combis.add((i, target))
    candidate = next_candidate
    if not flg:
        cnt = -1
        break
    cnt += 1
print(cnt)
### BUGGY CODE ###

n = int(input())
input_array = []
for i in range(n):
    input_array.append(input())
counter = {}
for i in set(input_array):
    counter[i] = input_array.count(i)
max_key_list = [kv[0] for kv in counter.items() if kv[1]==max(counter.values())]
max_key_list.sort()
for i in max_key_list:
    print(i)

### FIXED CODE ###

n = int(input())
count_dict = {}
for _ in range(n):
    e = input()
    if e in count_dict.keys():
        count_dict[e] += 1
    else:
        count_dict[e] = 1

m = max(count_dict.values())
for e in sorted(k for k in count_dict if count_dict[k] == m):
    print(e)
### BUGGY CODE ###

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

c = [0]*N
ans = 0
for i in range(N):
  c[i] = A.count(i+1)
  if c[i]>1:
    ans+=c[i]*(c[i]-1)//2

for i in range(N):
  print(ans-c[A[i]-1]*(c[A[i]-1]-1)//2+(c[A[i]-1]-1)*(c[A[i]-1]-2)//2) if c[A[i]-1]>1 else print(ans)

### FIXED CODE ###

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

c = collections.Counter(A)
ans = 0
for i in c:
  ans+=c[i]*(c[i]-1)//2

for i in range(N):
  print(ans-(c[A[i]]-1))
### BUGGY CODE ###

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

A.sort()
A.append([0])
ans = 0
for i in range(N):
    if A[i] != A[i + 1]:
        flag = True
        for j in range(i):
            if A[i] % A[j] == 0:
                flag = False
                break
        if flag:
            ans += 1

print(ans)

### FIXED CODE ###

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

A.sort()
A.append(0)
dp = [True] * (10 ** 6 + 5)
ans = 0
for i in range(N):
    if dp[A[i]-1]:
        if A[i] != A[i + 1]:
            ans += 1
        dp[A[i]-1::A[i]] = [False] * (len(dp) // A[i])

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

N = int(input())
P = list(map(int,input().split()))
a = []
b = []
ans = 1
for i in range(1,len(P)):
    a = P[:i + 1]
    b= P[i]
    a.sort()
    if b == a[0]:
        ans += 1
print(ans)    

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
mi = 10**7
b = [0]*N
for i in range(N):
    if mi > P[i]:
        b[i] += 1
        mi=P[i]
print(sum(b))
### BUGGY CODE ###

N, K =map(int, input().split())
lst=list(map(int, input().split()))
mx=0
for i in range(0, N-K+1):
	S=sum(lst[i:i+K])
	if mx<S:
		mx=S
print((mx+K)/2)

### FIXED CODE ###

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

expect=[(dice+1)/2 for dice in p]
#print(expect)
#plus_p=[sum(expect[i:i+K]) for i in range(N-K+1)]

first=sum(expect[0:K])
plus_p=[first]
for i in range(1, N-K+1):
	plus_p.append(plus_p[i-1]-expect[i-1]+expect[i-1+K])
#print(plus_p)
print(max(plus_p))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
H,W=map(int, sys.stdin.readline().split())

A=[ map(int, sys.stdin.readline().split()) for _ in range(H) ]
B=[ map(int, sys.stdin.readline().split()) for _ in range(H) ]

for h in range(H):
    for w in range(W):
        A[h][w]=abs(A[h][w]-B[h][w])

dp=[ [ 0 for _ in range(W) ] for __ in range(H) ]

Center=80*80      #中心地のセット マイナスの値もセットできるようにbitsetのゼロを80*80+1桁目に置く

#初期化
r,c=0,0
val=A[r][c]
dp[r][c]=1<<val+Center

q=deque()
q.append((0,0))
D=[(1,0),(0,1)]

while q:
    r,c=q.popleft()
    for dr,dc in D:
        if r+dr<H and c+dc<W:
            next_r=r+dr
            next_c=c+dc
            next_val=A[next_r][next_c]
            dp[next_r][next_c]|=dp[r][c]<<next_val
            dp[next_r][next_c]|=dp[r][c]>>next_val
            q.append((next_r,next_c))

ans=float("inf")
for i in range(80*80*2):
    bit=dp[H-1][W-1]>>i&1
    if bit==1:
        ans=min(ans,abs(i-Center))

print ans


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque,defaultdict

H,W=map(int, sys.stdin.readline().split())
A=[ map(int, sys.stdin.readline().split()) for _ in range(H) ]
B=[ map(int, sys.stdin.readline().split()) for _ in range(H) ]

for h in range(H):
    for w in range(W):
        A[h][w]=abs(A[h][w]-B[h][w])

dp=[ [ 0 for _ in range(W) ] for __ in range(H) ]

Center=80*80      #中心地のセット マイナスの値もセットできるようにbitsetのゼロを80*80+1桁目に置く

#初期化
r,c=0,0
val=A[r][c]
dp[r][c]=1<<val+Center

q=deque()
q.append((0,0))
D=[(1,0),(0,1)]
Visit=defaultdict(lambda: 0)     #訪問済みの頂点にフラグ1を立てる
Visit[(0,0)]=1
D=[(1,0),(0,1)]

for r in range(H):
    for c in range(W):
        for dr,dc in D: #横に1つ移動か、下に1つ移動
            if r+dr<H and c+dc<W:   #移動しようとするマスが存在するならばif文内の処理を行う
                next_r=r+dr
                next_c=c+dc
                next_val=A[next_r][next_c]
                dp[next_r][next_c]|=dp[r][c]<<next_val  #次のマスの値が+の場合は、bitshift全体を左にシフト
                dp[next_r][next_c]|=dp[r][c]>>next_val  #次のマスの値が-の場合は、bitshift全体を右にシフト
                q.append((next_r,next_c))

ans=float("inf")
for i in range(Center*2):
    bit=dp[H-1][W-1]>>i&1
    if bit==1:
        ans=min(ans,abs(i-Center))

print ans
### BUGGY CODE ###

import bisect
from collections import defaultdict, deque

n, m = map(int, input().split())
d = defaultdict(list)

queue = deque()
for i in range(m):
    p, y = map(int, input().split())
    d[p].append(y)
    queue.append((p, y))

while queue:
    p, y = queue.popleft()
    index = sorted(d[p]).index(y)
    print('{:06d}{:06d}'.format(p, index + 1))

### FIXED CODE ###

from collections import defaultdict
import bisect

n, m = map(int, input().split())
d = defaultdict(list)

queue = []
for i in range(m):
    p, y = map(int, input().split())
    d[p].append((y, i))

arr = [0] * m
for k, v in d.items():
    for i, item in enumerate(sorted(v, key=lambda x: x[0])):
        arr[item[1]] = (k, i)

for k, v in arr:
    print('{:06d}{:06d}'.format(k, v + 1))
### BUGGY CODE ###

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

pos = 1
ans = 0
leng = len(alist)
while(len(alist) > 0 and pos <= len(alist)):
    if (pos != alist[pos-1]):
        del(alist[pos-1])        
        ans += 1
        continue
    else:
        pos += 1

if (leng == ans):
    print("-1")
else:  
    print (ans)


### FIXED CODE ###

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

pos = 1
ans = 0
leng = len(alist)
while(leng >= pos+ans):
    if (pos != alist[pos-1+ans]):
        ans += 1
    else:
        pos += 1

if (leng == ans):
    print("-1")
else:  
    print (ans)
### BUGGY CODE ###

# C
import functools
def gcd(a,b):
    if a<b:a,b=b,a
    if a%b==0:return b
    return gcd(b,a%b)

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
pre_a = -1

for i in range(n):
    if pre_a != a[i]:
        values = a[:i] + a[i+1:]
        res = functools.reduce(gcd, values)
        ans = max(ans, res)
    pre_a = a[i]
print(ans)

### FIXED CODE ###

# C
import functools
# 3.4以前は math の gcd が対応していないので fractions のものを使う
# from fractions import gcd
def gcd(a,b):
    if a<b:a,b=b,a
    if a%b==0:return b
    return gcd(b,a%b)


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

gcd_left = [a[0]]
gcd_right = [a[-1]]
for i in range(1,n):
    if gcd_left[i-1] != 1:
        res = gcd(gcd_left[i-1], a[i])
    else:
        res = 1
    gcd_left.append(res)

for i in range(1,n):
    if gcd_right[i-1] != 1:
        res = gcd(gcd_right[i-1], a[-(i+1)])
    else:
        res = 1
    gcd_right.append(res)
gcd_right = gcd_right[::-1]


ans = 0
for i in range(n):
    if i == 0:
        res = gcd_right[1]
    elif i == n-1:
        res = gcd_left[-2]
    else:
        res = gcd(gcd_right[i+1], gcd_left[i-1])
    ans = max(res, ans)
print(ans)
### BUGGY CODE ###

import sys
from collections import Counter

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, P = lr()
S = sr()
# 累積和
remain = [0] * N
cur = 0
for i in range(N):
    num = 10 * cur + int(S[i])
    cur = num % P
    remain[i] = cur

counter = Counter(remain)
answer = 0
v = counter[0]
if v >= 1:
    answer += v * (v+1) // 2

for i in range(N):
    if remain[i] == 0:
            continue
    for j in range(i+1, N):        
        diff = j - i
        if (remain[j] - remain[i] * (10**diff)) % P == 0:
            answer += 1

print(answer)


### FIXED CODE ###

import sys
from collections import Counter

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, P = lr()
S = sr()
# 累積和
remain = [0] * N
cur = 0
answer = 0
S_rev = S[::-1]
power = 1
for i in range(N):
    if i >= 1:
        power *= 10
        power %= P
    num = cur + power * int(S_rev[i])
    cur = num % P
    remain[i] = cur

if P == 2 or P == 5:
    ind = (i for i, x in enumerate(S, 1) if int(x) % P == 0)
    answer = sum(ind)

else:
    counter = Counter(remain)
    answer += counter[0]
    for k, v in counter.items():
        answer += v * (v-1) // 2

print(answer)
### BUGGY CODE ###

N = [int(i) for i in input().split()]

answerList = []

for i in range(N[0]):
    for j in range(N[0] + 1):
        if j > i > 0:
            calculateList = [abs(j - i),
                             abs(abs(N[1] - i) + + 1 + abs(j - N[2])),
                             abs(abs(N[2] - i) + + 1 + abs(j - N[1]))]
            answerList.append(min(calculateList))

for i in range(N[0] - 1):
    print(answerList.count(i + 1))

### FIXED CODE ###

N = [int(i) for i in input().split()]

answerList = []

for i in range(N[0]):
    answerList.append(0)

for i in range(N[0]):
    if i > 0:
        for j in range(N[0]):
            if j + 1 > i > 0:
                calculateList = [abs(j + 1 - i),
                                 abs(N[1] - i) + 1 + abs(j + 1 - N[2]),
                                 abs(N[2] - i) + 1 + abs(j + 1 - N[1])]
                answer = min(calculateList)
                answerList[answer] = answerList[answer] + 1

for i in range(N[0] - 1):
    print(answerList[i + 1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)
n = int(input())
d = int(input())
p = 10**9+7
DP = {}
DP[-1] = [0]*d
DP[0] = [0]*d
DP[0][0] = 1
def dp(i):
    try:
        return DP[i]
    except:
        pass
    q, r = i//10, i % 10
    DP[i] = []
    for j in range(d):
        tmp = 0
        for k in range(r+1):
            tmp += dp(q)[(j-k) % d]
        for k in range(r+1, 10):
            tmp += dp(q-1)[(j-k) % d]
        DP[i].append(tmp % p)
    return DP[i]
print((dp(n)[0]-1) % p)


### FIXED CODE ###

n = int(input())
d = int(input())
p = 10**9+7
if d == 1:
    print(n % p)
    exit()
N = [int(i) for i in list(str(n))]
DP0 = [0] * d
DP1 = [0] * d
DP1[0] += 1
for i in N:
    DP0_ = [0] * d
    DP1_ = [0] * d
    for r in range(d):
        for j in range(i):
            DP0_[r] += DP1[(r-j) % d]
            DP1_[r] += DP1[(r-j) % d]
        DP0_[r] += DP0[(r-i) % d]
        DP1_[r] += DP1[(r-i) % d]
        for j in range(i+1, 10):
            DP0_[r] += DP0[(r-j) % d]
            DP1_[r] += DP0[(r-j) % d]
        DP0_[r], DP1_[r] = DP0_[r] % p, DP1_[r] % p
    DP0, DP1 = DP0_, DP1_
print((DP1[0]-1+p) % p)
### BUGGY CODE ###

from collections import defaultdict

N, Q = map(int, input().split())
V = {v: 0 for v in range(1, N+1)}
E = {v: [] for v in V.keys()}
for _ in range(N-1):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
added = defaultdict(int)
for _ in range(Q):
    p, x = map(int, input().split())
    added[p] += x
stack = [(1, added[1])]
visited = {v: False for v in V.keys()}
while stack:
    v, value = stack.pop()
    visited[v] = True
    V[v] += value
    for u in E[v]:
        if not visited[u]:
            stack.append((u, value + added[u]))
print(*[val for val in V.values()])

### FIXED CODE ###

N, Q = map(int, input().split())
V = {v: 0 for v in range(1, N+1)}
E = {v: [] for v in V.keys()}
for _ in range(N-1):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
added = {v: 0 for v in V.keys()}
for _ in range(Q):
    p, x = map(int, input().split())
    added[p] += x
stack = [(1, added[1])]
visited = {v: False for v in V.keys()}
while stack:
    v, value = stack.pop()
    visited[v] = True
    V[v] += value
    for u in E[v]:
        if not visited[u]:
            stack.append((u, value + added[u]))
print(*[val for val in V.values()])
### BUGGY CODE ###

n,p=map(int,input().split())
if n==1:
	print(p)
	exit()
ans=1
for i in range(2,int(p**0.5)+2):
	if p<pow(i,n):
		break
	while p%(pow(i,n))==0:
		if p%(pow(i,n))==0:
			ans*=i
			p//=(pow(i,n))
print(ans)

### FIXED CODE ###


n,p=map(int,input().split())
ans=[]
for i in range(2,int(p**0.5)+1):
	cnt=0
	while p%i==0:
		p//=i
		cnt+=1
	if cnt>0:
		ans.append([i,cnt])
ans.append([p,1])
ret=1
for i in range(len(ans)):
	ret*=pow(ans[i][0],(ans[i][1]//n))
print(ret)
### BUGGY CODE ###

N = int(input())
X = list(map(int, input().split()))

for i in range(N):
    l = X[:i]
    r = X[i+1:]
    B = []
    B.extend(l)
    B.extend(r)
    B.sort()
    print(B[int((len(B)-1)/2)])


### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))

Y = sorted(X)

l = Y[N//2-1]
r = Y[N//2]

for x in X:
    if l >= x:
        print(r)
    else:
        print(l)
### BUGGY CODE ###

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

l=list(map(int,input().split()))

for i in range(m):
    j= l.index(max(l))
    l[j] = l[j]//2


print(sum(l))


### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(lambda x: -int(x) ,input().split()))
heapq.heapify(a)

for _ in range(m):
    tmp = -heapq.heappop(a)
    tmp //= 2
    heapq.heappush(a,-tmp)
print(-sum(a))
### BUGGY CODE ###

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

if sum(A) <= K:
    a_max = N
    ans = N

else:
    a_total = 0
    for i in range(N):
        a_total += A[i]
        if a_total > K:
            break
    a_max = i
    ans = a_max


for i in range(a_max+1)[::-1]:
    total = sum(A[:i])
    #print('b total: ', total)
    if total + sum(B) <= K:
        ans = max(ans, i + M)
    else:
        for j in range(M):
            total += B[j]
            #print('a total: ', total)
            if total > K:
                flag = True
                break
        ans = max(ans, i + j)
    #print('ans: ', ans)
    #print()

print(ans)

### FIXED CODE ###

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

a, b = [0]*N, [0]*M

total = 0
for i in range(N):
    total += A[i]
    a[i] = total

a = [0] + a

total = 0
for i in range(M):
    total += B[i]
    b[i] = total

b = [0] + b

ans, j = 0, M
for i in range(N+1):
    if a[i] > K:
        break
    while b[j] + a[i] > K:
        j -= 1
    #print(a[i], b[j], i, j)
    ans = max(ans, i + j)

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

import sys


a,b,n = (int(i) for i in input().split())


ans =0

for i in range(1,n+1):
    temp = a*i//b-a*(i//b)
    if temp > ans:
        ans = temp


print(ans)


### FIXED CODE ###

import sys


a,b,n = (int(i) for i in input().split())


if n < b-1:
    ans = (a*n//b)

else:
    ans = ((b-1)*a)//b



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

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

for i in range(N):
    ans = ans*A[i]

if ans > 10**18:
    ans=-1

print(ans)

### FIXED CODE ###

import sys
n = input()
list_num =list(map(int,input().split()))
output = 1
if 0 in list_num:
    print(0)
    sys.exit()
for i in list_num:
    output = output * i
    if output > 10 ** 18:
        print(-1)
        sys.exit()
print(output)