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

a = []
n = int(input())
for _ in range(n):
    s, i = input().split()
    a += [(s, int(i))]
b = a[:]

def partition(a, left, right):
    standard = a[right][1]
    cnt = left
    for i in range(left, right+1):
        if i == right:
            if a[i][1] <= standard:
                a[i],a[cnt] = a[cnt], a[i] 
        elif a[i][1] <= standard:
            a[cnt],a[i] = a[i], a[cnt]
            cnt += 1
    return cnt

def quickSort(a, left = 0, right = len(a) - 1):
    if 1 <= right - left:
        cnt_ = partition(a, left, right)
        quickSort(a,left, cnt_ - 1)
        quickSort(a,cnt_ + 1, right)

quickSort(a, 0 , len(a)-1)

#bubble sort


for i in range(n-1):
    for j in range(n-1-i):
        if b[j][1] > b[j+1][1]:
            b[j], b[j+1] = b[j+1], b[j]
        

if a == b:
    print('Stable')
else:
    print('Not stable')

for i in range(n):
    print(*a[i])


### FIXED CODE ###

a = []
b = {}
n = int(input())
for _ in range(n):
    s, i = input().split()
    a += [(s, int(i))]
    b.setdefault(int(i), []).append(s)
b = {val: iter(s).__next__ for val, s in b.items()}

def partition(a, left, right):
    standard = a[right][1]
    cnt = left
    for i in range(left, right):
        if a[i][1] <= standard:
            a[cnt],a[i] = a[i], a[cnt]
            cnt += 1
    a[cnt],a[right] = a[right], a[cnt]
    return cnt

def quickSort(a, left = 0, right = len(a) - 1):
    if 1 <= right - left:
        cnt_ = partition(a, left, right)
        quickSort(a,left, cnt_ - 1)
        quickSort(a,cnt_ + 1, right)

quickSort(a, 0 , len(a)-1)

ok = 1
for s, i in a:
    if b[i]() != s:
        ok = 0
print(['Not stable','Stable'][ok])


for i in range(n):
    print(*a[i])
### BUGGY CODE ###

import sys
def main():

    n=int(input())
    p=tuple(map(int,input().split()))
    s=1
    for i in range(n):
        s*=p[i]
    if s>=10**18+1:
        print(-1)
        sys.exit()
    print(s)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
def main():

    n=int(input())
    p=list(map(int,input().split()))
    s=1
    p=sorted(p)
    for i in p:
        s*=i
        if i==0:
            print(0)
            sys.exit()
        elif s>=10**18+1:
            print(-1)
            sys.exit()
    print(s)

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

def main():
    N, Q = input().split()
    S = input()

    for i in range(int(Q)):
        a, b = (int(x) for x in input().split())
        sss = S[a - 1: b]
        sss = sss.replace("AC", "1")
        count = sss.count("1")
        print(count)

    return 0


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, Q = map(int, input().split())
    S = input()

    list = [0] * (N + 1)

    for i in range(N):
        list[i + 1] = list[i] + (1 if S[i:i + 2] == "AC" else 0)

    for i in range(Q):
        a, b = map(int, input().split())
        output = list[b - 1] - list[a - 1]
        print(output)


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

def main():
    from collections import Counter
    N, P = (int(i) for i in input().split())
    S = input()

    ans = 0
    if P == 5 or P == 2:
        for j in range(1, N+1):
            # j文字取る
            num = int(S[:j])
            if num % P == 0:
                ans += j
    else:
        S = [s for s in S]
        acc = [0]*(N+1)
        d = 1
        for i, s in enumerate(S[::-1]):
            # print(i, s)
            s = int(s)
            acc[i+1] = (s * d + acc[i]) % P
            d *= 10
            d %= P
        c = Counter(acc)
        # print(acc, c)
        ans = sum(v*(v-1)//2 for v in c.values())
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import Counter
    N, P = (int(i) for i in input().split())
    S = [int(s) for s in input()]

    ans = 0
    if P == 5 or P == 2:
        for i, s in enumerate(S, start=1):
            # j文字取る
            if s % P == 0:
                ans += i
    else:
        acc = [0]*(N+1)
        d = 1
        for i, s in enumerate(S[::-1], start=1):
            # print(i, s)
            acc[i] = (s * d + acc[i-1]) % P
            d *= 10
            d %= P
        c = Counter(acc)
        # print(acc, c)
        ans = sum(v*(v-1)//2 for v in c.values())
    print(ans)


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

import itertools
n = int(input())

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

sans = list(itertools.combinations(ls,3))
k = len(sans)
count = 0
for i in range(k):
    a = list(itertools.permutations(sans[i]))
    b = 0
    for i in range(6):
        if (a[i])[0] < (a[i])[1] + (a[i])[2]:
            b += 1
    if b == 6:
        count += 1
print(count)


### FIXED CODE ###

import bisect
n = int(input())

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

ls.sort()
count = 0
for i in range(n):
    for j in range(i + 1,n):
        t = ls[i] + ls[j]
        index = bisect.bisect_left(ls,t)
        count += max(0,index - j - 1)

print(count)
### BUGGY CODE ###

n,k = map(int,input().split())
s=input()
li=[]
li_z=[]
li_o=[]


    
check="1"
seq=0
for i in s:
    if check!=i:
        check=i
        li.append(seq)
        seq=1
    else:
        seq+=1
        
li.append(seq)

for  i in range(len(li)):
    if i%2==0:
        li_o.append(li[i])
    else:
        li_z.append(li[i])
    
if s[n-1]=="0":
    li_o.append(0)


if len(li_o)<=k:
    print(n)
else:
    m=0
    for i in range(len(li_o)-k):
        tmp=sum(li_o[i:i+k+1])+sum(li_z[i:i+k])
        m=max(tmp,m)
        
    print(m)

### FIXED CODE ###

n,k = map(int,input().split())
s=input()
li=[]
li_z=[]
li_o=[]


    
check="1"
seq=0
for i in s:
    if check!=i:
        check=i
        li.append(seq)
        seq=1
    else:
        seq+=1
        
li.append(seq)

for  i in range(len(li)):
    if i%2==0:
        li_o.append(li[i])
    else:
        li_z.append(li[i])
    
if s[n-1]=="0":
    li_o.append(0)


if len(li_o)<=k:
    print(n)
else:
    m=sum(li_o[0:0+k+1])+sum(li_z[0:0+k])
    tmp=m
    for i in range(1,len(li_o)-k):
        tmp=tmp-li_o[i-1]+li_o[i+k]-li_z[i-1]+li_z[i+k-1]
        m=max(tmp,m)
        
    print(m)
### BUGGY CODE ###

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

ans = 1
for i in range(1, N):
    if min(P[:i]) >= P[i]:
        ans += 1
print(ans)


### FIXED CODE ###

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

# N = 5
# P = [4, 2, 5, 1, 3]

ans = 0
min = 2 * 10**5
for i in range(0, N):
    # i = 1
    if min > P[i]:
        min = P[i]
    if P[i] <= min:
        ans += 1

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

# vim: fileencoding=utf-8


def main():
    N = int(input())
    for n in range(1, N + 1):
        ans = 0
        if n <= 5:
            print(ans)
            continue

        zMax = int((N + 1) / 6) + 1
        for x in range(1, int((N + 1) / 6) + 1):
            tx = x ** 2
            if tx + x >= n or x >= zMax:
                break
            for y in range(x, int((N + 1) / 6) + 1):
                ty = tx + y ** 2 + x * y
                if ty + y + x >= n or y >= zMax:
                    break
                for z in range(y, int((N + 1) / 6) + 1):
                    t = ty + z ** 2 + y * z + z * x
                    if t == n:
                        if x == y and x == z:
                            ans += 1
                        elif x == y or y == z:
                            ans += 3
                        else:
                            ans += 6
                        if z <= zMax:
                            zMax = z
                        break
                    if t >= n:
                        break
        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

# vim: fileencoding=utf-8


def main():
    N = int(input())
    ans = [0] * N
    for x in range(1, 101):
        for y in range(1, 101):
            for z in range(1, 101):
                t = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x - 1
                if t >= len(ans):
                    break
                ans[t] += 1

    print(*ans)


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

import sys
def input():
    return sys.stdin.readline()[:-1]

N,X,Y = map(int,input().split(' '))
M = -(-(X+Y)//2)
ANS = []
for i in range(N):
    for j in range(i+1,N):
        d = j-i
        dd = abs(X-1-i)+1+abs(Y-1-j)
        ANS.append(min(d,dd))
ANS.sort()
L = len(ANS)
cnt = 0
ans = [0]*(N-1)
while cnt != L:
    k = ANS[cnt]
    ans[k-1] += 1
    cnt += 1
for i in range(N-1):
    print(ans[i])

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

N,X,Y = map(int,input().split(' '))
M = -(-(X+Y)//2)
ANS = []
for i in range(N):
    for j in range(i+1,N):
        d = j-i
        dd = abs(X-1-i)+1+abs(Y-1-j)
        ANS.append(min(d,dd))
ANS.sort()
L = len(ANS)
cnt = 0
ans = [0]*(N-1)
while cnt != L:
    k = ANS[cnt]
    ans[k-1] += 1
    cnt += 1
for i in range(N-1):
    print(ans[i])
### BUGGY CODE ###

import sys
import numpy as np

read=sys.stdin.read
readline=sys.stdin.readline

def main():
  wb={'W':0,'B':1}
  n,k=map(int,readline().split())
  xyc=[l.split() for l in read().splitlines()]
  xyc=[[int(lst[0]) % (2*k),int(lst[1]) % (2*k),wb[lst[2]]] for lst in xyc]
  mat=np.zeros((2,4*k+1,4*k+1),dtype='int64')
  cand=np.zeros((2*k+1,2*k+1),dtype='int64')
  for i in range(4):
    for x,y,c in xyc:
      mat[c,:x+2+2*k*(i&1),:y+2+2*k*(i>>1&1)]+=1
  cand=mat[0,k:3*k+1,k:3*k+1]+mat[0,:2*k+1,:2*k+1]-mat[0,k:3*k+1,:2*k+1]-mat[0,:2*k+1,k:3*k+1]\
      +mat[0,2*k:4*k+1,2*k:4*k+1]+mat[0,k:3*k+1,k:3*k+1]-mat[0,2*k:4*k+1,k:3*k+1]-mat[0,k:3*k+1,2*k:4*k+1]\
      +mat[1,2*k:4*k+1,k:3*k+1]+mat[1,k:3*k+1,:2*k+1]-mat[1,2*k:4*k+1,:2*k+1]-mat[1,k:3*k+1,k:3*k+1]\
      +mat[1,k:3*k+1,2*k:4*k+1]+mat[1,:2*k+1,k:3*k+1]-mat[1,:2*k+1,2*k:4*k+1]-mat[1,k:3*k+1,k:3*k+1]
  print(np.max(cand))
  
if __name__=='__main__':
  main()
  
  
  


### FIXED CODE ###

import sys
import numpy as np

read=sys.stdin.read
readline=sys.stdin.readline

def main():
  wb={'W':1,'B':0}
  n,k=map(int,readline().split())
  xyc=[l.split() for l in read().splitlines()]
  xy=[[int(lst[0]) % (2*k),(int(lst[1])+k*wb[lst[2]]) % (2*k)] for lst in xyc]
  mat=np.zeros((k+1,2*k+1),dtype='int64')
  cand=np.zeros((k+1,k+1),dtype='int64')
  for e in xy:
    f0=e[0]>=k
    f1=e[1]>=k
    mat[e[0]-f0*k+1,e[1]+(-1)**f1*f0*k+1]+=1
  mat=np.cumsum(mat,axis=0)
  mat=np.cumsum(mat,axis=1)
  cand=mat[k,2*k]-mat[k,k:2*k+1]+mat[k,:k+1]\
       -np.reshape(mat[:k+1,2*k],(k+1,1))+2*mat[:,k:2*k+1]-2*mat[:,:k+1]
  print(max(np.max(cand),mat[k,2*k]-np.min(cand)))
  
if __name__=='__main__':
  main()
### BUGGY CODE ###

S = list(input())
S = list(map(int, S))

cnt = 0
renew=True
while S and renew:
    nextS = []
    renew = False
    lS = len(S)
    i = 0
    while (i <= lS-1):
        if i == lS-1:
            nextS.append(S[i])
            break
        a = S[i]
        b = S[i+1]
        if a != b:
            cnt += 1
            i+=2
            renew = True
        else:
            nextS.append(a)
            i+=1
    S = nextS
print(cnt*2)

### FIXED CODE ###

from collections import Counter
S = list(input())
S = list(map(int, S))

cnt = Counter(S)
setS = set(S)
if len(setS) == 1:
    print(0)
else:
    print(2*min(cnt[0], cnt[1]))
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter
from heapq import heappush, heappop
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

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

H, W, D =na()
A = [na() for _ in range(H)]
Q = ni()
A = np.array(A)
d = {}
for i in range(H):
    for j in range(W):
        d[A[i][j]] = (i, j)
for _ in range(Q):
    ans = 0
    l, r = na()
    t = (r - l) // D
    for j in range(t):
        px, py = d[l + j * D]
        nx, ny = d[l + (j + 1) * D]
        #print(px, py, nx, ny)
        ans += abs(px - nx) + abs(py - ny)
    print(ans)

### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
#from operator import itemgetter
#from heapq import heappush, heappop
#import numpy as np
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

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

H, W, D =na()
A = [na() for _ in range(H)]
Q = ni()
d = {}
for i in range(H):
    for j in range(W):
        d[A[i][j]] = (i, j)

dp = [0 for _ in range(H*W+1)]

for i in range(1, D+1):
    dp[i] = 0

for i in range(D+1, H*W+1):
    ni, nj = d[i]
    pi, pj = d[i - D]
    dp[i] = dp[i - D] + abs(ni - pi) + abs(nj - pj)

for i in range(Q):
    ans = 0
    l, r = na()
    ans = dp[r] - dp[l]
    print(ans)
### BUGGY CODE ###


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

import itertools
com = list(itertools.combinations(L, 3))

count = 0
for i in com:
    #print(i)
    if (i[0] < i[1] + i[2]) and (i[1] < i[0] + i[2]) and (i[2] < i[1] + i[0]):
        count += 1

print(count)

### FIXED CODE ###

def fnt(arr,n): 
  
     
     
     
    count = 0
  
     
    for i in range(0,n-2): 
  
         
        k = i + 2
  
        # Fix the second element 
        for j in range(i+1,n): 
  
             
            while (k < n and arr[i] + arr[j] > arr[k]): 
                k += 1
  
             
            if(k>j): 
                count += k - j - 1
  
    return count
 
 
n=int(input())
arr=input()
arr=arr.split()
arr=list(map(int,arr))
arr.sort()
print(fnt(arr,n))
### BUGGY CODE ###

import sys
import itertools
input = sys.stdin.readline
inf = 200000000
n, m, r = map(int,input().split())
rs = list(map(int,input().split()))
d = [[inf] * (n+1) for j in range(n+1)]
for i in range(n+1):
    d[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    d[a][b] = d[b][a] = c
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(i+1,n+1):
            d[i][j] = d[j][i] = min(d[i][j], d[i][k] + d[k][j])
p = list(itertools.permutations(range(r)))
s = inf
for q in p:
    t = 0
    for i in range(r-1):
        t += d[rs[q[i]]][rs[q[i+1]]]
    if s > t:
        s = t
print(s)

### FIXED CODE ###

import sys
import itertools
input = sys.stdin.readline
inf = 200000000
n, m, r = map(int,input().split())
rs = list(map(int,input().split()))
d = [[inf] * (n+1) for j in range(n+1)]
for i in range(n+1):
    d[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    d[a][b] = d[b][a] = c
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(i+1,n+1):
            d[i][j] = d[j][i] = min(d[i][j], d[i][k] + d[k][j])
p = list(itertools.permutations(range(r)))
s = inf
for q in p:
    t = 0
    for i in range(r-1):
        t += d[rs[q[i]]][rs[q[i+1]]]
    if s > t:
        s = t
print(s)
### BUGGY CODE ###

S=list(input())
cnt=0
a=[0]*len(S)
for i in range(len(S)-1,-1,-1):
  if S[i]=='W':
    cnt=S[:i+1].count('B')
    a[i]=cnt
print(sum(a))

### FIXED CODE ###

S=list(input())
cnt=0
ans=0
for i in range(len(S)-1,-1,-1):
  if S[i]=='W':
    cnt+=1
  else:
    ans+=cnt

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

import numpy as np

n,p = map(int, input().split())
s = list(map(int, input().strip()))

dp = np.zeros(p,dtype = int)

count = 0
d = 1
for i in range(n):
    ne_ar = np.zeros(p,dtype = int)
    if(p == 2 or p == 5):
        ne = int(s[n-i-1]) % p
        if(ne == 0):
            dp[0] += 1
        count += dp[0]
    else:
        ne = (int(s[n-i-1]) * d) % p
        ne_ar[ne:] += dp[:(p-ne)]
        ne_ar[:ne] += dp[(p-ne):]
        ne_ar[ne] += 1
        dp = ne_ar
        d *= 10
        d %= p
        count += ne_ar[0]

print(count)

### FIXED CODE ###

n,p = map(int, input().split())
s = list(map(int, input().strip()))

count = 0

if(p == 2 or p == 5): #10と互いに素ではない場合
    co = 0
    for i in range(n): #1の位から順に数を追加していく
        ne = int(s[n-i-1]) % p
        if(ne == 0):
            co += 1
        count += co
    print(count)
else:
    sta = [0]*p
    sta[0] += 1
    d = 1
    co = 0
    for i in range(n):
        ne = int(s[n-i-1]) * d % p
        co += ne
        co %= p
        sta[co] += 1
        d *= 10
        d %= p
    for i in range(p):
        count += sta[i] * (sta[i]-1) // 2
    print(count)
### BUGGY CODE ###

import math
N, K = map(int,input().split())
logs = list(map(int,input().split()))
a = 0
b = max(logs)
while math.ceil(a) != math.ceil(b):
    c = (a+b)/2
    times = []
    for i in logs:
        times.append(math.floor(i/c))
    if sum(times) > K:
        a = (a+b)/2
    else:
        b = (a+b)/2
print(math.ceil(b))

### FIXED CODE ###

import math
N, K = map(int,input().split())
logs = list(map(int,input().split()))
a = 0
b = max(logs)
b_memo = set()
count=0
flg =0
while math.ceil(a) != math.ceil(b):
    c = (a+b)/2
    times = []
    for i in logs:
        times.append(math.floor(i/c))
    if sum(times) > K:
        a = c
    else:
        b = c
    if b - a < 0.001:
        count +=1
    if count >20:
        flg+=1
        break
if flg == 0:         
    print(math.ceil(b))
else:
    a = math.ceil(a)
    times = []
    for j in logs:
        times.append(math.floor(i/a))
    if sum(times) > K:
        print(math.ceil(b))   
    else:
        print(math.ceil(a))
### BUGGY CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
for i in range(n):
  x=a[i]
  a.pop(i)
  print(max(a))
  a.insert(i,x)

### FIXED CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
max1=1
m=0
for i in range(n):
  if max1<a[i]:
    max1=a[i]
    m=i
a.pop(m)
max2=max(a)
a.insert(m,max1)
for i in range(n):
  if i!=m:
    print(max1)
  else:
    print(max2)
### BUGGY CODE ###

import numpy as np
n=int(input())
s=np.zeros(100001,dtype='int32')
a=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
for i in range(n+1):
    s[i]=i
for i in range(1,12):
    if a[i]<=n :
        k=a[i]
        for j in range(k,n+1):
            if s[j]>s[j-k]+1:
                s[j]=s[j-k]+1
print(s[n])


### FIXED CODE ###

n=int(input())
s=[i for i in range(n+1)]
a=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
for i in range(n+1):
    s[i]=i
for i in range(1,12):
    if a[i]<=n :
        k=a[i]
        for j in range(k,n+1):
            if s[j]>s[j-k]+1:
                s[j]=s[j-k]+1
print(s[n])
### BUGGY CODE ###

import sys
from copy import deepcopy
from functools import lru_cache
sys.setrecursionlimit(10**6)

def main():
    #node i is list of [child,size,comb] connected i
    #return [size,comb]
    @lru_cache(maxsize=1000000)
    def deep(i,parent):
        if len(node[i])==1 and parent!=-1:
            return [1,1]
        mysize=0
        mycomb=1
        for j in node[i]:
            if j!=parent:
                size,comb=deep(j,i)
                mysize+=size
                mycomb=(mycomb*comb)%mod
                mycomb=(mycomb*inv[size])%mod
        mycomb=(mycomb*fact[mysize])%mod
        return [mysize+1,mycomb]

    F = 2*10**5
    mod = 10**9+7
    fact = [1]*F
    inv = [1]*F
    for i in range(2,F):
        fact[i]=(fact[i-1]*i)%mod
    inv[F-1]=pow(fact[F-1],mod-2,mod)
    for i in range(F-2,1,-1):
        inv[i] = (inv[i+1]*(i+1))%mod
    
    n=int(input())
    node=[[] for i in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        node[a-1].append(b-1)
        node[b-1].append(a-1)
    for i in range(n):
        print(deep(i,-1)[1])

main()

### FIXED CODE ###

n=int(input())
F = n+5
mod = 10**9+7
fact = [1]*F
inv = [1]*F
for i in range(2,F):
    fact[i]=(fact[i-1]*i)%mod
inv[F-1]=pow(fact[F-1],mod-2,mod)
for i in range(F-2,1,-1):
    inv[i] = (inv[i+1]*(i+1))%mod

#invnum[0] cant be used
invnum=[fact[i-1]*inv[i] for i in range(n)]

graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

stack=[0]
order=[0]
parent=[-1]*n
comb=[0]*n
size=[1]*n

# BFS order
while stack:
    node = stack.pop()
    for neib in graph[node]:
        if neib!=parent[node]:
            stack.append(neib)
            order.append(neib)
            parent[neib]=node

#calc size including self
for node in order[n-1:0:-1]:
    size[parent[node]]+=size[node]

#calc root comb
comb[0]=fact[n-1]
for node in range(1,n):
    comb[0]*=invnum[size[node]]
    comb[0]%=mod

#calc all comb
for node in order[1:]:
    comb[node]=comb[parent[node]]*size[node]*invnum[n-size[node]]%mod

print(*comb,sep="\n")
### BUGGY CODE ###

# B - Multiplication 2
from functools import reduce
from operator import mul


def main():
    _, *A = map(int, open(0).read().split())
    prod = reduce(mul, A)
    print(prod if prod <= 10 ** 18 else -1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

# B - Multiplication 2
def main():
    _, *A = map(int, open(0).read().split())
    if 0 in A:
        print(0)
        return 
    prod = 1
    LIM = 10 ** 18
    for i in A:
        prod *= i
        if prod > LIM:
            print(-1)
            return
    print(prod)


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

n=int(input())
A=list(map(int,input().split()))
divsors=[]
for i in range(n):
  for j in range(1,int(A[i]**(1/2)+1)):
    if A[i]%j==0:
      divsors.append(j)
      if j!=A[i]//j:
        divsors.append(A[i]//j)
set_divsors=sorted(list(set(divsors)))[::-1]
for i in range(len(set_divsors)):
  a=divsors.count(set_divsors[i])
  if a==n or a==n-1:
    print(set_divsors[i])
    break

### FIXED CODE ###

n=int(input())
A=[]*n
A[:]=map(int,input().split())

def gcd(a,b):
    while b:
        a,b=b,a%b
    return a
      
left=[0]*n
right=[0]*n
for i in range(1,n):
  left[i]=gcd(left[i-1],A[i-1])
  right[n-1-i]=gcd(right[n-i],A[n-i])

ans=0
for i,j in zip(left,right):
  ans=max(ans,gcd(i,j))
print(ans)
### BUGGY CODE ###

import heapq
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))
F = list(map(int, sys.stdin.readline().split()))

A.sort()
F.sort(reverse=True)

heap = []
for a, f in zip(A, F):
    heap.append((-a * f, a, f))
heapq.heapify(heap)
for _ in range(K):
    _, a, f = heap[0]
    if a == 0:
        break
    a -= 1
    heapq.heapreplace(heap, (-a * f, a, f))

ans = 0
for af, _, _ in heap:
    ans = max(ans, -af)
print(ans)


### FIXED CODE ###

import heapq
import math
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))
F = list(map(int, sys.stdin.readline().split()))

if N == 1:
    a = A[0]
    f = F[0]
    ans = max(a - K, 0) * f
    print(ans)
    exit()

A = np.array(A, dtype=int)
F = np.array(F, dtype=int)
A.sort()
F.sort()
F = F[::-1]


def required_k(score):
    # score を出すために必要な K
    return np.ceil(np.maximum(A - score / F, 0)).sum()


ok = (A * F).max()
ng = -1
while abs(ok - ng) > 1:
    score = (ok + ng) // 2
    if required_k(score) <= K:
        ok = score
    else:
        ng = score
print(ok)