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

import sys
input = sys.stdin.buffer.readline # 入出力高速化

class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.depth = N.bit_length()

    def _bitsum(self, i):
        ret = 0
        while i:
            ret += self.tree[i]
            i ^= i & -i
        return ret

    def bitsum(self, l, r=None):
        if r is None:
            return self._bitsum(l)
        else:
            return self._bitsum(r) - self._bitsum(l)

    def bitadd(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        return

    def lower_bound(self, x):
        sum_ = 0
        pos = 0
        v = 1 << self.depth
        for i in range(self.depth, -1, -1):
            k = pos + v
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += v
            v >>= 1
        return pos

def main():
    N, Q = map(int, input().split())
    tl = list() # イベントタイムライン
    points = list()
    for _ in range(N):
        S, T, X = map(int, input().split())
        tl.append((S-X, 1, X)) # insert
        tl.append((T-X, 0, X)) # erase
        points.append(X)
        
    for _ in range(Q):
        D = int(input())
        tl.append((D, 2, 0)) # min
    
    tl.sort()
    points.sort()
    M = len(points)
    comp = {e:i for i, e in enumerate(points)} # 座標圧縮
    B = BIT(M + 20)
 
    for t, c, x in tl:
        if c == 0: # erase
            B.bitadd(comp[x], -1)
        elif c == 1: # insert
            B.bitadd(comp[x], 1)
        else: # min
            idx = B.lower_bound(1)
            print(-1 if idx > M + 10 else points[idx])
    return
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()

from heapq import heappush, heappop 

running = []
events = []
delete = set()

n, q = map(int, input().split())
for _ in range(n):
    s, t, x = map(int, input().split())
    time = max(s - x, 0)
    if t - x < 0:
        continue
    events.append((s - x, x, 1)) # 追加イベント
    events.append((t - x, x, 0)) # 削除イベント
events.sort()
ans = []
idx = -1
for _ in range(q):
    d = int(input())
    if d >= events[-1][0]:
        print(-1)
        #ans.append(-1)
        continue
    while events[idx + 1][0] <= d:
        idx += 1
        if events[idx][2] == 1:
            heappush(running, events[idx][1])
            delete.discard(events[idx][1])
        else:
            delete.add(events[idx][1])
    flag = 1
    while running:
        x = heappop(running)
        if x not in delete:
            heappush(running, x)
            print(x)
            #ans.append(x)
            flag = 0
            break
    if flag:
        print(-1)
### BUGGY CODE ###

N, A = map(int, input().split())
x = [int(i) for i in input().split()]
 
lim = sum(x)
dp = [[0]*(lim + 1) for i in range(N + 1)]
 
dp[0][0] = 1
 
for i in range(N):
    for k in range(N, 0, -1):
        for v in range(lim, -1, -1):
            if v - x[i] < 0:
                break
            dp[k][v] += dp[k - 1][v - x[i]]
 
ans = 0

for k in range(1, N + 1):
    if k*A > lim:
        break
    ans += dp[k][k*A]

print(ans)

### FIXED CODE ###

import sys
from collections import Counter

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N, A = map(int, input().split())
    x = [int(i) for i in input().split()]

    # 3d DP
    max_x = max(x)

    dp = [[[0] * (max_x * N + 1) for j in range(N + 1)]
                                 for i in range(N + 1)]

    dp[0][0][0] = 1

    for i in range(0, N):
        for k in range(0, N + 1):
            for y in range(max_x * N + 1):
                if dp[i][k][y]:
                    dp[i + 1][k][y] += dp[i][k][y]
                    dp[i + 1][k + 1][y + x[i]] += dp[i][k][y]

            # print(dp[i][k])
        # print()

    cnt = 0
    for k in range(1, N + 1):
        for y in range(1, max_x * N + 1):
            if y // k == A and y % k == 0:
                cnt += dp[N][k][y]

    print(cnt)

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

def main():
    N = int(input())
    Ass = tuple(tuple(map(int, input().split())) for _ in range(N))

    dp = [0 for _ in range(N)]
    index = [0 for _ in range(N)]
    flag = True
    cnt = 0
    while flag:
        flag = False
        for i, As in enumerate(Ass):
            if index[i] >= N - 1:
                continue
            t = As[index[i]] - 1
            if index[t] >= N - 1:
                continue
            if Ass[t][index[t]] == i + 1:
                index[t] += 1
                index[i] += 1
                dp[t] = dp[i] = max(dp[t], dp[i]) + 1
                cnt += 1
                flag = True
    if cnt != N * (N - 1) // 2:
        print(-1)
    else:
        print(max(dp))

main()

### FIXED CODE ###

from collections import deque
 
N = int(input())
Ass = tuple(deque(map(int, input().split())) for _ in range(N))
 
dp = [0 for _ in range(N)]
Q = set(range(N))
ans = -1
while Q:
    ans += 1
    Q2 = Q.copy()
    Q.clear()
    for i in Q2:
        if not Ass[i]:
            continue
        t = Ass[i][0] - 1
        if not Ass[t]:
            continue
        if Ass[t][0] == i + 1:
            Q.add(i)
            Q.add(t)
    for i in Q:
        Ass[i].popleft()

if any(Ass):
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
H = [int(input()) for _ in range(n)]
H = sorted(H)
ans = float("INF")
for i in range(n - k + 1):
  selected = H[i:k + i]
  ans = min(ans,max(selected) - min(selected))
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
H = sorted([int(input()) for _ in range(n)])
ans = float("INF")
for i in range(n - k + 1):
  diff = H[k + i -1] - H[i]
  ans = min(ans,diff)
print(ans)
### BUGGY CODE ###

#import sys
#input = sys.stdin.readline

#A1 ~ Aiまでの和 O(logN)
#A1 ~ Aiまでの和 O(logN)
def BIT_query(BIT,idx):
    res_sum = 0
    if idx == 0:
        return 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(BIT,idx,x,n):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

def main():
    N, Q = map( int, input().split())
    C = list( map( int, input().split()))
    LR = [ tuple( map( int, input().split())) for _ in range(Q)]
    LRI = []
    for i, x in enumerate(LR):
        LRI.append((x[1], x[0], i))
    LRI.sort()
    lastAppend = [-1]*(N+1)
    BIT = [0]*(N+1)
    ANS = [0]*Q
    now = 1
    for r, l, i in LRI:
        while now <= r:
            c = C[now-1]
            if lastAppend[c] == -1:
                BIT_update(BIT, now, 1,N)
            else:
                BIT_update(BIT, now, 1,N)
                BIT_update(BIT, lastAppend[c],-1,N)
            lastAppend[c] = now                
            now += 1
        ANS[i] = BIT_query(BIT,r) - BIT_query(BIT,l-1)
    print( "\n".join( map( str, ANS)))
    
    

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, Q = map( int, input().split())
    C = list( map( int, input().split()))
    LRI = []
    for i in range(Q):
        l, r = map( int, input().split())
        LRI.append((r,l,i))
    LRI.sort(key=lambda x:x[0])
    lastAppend = [-1]*(N+1)
    BIT = [0]*(N+1)
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        if idx == 0:
            return 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= N:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    ANS = [0]*Q
    now = 1
    for r, l, i in LRI:
        while now <= r:
            c = C[now-1]
            if lastAppend[c] == -1:
                BIT_update(now, 1)
            else:
                BIT_update( now, 1)
                BIT_update(lastAppend[c],-1)
            lastAppend[c] = now                
            now += 1
        ANS[i] = BIT_query(r) - BIT_query(l-1)
    print( "\n".join( map( str, ANS)))
    
    

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

h,w = map(int,input().split())
mp = {}
for i in range(2):
    for j in range(h):
        tmp = input().split()
        for k in range(w):
            mp[(k,j,i)] = int(tmp[k])
mp2 = {}
for i in range(h):
    for j in range(w):
        mp2[(j,i)] = abs(mp[(j,i,0)]-mp[(j,i,1)])

mp3 = [[set() for e in range(h)] for i in range(w)]
mp3[0][0].add(mp2[(0,0)])
# print(mp3)
for i in range(w):
    for j in range(h):
        for k in mp3[i][j]:
            if i < w -1:
                a = mp2[(i+1,j)]
                mp3[i+1][j].add(abs(k-a))
                mp3[i+1][j].add(abs(k+a))
            if j < h -1:
                a = mp2[(i,j+1)]
                mp3[i][j+1].add(abs(k-a))
                mp3[i][j+1].add(abs(k+a))
print(min(mp3[w-1][h-1]))


### FIXED CODE ###

H, W = [int(x) for x in input().split()]
 
A = [[0]*W for i in range(H)]
for c in [1, -1]:
    for i in range(H):
        arr = [int(x) for x in input().split()]
        for j in range(W):
            A[i][j] += arr[j] * c
 
M = 160*80
dp = [[0]*W for i in range(H)]
dp[0][0] = 1 << M
for i in range(H):
    for j in range(W):
        if i > 0:
            dp[i][j] |= dp[i-1][j]
        if j > 0:
            dp[i][j] |= dp[i][j-1]
        a = abs(A[i][j])
        dp[i][j] = (dp[i][j] << a) | (dp[i][j] >> a)
 
ans = M
for i in range(2*M):
    if dp[H-1][W-1] & (1 << i) > 0:
        ans = min(ans, abs(M-i))
print(ans)
### BUGGY CODE ###

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

cum = [[0]*(N) for i in range(N)]
for i in range(N):
  c = 0
  for j in range(i, N):
    c += A[j]
    cum[i][j] = c

dp = [[0]*N for i in range(N)]

for n in range(1, N+1):
  for i in range(N-n):
    j = i + n
    min_cost = 0
    for k in range(i, j):
      if min_cost == 0:
        min_cost = dp[i][k] + dp[k+1][j]
      else:
        min_cost = min(min_cost, dp[i][k]+dp[k+1][j])
    
    dp[i][j] = min_cost + cum[i][j]

print(dp[0][N-1])

### FIXED CODE ###

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

cum = [[0]*(N) for i in range(N)]
for i in range(N):
  c = 0
  for j in range(i, N):
    c += A[j]
    cum[i][j] = c

dp = [[0]*N for i in range(N)]

def get_min_cost(i, j):
  global dp
  if dp[i][j] > 0:
    return dp[i][j]
  else:
    min_cost = 0
    for k in range(i, j):
      if min_cost == 0:
        min_cost = get_min_cost(i, k) + get_min_cost(k+1, j) + cum[i][j]
      else:
        cost = get_min_cost(i, k) + get_min_cost(k+1, j) + cum[i][j]
        min_cost = min(min_cost, cost)
    
    dp[i][j] = min_cost
    return dp[i][j]

print(get_min_cost(0, N-1))
### BUGGY CODE ###

a, b = [int(i) for i in input().split()]
num = 1
numb = 1
if abs(a-b) == 1:
    for i in range(a):
        num = (a-i)*num
    for i in range(b):
        numb = (b-i)*numb
    num = num*numb
elif abs(a-b) == 0:
    for i in range(a):
        num = (a-i)*num
    num = (num**2)*2
else:
    num = 0

print(num%(10**9+7))

### FIXED CODE ###

from math import factorial

a, b = [int(i) for i in input().split()]
num = 1
if abs(a-b) == 1:
    num = factorial(a)*factorial(b)
elif abs(a-b) == 0:
    num = factorial(a) * factorial(b) * 2
else:
    num = 0

print(num%(10**9+7))
### BUGGY CODE ###

N = int(input())
a = sorted(list(map(int, input().split())))
ans = 0
for x in range(a[0],a[-1]+1):
    cnt = 0
    for i in a:
        if abs(i-x) == 0 or abs(i-x) == 1:
            cnt += 1
    ans = max(cnt, ans)
print(ans)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
cnt = [0]*(10**7)
for i in a:
    cnt[i-1] += 1
    cnt[i] += 1
    cnt[i+1] += 1
print(max(cnt))
### BUGGY CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
B=[]
for k in range(N):
  A0=A[0]
  A.remove(A0)

  print(max(A))
  A.append(A0)

### FIXED CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
B=sorted(A)
A0=B[N-1]
A1=B[N-2]
for i in range(N):
  if A[i]!=A0:
    print(A0)
  else:
    print(A1)
### BUGGY CODE ###

s=input()
t=input()
dp=[[0]*(len(t)+1) for _ in range(len(s)+1)]
for i in range(len(s)):
  for j in range(len(t)):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i][j]+1
    else:
      dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
len_=dp[len(s)][len(t)]
s_now=len(s)
t_now=len(t)
ans=''
if len_==0:
  print(ans)
  exit()
while len_>0:
  if s[s_now-1]==t[t_now-1]:
    ans=ans+s[s_now-1]
    len_+=-1
    s_now+=-1
    t_now+=-1
    
  else:
    if dp[s_now][t_now]==dp[s_now][t_now-1]:
      t_now=t_now-1
    elif dp[s_now][t_now]==dp[s_now-1][t_now]:
      s_now=s_now-1
ans=ans[::-1]
print(ans)



### FIXED CODE ###

s=input()
t=input()
dp=[[0]*(len(t)+1) for _ in range(len(s)+1)]
for i in range(len(s)):
  for j in range(len(t)):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i][j]+1
    else:
      dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
len_=dp[len(s)][len(t)]
s_now=len(s)
t_now=len(t)
ans=''
if len_==0:
  print(ans)
  exit()
while len_>0:
  if s[s_now-1]==t[t_now-1]:
    ans=ans+s[s_now-1]
    len_+=-1
    s_now+=-1
    t_now+=-1
    
  else:
    if dp[s_now][t_now]==dp[s_now][t_now-1]:
      t_now=t_now-1
    elif dp[s_now][t_now]==dp[s_now-1][t_now]:
      s_now=s_now-1
ans=ans[::-1]
print(ans)
### BUGGY CODE ###

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

print(sum(list(filter(lambda x: x<P[i], set(P[:i+1])))==[] for i in range(N)))

### FIXED CODE ###

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

mi=P[0]
cnt=0
for i in range(N):
    if P[i]<mi:mi=P[i]
    if P[i]<=mi:cnt+=1
       
print(cnt)
### BUGGY CODE ###

def max_heapify(a, i):
    h = len(a)
    l = 2 * i + 1
    r = 2 * i + 2
    if l < h and a[l] > a[i]:
        largest = l
    else:
        largest = i
    if r < h and a[r] > a[largest]:
        largest = r

    if largest != i:
        tmp = a[i]
        a[i] = a[largest]
        a[largest] = tmp
        max_heapify(a, largest)


def build_max_heap(a):
    h = len(a)
    for i in range(h // 2 - 1, -1, -1):
        max_heapify(a, i)


def extract_max(a):
    max = a[0]
    a[0] = a[-1]
    a.pop()
    build_max_heap(a)
    return max


heap = []
ans = []
while True:
    s = input().split()
    if s[0] == "end":
        break
    elif s[0] == "extract":
        ans.append(extract_max(heap))
    elif s[0] == "insert":
        heap.append(int(s[1]))
        build_max_heap(heap)

for x in ans:
    print(x)


### FIXED CODE ###

import sys


def extract_max(A):
    x = A[0]
    A[0] = A[-1]
    A.pop()
    H = len(A)
    i = 0
    while i < H:
        v = A[i]
        rv = 0
        lv = 0
        r = (i + 1) * 2
        l = r - 1
        if l < H:
            lv = A[l]
            if r < H:
                rv = A[r]

        if v < lv and lv > rv:
            A[l] = v
            A[i] = lv
            i = l
        elif v < rv:
            A[r] = v
            A[i] = rv
            i = r
        else:
            break
    return x


def insert(a, n):
    i = len(a)
    a.append(n)
    while i > 0:
        p = int((i + 1) / 2) - 1
        v = a[i]
        pv = a[p]
        if pv < v:
            a[p] = v
            a[i] = pv
            i = p
        else:
            break


def main():
    istr = sys.stdin.read()
    cmds = list(istr.splitlines())
    S = []
    for cmd in cmds:  # input()
        if cmd[0] == "i":
            insert(S, int(cmd[7:]))

        elif cmd == "extract":
            a = extract_max(S)
            print(a)

        elif cmd == "end":
            break


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

from functools import lru_cache

MOD = 998244353

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0

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

n = 2 * min(K // A + 2, N + 1) + 3

lst = Factorial(N + 1, MOD) #O(N)
N_factrorial = lst.factorial(N)
l_ifactorial = lst.ifactorial
# print (N_factrorial)


@lru_cache(maxsize = None)
def calc(a, b):
    tmp = 0
    G = min(a, b) #緑色の最大値
    # print ('G=', G)
    for green in range(G, -1, -1):
        red = a - green
        blue = b - green
        none_color = N - red - green - blue
        # print (red, green, blue, none_color)
        if none_color < 0:
            break
        tmp += ((((N_factrorial * l_ifactorial(red) % MOD) * l_ifactorial(green) % MOD) * l_ifactorial(blue) % MOD) * l_ifactorial(none_color) % MOD)
        tmp %= MOD
    return tmp

def count(a, b):
    if a + b > 2 * N:
        return 0
    # print ('to calc')
    return calc(a, b)

ans = 0
for a in range(n): #Aの数
    if A * a > K:
        break
    if (K - A * a) % B != 0:
        continue
    b = (K - A * a) // B
    # print ('a=', a, 'b=', b)
    ans += count(a, b)
    ans %= MOD

print (ans)

### FIXED CODE ###

import numpy as np
MOD = 998244353

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0

def gcd(a, b):
    if a > b:
        a, b = b, a
    if b % a == 0:
        return a
    return gcd(b % a, a)

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

if A < B:
    A, B = B, A

# n = 2 * min(K // A + 2, N + 1) + 3
n = min((K + A - 1) // A, N) + 1
lcm = A * B // gcd(A, B)
step = lcm // A

c = Factorial(N + 1, MOD).comb #O(N)

def calc(a, b):
    if a > b:
        a, b = b, a #必ずaのほうが小さくなる
    return (c(N, a) * c(N, b)) % MOD


def count(a, b):
    if a <= N and b <= N:
        return calc(a, b)
    return 0

def maike_satrt(step):
    for i in range(step):
        if (K - A * i) % B == 0:
            return i

start = maike_satrt(step)
# print (start, n)
ans = 0
for a in range(start, n, step): #Aの数
    if A * a > K:
        break
    # if (K - A * a) % B != 0:
    #     continue
    b = (K - A * a) // B
    # print ('a=', a, 'b=', b)
    ans += count(a, b)
    ans %= MOD

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

n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())

g = [[] for _ in range(3 * n)]

for u, v in uv:
    a = u - 1
    b = v - 1
    g[a].append(n + b)
    g[n+a].append(n*2 + b)
    g[n*2+a].append(b)

#print(g)

s -= 1
t -= 1
ans = 0
temp = [s]
while 1:
    ans += 1
    next = []
    for x in temp:
        next = next + g[x]
        g[x] = []
    if len(next) == 0:
        print(-1)
        exit()
    if t in next:
        print(ans // 3)
        exit()
    temp = [] + list(set(next))


### FIXED CODE ###

n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())

g = [set() for _ in range(3 * n)]

for u, v in uv:
    a = u - 1
    b = v - 1
    g[a].add(n + b)
    g[n+a].add(n*2 + b)
    g[n*2+a].add(b)

#print(g)

s -= 1
t -= 1
ans = 0
temp = set()
temp.add(s)
while 1:
    ans += 1
    next = set()
    for x in temp:
        for y in g[x]:
            next.add(y)
        g[x] = []
    if len(next) == 0:
        print(-1)
        exit()
    if t in next:
        print(ans // 3)
        exit()
    temp = next
### BUGGY CODE ###

N,W = map(int,input().split())
wv = []
for i in range(N):
    a = list(map(int,input().split()))
    wv.append(a)
sumv = sum([i[1] for i in wv])

dp = [[float('inf') for i in range(sumv+1)] for j in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0
for i in range(N):
    for j in range(sumv+1):
        if j - wv[i][1] >=0 :
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]] + wv[i][0])
        else:
            dp[i+1][j] = dp[i][j]

for i in range(sumv,-1,-1):
    if dp[-1][i] <= W:
        print(i)
        break



### FIXED CODE ###

N,W = map(int,input().split())
wv = []
for i in range(N):
    a = list(map(int,input().split()))
    wv.append(a)
sumv = sum([i[1] for i in wv])
dp = [[10**10 for i in range(sumv+1)] for j in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0
for i in range(N):
    for j in range(sumv+1):
        if j - wv[i][1] >=0 :
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]] + wv[i][0])
        else:
            dp[i+1][j] = dp[i][j]

for i in range(sumv,-1,-1):
    if dp[-1][i] <= W:
        print(i)
        break
### BUGGY CODE ###

import sys
 
def input():
    return sys.stdin.readline().strip()
 
n = int(input())
A = list(map(int, input().split()))
sum = 1
for i in range(n):
    sum *= A[i]
if(sum > 10**18):
    sum = -1
print(sum)


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline().strip()

def main():
    n = int(input())
    A = list(map(int, input().split()))
    if 0 in A:
        print(0)
        return
    x = 1
    for i in A:
        x *= i
        if x > pow(10,18):
            print(-1)
            return
    print(x)

main()
### BUGGY CODE ###

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

### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for x in range(k+1):
  for y in range(k+1):
    if x+y<=s and s-x-y<=k:
      count+=1
print(count)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.readline()[:-1]

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

queries = [0 for _ in range(n)]
for _ in range(q):
	p, x = map(int, input().split())
	queries[p-1] += x

ans = [0 for _ in range(n)]

def dfs(x, c, p):
	#print(x)
	ans[x] = c + queries[x]
	for v in adj[x]:
		if v != p:
			dfs(v, ans[x], x)
	return

dfs(0, 0, -1)

print(*ans)

### FIXED CODE ###

import sys
#sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.readline()[:-1]

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

queries = [0 for _ in range(n)]
for _ in range(q):
	p, x = map(int, input().split())
	queries[p-1] += x

ans = [0 for _ in range(n)]

st = [(0, 0, -1)]
while st:
	l = st.pop()
	ans[l[0]] = l[1] + queries[l[0]]
	for v in adj[l[0]]:
		if v != l[2]:
			st.append((v, ans[l[0]], l[0]))

print(*ans)