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

N,M=map(int,input().split())
P_list=[int(p) for p in input().split()]
Tree=[-1]*N
def find(x):
  while Tree[x]>=0:
    x=Tree[x]
  return x
def unite(x,y):
  s1=find(x)
  s2=find(y)
  if s1==s2:
    pass
  else:
    if Tree[s1]<Tree[s2]:
      Tree[s2]=s1
    elif Tree[s2]>Tree[s1]:
      Tree[s1]=s2
    else:
      Tree[s1]+=-1
      Tree[s2]=s1
  return
for m in range(M):
  x,y=map(int,input().split())
  unite(x-1,y-1)
ans=0
for i in range(N):
  if find(P_list[i]-1)==find(i):
    ans+=1
print(ans)
    
  

### FIXED CODE ###

N,M=map(int,input().split())
P_list=[int(p) for p in input().split()]
Tree=[i for i in range(N)]
def find(x):
  if x==Tree[x]:
    return x
  else:
    root=find(Tree[x])
    Tree[x]=root
    return root
def unite(x,y):
  s1=find(x)
  s2=find(y)
  if s1==s2:
    pass
  else:
    Tree[s1]=s2
for m in range(M):
  x,y=map(int,input().split())
  unite(x-1,y-1)
ans=0
for i in range(N):
  if find(P_list[i]-1)==find(i):
    ans+=1
print(ans)
### BUGGY CODE ###

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

MOD = 998244353 # prime
fact_inv, inv = [0]*10**6, [0]*10**6

def init_nCk():
    fact_inv[0] = fact_inv[1] = 1
    inv[1] = 1
    for i in range(2,10**6):
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        fact_inv[i] = fact_inv[i-1] * inv[i] % MOD

def nCk(n,k):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    ans = 1
    for i in range(n, n-k+1 - 1, -1):
        ans *= i
        ans %= MOD
    return ans * fact_inv[k] % MOD

# WAKARAN
res = 0
init_nCk()
for a in range(0,N+1):
    # 割り切れることを確認
    if (K - A*a)%B == 0 and (K -A*a)//B >= 0:
        b = (K -A*a)//B
        res += nCk(N,a)*nCk(N,b)
        res %= MOD
print(res)

### FIXED CODE ###

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

MOD = 998244353 # prime
MAX = 10**6

fac = [0]*MAX
finv = [0]*MAX
inv = [0]*MAX

def init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2,MAX):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i-1] * inv[i] % MOD

def C(n, k):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    return fac[n]%MOD * (finv[k] * finv[n-k] % MOD) % MOD

res = 0
init()
for a in range(0,N+1):
    # 割り切れることを確認
    if (K - A*a)%B == 0 and (K -A*a)//B >= 0:
        b = (K -A*a)//B
        res += C(N,a)*C(N,b)
        res %= MOD
print(res)
### BUGGY CODE ###

class SegmentTree:
    def __init__(self,n):
        self.siz = 1
        while self.siz < n: self.siz *= 2
        self.node = [0]*(2*self.siz-1)

    def update(self,i,x):
        i += self.siz-1
        self.node[i] = x
        while i > 0:
            i = (i-1)//2
            self.node[i] = self.node[i*2+1] | self.node[i*2+2]
    
    def query(self,a,b,k=0,l=0,r=-1):
        if r < 0: r = self.siz
        if r <= a or b <= l: return 0
        if a <= l and r <= b: return self.node[k]
        vl = self.query(a,b,k*2+1,l,(l+r)//2)
        vr = self.query(a,b,k*2+2,(l+r)//2,r)
        return vl | vr
    
n = int(input())
st = SegmentTree(n)
s = list(input())
def f(c): return 1<<(ord(c) - ord("a"))
for i in range(n): st.update(i,f(s[i]))
q = int(input())
for _ in range(q):
    typ,x,y = input().split()
    if typ == "1":
        i,c = int(x)-1,y
        if s[i] == c: continue
        st.update(i,f(c))
        s[i] = c
    else:
        l,r = int(x)-1,int(y)
        print(bin(st.query(l,r)).count("1"))

### FIXED CODE ###

class SegmentTree:
    def __init__(self,n):
        self.siz = 1
        while self.siz < n: self.siz *= 2
        self.node = [0]*(2*self.siz-1)

    def update(self,i,x):
        i += self.siz-1
        self.node[i] = x
        while i > 0:
            i = (i-1)//2
            self.node[i] = self.node[i*2+1] | self.node[i*2+2]
    
    def query(self,a,b,k=0,l=0,r=-1):
        if r < 0: r = self.siz
        if r <= a or b <= l: return 0
        if a <= l and r <= b: return self.node[k]
        vl = self.query(a,b,k*2+1,l,(l+r)//2)
        vr = self.query(a,b,k*2+2,(l+r)//2,r)
        return vl | vr
    
n = int(input())
st = SegmentTree(n)
s = list(input())
def f(c): return 1<<(ord(c) - ord("a"))
for i in range(n): st.update(i,f(s[i]))
q = int(input())
for _ in range(q):
    typ,x,y = input().split()
    if typ == "1":
        i,c = int(x)-1,y
        if s[i] == c: continue
        st.update(i,f(c))
        s[i] = c
    else:
        l,r = int(x)-1,int(y)
        print(bin(st.query(l,r)).count("1"))
### BUGGY CODE ###

n = int(input())
uvw = [list(map(int, input().split())) for _ in range(n - 1)]
ans = [-1] * (n + 1)
ans[1] = True
while uvw:
    nuvw = []
    for u, v, w in uvw:
        if ans[u] != -1:
            if w % 2:
                ans[v] = not ans[u]
            else:
                ans[v] = ans[u]
        elif ans[v] != -1:
            if w % 2:
                ans[u] = not ans[v]
            else:
                ans[u] = ans[v]
        else:
            nuvw.append([u, v, w])
    uvw = nuvw
for x in ans[1:]:
    print(x * 1)


### FIXED CODE ###

n = int(input())
pea = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    w %= 2
    pea[u].append([v, w])
    pea[v].append([u, w])
ans = [-1] * (n + 1)
ans[1]=1
nodes=[1]
used=set()
used.add(1)
ansi=1
while nodes:
    nn=[]
    for i in nodes:
        ansi=ans[i]
        for u,w in pea[i]:
            if u in used:continue
            ans[u]=(ansi+w)%2
            used.add(u)
            nn+=[u]
    nodes=nn
for x in ans[1:]:
    print(x)
### BUGGY CODE ###

import sys
import collections
tmp=sys.stdin.readline().rstrip()
def main():
   ans=0
   cnt=[0]*2019
   cnt[0]+=1
   d=0
   for i,j in enumerate(reversed(tmp)):
      d+=int(j)*10**(i)
      cnt[d%2019]+=1
   cnt=collections.Counter(cnt).items()
   for i,j in cnt:
      if i > 1:
         ans+=i*(i-1)//2*j
   print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
tmp=sys.stdin.readline().rstrip()
def main():
   ans=0
   cnt=[0]*2019
   cnt[0]+=1
   t=0
   d=1
   for i in reversed(tmp):
      t=(t+int(i)*d)%2019
      cnt[t]+=1
      d=d*10%2019
   for i in cnt:
      ans+=i*(i-1)//2
   print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys

n, *inp = map(int, sys.stdin.buffer.read().split())
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]

weight_limit = 10 ** 5
precalc_limit = min(1 << 11, n + 1)
precalc = [[0] * (weight_limit + 1)]

for u in range(1, precalc_limit):
    v = vvv[u]
    w = www[u]
    dp = precalc[u >> 1][:]
    for x in range(weight_limit, w - 1, -1):
        nv = dp[x - w] + v
        if dp[x] < nv:
            dp[x] = nv
    precalc.append(dp)

buf = []
mp = iter(inp[n * 2 + 1:])
for u, l in zip(mp, mp):
    if u < precalc_limit:
        buf.append(precalc[u][l])
        continue
    dp_w = [0]
    dp_v = [0]
    while u >= precalc_limit:
        v = vvv[u]
        w = www[u]
        for i in range(len(dp_w)):
            nw = dp_w[i] + w
            if nw > l:
                continue
            nv = dp_v[i] + v
            dp_w.append(nw)
            dp_v.append(nv)
        u >>= 1
    ans = 0
    for w, v in zip(dp_w, dp_v):
        nv = v + precalc[u][l - w]
        if ans < nv:
            ans = nv
    buf.append(ans)

print('\n'.join(map(str, buf)))


### FIXED CODE ###

import sys

n, *inp = map(int, sys.stdin.buffer.read().split())
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]

weight_limit = 10 ** 5
precalc_limit = min(1 << 10, n + 1)
precalc = [[0] * (weight_limit + 1)]

for u in range(1, precalc_limit):
    v = vvv[u]
    w = www[u]
    dp = precalc[u >> 1][:]
    for x in range(weight_limit, w - 1, -1):
        nv = dp[x - w] + v
        if dp[x] < nv:
            dp[x] = nv
    precalc.append(dp)

buf = []
mp = iter(inp[n * 2 + 1:])
for u, l in zip(mp, mp):
    if u < precalc_limit:
        buf.append(precalc[u][l])
        continue
    dp_w = [0]
    dp_v = [0]
    while u >= precalc_limit:
        v = vvv[u]
        w = www[u]
        for i in range(len(dp_w)):
            nw = dp_w[i] + w
            if nw > l:
                continue
            nv = dp_v[i] + v
            dp_w.append(nw)
            dp_v.append(nv)
        u >>= 1
    ans = 0
    for w, v in zip(dp_w, dp_v):
        nv = v + precalc[u][l - w]
        if ans < nv:
            ans = nv
    buf.append(ans)

print('\n'.join(map(str, buf)))
### BUGGY CODE ###

N, K = map(int, input().split())
mod = 10 ** 9 + 7

dp = [[[[0 for _ in range(K + 1)] for _ in range(2)] for _ in range(K + 1)] for _ in range(N - K + 1)]
for r in range(N - K + 1):
    for b in range(K + 1):
        for i in range(b + 1):
            if b == 0 and i == 0:
                dp[r][b][0][i] = 1
                dp[r][b][1][i] = 1
            if r > 0:
                dp[r][b][0][i] = (dp[r-1][b][0][i] + dp[r-1][b][1][i]) % mod
            if b > 0 and i > 0:
                dp[r][b][1][i] = (dp[r][b-1][0][i-1] + dp[r][b-1][1][i]) % mod

for i in range(1, K+1):
    print(dp[N-K][K][1][i])


### FIXED CODE ###

N, K = map(int, input().split())
mod = 10 ** 9 + 7

from math import factorial

# comb init
nmax = 2000 + 1  # change here
fac = [0] * (nmax + 1)
finv = [0] * (nmax + 1)
inv = [0] * (nmax + 1)
fac[0] = 1
fac[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
for i in range(2, nmax):
    fac[i] = fac[i - 1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i - 1] * inv[i] % mod


def comb(n, r):
    if n < r:
        return 0
    else:
        return (fac[n] * ((finv[r] * finv[n - r]) % mod)) % mod


r = N - K
for b in range(1, K+1):
    print((comb(r+1, b) * comb(K - 1, b - 1)) % mod)
### BUGGY CODE ###

N, M = map(int,input().split())
ships = []
for m in range(M):
    ships.append(list(map(int,input().split())))

flag = 0
for n in range(2,N+1):
    if [1,n] in ships and [n,N] in ships:
        print("POSSIBLE")
        flag=1
        break

if flag==0:
    print("IMPOSSIBLE")


### FIXED CODE ###

N, M = map(int,input().split())
ships_1 = []
ships_2 = []
for m in range(M):
    tmp = list(map(int,input().split()))
    if tmp[0]==1:
        ships_1.append(tmp[1])
    elif tmp[1] == N:
        ships_2.append(tmp[0])

matched_list = list(set(ships_1) & set(ships_2))
if matched_list:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

import heapq

# dijkstra shortest path solver
def shortest_path(G, s, t):
    fixed = {}
    q = list()
    heapq.heappush(q, (0, s))

    while q:
        w,x = heapq.heappop(q)
        if x == t: return w
        if x in fixed: continue;
        fixed[x] = w

        for y in G[x]:
            if (y in fixed) == False:
                heapq.heappush(q, (w + G[x][y] , y))
    return None

def memo(G, n, s):
    cost = list()
    for i in range(n):
        cost.append(shortest_path(G, s, i))
    return cost

if __name__ == '__main__':
    money = 10**15

    # read inputs
    n, m, s, t = list(map(int,input().split()))
    # zero origin
    S = s-1
    T = t-1

    # create empty graph
    G = [{} for i in range(n)] # JPY
    H = [{} for i in range(n)] # SNK

    # set virtex with weight
    for i in range(m):
        u, v, p, q = list(map(int, input().split()))
        u -= 1
        v -= 1
        G[u][v] = p
        G[v][u] = p
        H[u][v] = q
        H[v][u] = q

    min_jpy = memo(G, n, S)
    min_snk = memo(H, n, T)
    for year in range(n):
        cost = None
        for i in range(year, n):
            t = min_jpy[i] + min_snk[i]
            if cost is None:
                cost = t
            else:
                if cost > t:
                    cost = t

        print(money - cost)


### FIXED CODE ###

import heapq
from itertools import accumulate

# dijkstra shortest path solver
def min_cost(G, s, n):
    inf = float("inf")
    cost = [inf for _ in range(n)]
    cost[s] = 0
    q = list()
    heapq.heappush(q, (0, s))

    while (len(q) != 0):
    #while q:
        w,index = heapq.heappop(q)
        if cost[index] < w:
            continue
        for j in G[index]:
            c = cost[index] + G[index][j]
            if c < cost[j]:
                cost[j] = c
                heapq.heappush(q, (c, j))
    return cost

if __name__ == '__main__':
    money = 10**15

    # read inputs
    n, m, s, t = list(map(int,input().split()))
    # zero origin
    S = s-1
    T = t-1

    # create empty graph
    G = [{} for _ in range(n)] # JPY
    H = [{} for _ in range(n)] # SNK

    # set virtex with weight
    for i in range(m):
        u, v, p, q = list(map(int, input().split()))
        u -= 1
        v -= 1
        G[u][v] = p
        G[v][u] = p
        H[u][v] = q
        H[v][u] = q

    min_jpy = min_cost(G, S, n)
    min_snk = min_cost(H, T, n)
    total = [x+y for (x, y) in zip(min_jpy, min_snk)]
    # pre calc minimum cost for all year
    fl = list(accumulate(total[::-1], min))[::-1]

    for year in range(n):
        print(money - fl[year])
### BUGGY CODE ###

number_of_sticks = int(input())

sticks = [int(x) for x in input().split(' ')]

sticks.sort()

# print(sticks)

triangles = 0

import bisect

for i in range (number_of_sticks - 2):
    for j in range (i+2, number_of_sticks):
        # print(sticks[i], sticks[j])
        # find number of sticks between range range sticks[j]-sticks[i], sticks[i] + sticks[j]
        # max_range = bisect.bisect_left(sticks, sticks[i] + sticks[j]) - 1
        max_range = j
        min_range = max(bisect.bisect(sticks, sticks[j] - sticks[i]), i + 1)
        # print("max range: " + str(max_range))
        # print("min range: " + str(min_range))
        triangles += max(0, max_range - min_range)

print(triangles)

### FIXED CODE ###

number_of_sticks = int(input())

sticks = [int(x) for x in input().split(' ')]

sticks.sort()

triangles = 0

import bisect

for i in range (number_of_sticks - 2):
    for j in range (i+2, number_of_sticks):
        max_range = j
        min_range = max(bisect.bisect(sticks, sticks[j] - sticks[i]), i + 1)
        triangles += max_range - min_range

print(triangles)
### BUGGY CODE ###

import math
from collections import deque
N, K = map(int, input().split())
A = list(map(int, input().split()))
S =sum(A)
cut = []
for k in range(N):
  cut.append(K*A[k]//S)

length = []
for k in range(N):
  length.append([A[k] / (cut[k]+1), k])

length.sort(key = lambda x: x[0], reverse=True)

def nibun_insert(lis, item):
  end = len(lis)
  start = 0
  now = (end+start)//2
  while end > start+1:
    if lis[now][0] > item[0]:
      start = 0 + now
      now = (now + end)//2
    else:
      end = 0 + now
      now = (now + start)//2
  return deque(lis[:now+1] + [item] + lis[now+1:])
  

C = sum(cut)
res = min(K - C, N)
length = length[:res+1]
length = deque(length)
for k in range(res):
  a = length.popleft()
  cut[a[1]] += 1
  a[0] = a[0]*cut[a[1]]/(cut[a[1]]+1)
  length = nibun_insert(list(length), list(a))
  length.pop()

print(math.ceil(length.popleft()[0]))

### FIXED CODE ###

import math
from collections import deque
N, K = map(int, input().split())
A = list(map(int, input().split()))
S =sum(A)
cut = []
for k in range(N):
  cut.append(K*A[k]//S)

length = []
for k in range(N):
  length.append([A[k] / (cut[k]+1), k])

length.sort(key = lambda x: x[0], reverse=True)

def nibun_insert(lis, item):
  end = len(lis)
  start = 0
  now = (end+start)//2
  while end > start+1:
    if lis[now][0] > item[0]:
      start = 0 + now
      now = (now + end)//2
    else:
      end = 0 + now
      now = (now + start)//2
  return deque(lis[:now+1] + [item] + lis[now+1:])
  

C = sum(cut)
res = min(K - C, N)
length = length[:res+1]
length = deque(length)
for k in range(res):
  a = length.popleft()
  cut[a[1]] += 1
  a[0] = a[0]*cut[a[1]]/(cut[a[1]]+1)
  if a[0] <= length[-1][0]:
    length.append(a)
  elif a[0] >= length[0][0]:
    length.appendleft(a)
  else:
    length = nibun_insert(list(length), list(a))
  length.pop()

print(math.ceil(length.popleft()[0]))
### BUGGY CODE ###

n = int(input())
a = [0]*(10**5)
for i in range(1,1000):
    for j in range(1,1000):
        for  k in range(1,101):
            try:
                a[i*i+j*j+k*k+i*j+j*k+i*k]+=1
            except:
                continue
for i in range(1, n+1):
    print(a[i])

### FIXED CODE ###

n = int(input())
a = [0]*((10**4)+1)
for i in range(1,101):
    for j in range(1,101):
        for  k in range(1,101):
            try:
                a[i*i+j*j+k*k+i*j+j*k+i*k]+=1
            except:
                continue
for i in range(1, n+1):
    print(a[i])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left, bisect_right
from copy import copy, deepcopy
N = int(input())
A = list(map(int, input().split()))
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v,LIS):
    if len(edge[v])==0:
        return
    for u in edge[v]:
        if visited[u]==False:
            visited[u]=True
            ind = bisect_left(LIS,A[u])
            lis = copy(LIS)
            if ind < len(lis):
                lis[ind] = A[u]
            else:
                lis.append(A[u])
            ans[u] = len(lis)
            dfs(u,lis)
    return

ans = [0]*N
visited = [False]*N
visited[0]=True
LIS = [A[0]]
ans[0] = 1
dfs(0,LIS)
print(*ans, sep='\n')


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left, bisect_right
N = int(input())
A = list(map(int, input().split()))
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v,LIS):
    if len(edge[v])==0:
        return
    for u in edge[v]:
        if visited[u]==False:
            visited[u]=True
            if A[u] > LIS[-1]:
                LIS.append(A[u])
                ans[u] = len(LIS)
                dfs(u,LIS)
                LIS.pop()
            else:
                ind = bisect_left(LIS,A[u])
                stack = LIS[ind]
                LIS[ind] = A[u]
                ans[u] = len(LIS)
                dfs(u,LIS)
                LIS[ind] = stack
    return

ans = [0]*N
visited = [False]*N
visited[0]=True
LIS = [A[0]]
ans[0] = 1
dfs(0,LIS)
print(*ans, sep='\n')
### BUGGY CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**6+10
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
    
r,c,R,C=map(int,input().split())
ans=0
for i in range(C-c):
  ans=ans+cmb(r+c+1+i,r,mod)*cmb(R-r+C-c-i,R-r,mod)
ans=ans+cmb(r+c,r,mod)
for i in range(R-r):
  ans=ans+cmb(c+r+1+i,c,mod)*cmb(C-c+R-r-i,C-c,mod)
print(ans%mod)

### FIXED CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
    
r,c,R,C=map(int,input().split())
ans=0
for i in range(C-c):
  ans=ans+cmb(r+c+1+i,r,mod)*cmb(R-r+C-c-i,R-r,mod)
ans=ans+cmb(r+c,r,mod)
for i in range(R-r):
  ans=ans+cmb(c+r+1+i,c,mod)*cmb(C-c+R-r-i,C-c,mod)
print(ans%mod)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(int(i) for i in input().split())

gokei = 0

for i in range(n-k+1):
    kitaiwa = (sum(p[i:i+k])+k)/2
    if gokei < kitaiwa:
        gokei = kitaiwa

print(gokei)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(int(i) for i in input().split())

kitai = [(x+1)/2 for x in p]

rui_kitai = [kitai[0]]

for i in range(1, n):
    ruiseki=rui_kitai[i-1]+kitai[i]
    rui_kitai.append(ruiseki)

gokei = 0

for i in range(n-k+1):
    if i==0:
        wa = rui_kitai[k-1]
    else:
        wa = rui_kitai[i+k-1]-rui_kitai[i-1]
    if gokei < wa:
        gokei = wa

print(gokei)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
UV = [[] for _ in range(n)]
for _ in range(m):
    u, v = list(map(lambda x: int(x)-1, input().split()))
    UV[u].append(v)
s, t = list(map(lambda x: int(x)-1, input().split()))

edges = [[]for _ in range(n)]

for v in range(n):
    for v2 in UV[v]:
        for v3 in UV[v2]:
            for v4 in UV[v3]:
                edges[v].append(v4)

INF = 10**18
dist = [INF]*n
dist[s] = 0
next_v = deque([s])
while next_v:
    v = next_v.popleft()
    for v2 in edges[v]:
        if dist[v2] <= dist[v]+1:
            continue
        dist[v2] = dist[v]+1
        next_v.append(v2)
print(dist[t]if dist[t] != INF else -1)


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
UV = [[]for _ in range(n)]
for _ in range(m):
    u, v = list(map(lambda x: int(x)-1, input().split()))
    UV[u].append(v)
s, t = list(map(lambda x: int(x)-1, input().split()))

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


def to_v(i, j):
    return 3*i+j


for i in range(n):
    for i2 in UV[i]:
        for j in range(3):
            edges[to_v(i, j)].append(to_v(i2, (j+1) % 3))

init_v = to_v(s, 0)
INF = 10**18
dist = [INF]*NV
dist[init_v] = 0
next_v = deque([init_v])
while next_v:
    v = next_v.popleft()
    for v2 in edges[v]:
        if dist[v2] <= dist[v]+1:
            continue
        dist[v2] = dist[v]+1
        next_v.append(v2)

print(dist[to_v(t, 0)]//3 if dist[to_v(t, 0)] != INF else -1)
### BUGGY CODE ###

s= input()
q= int(input())
for i in range(q):
    p = input()
    if p[0]=='1':s = s[::-1]
    elif p[0]=='2':
        _,f,c= p.split()
        if f=='1':s = c + s
        elif f=='2':s = s + c
print(s)


### FIXED CODE ###

from collections import deque
s= input()
q= int(input())
inv = False
head = deque()
tail = deque()
for i in range(q):
    p = input()
    if p[0]=='1':
        if inv:inv=False
        else:inv=True
    elif p[0]=='2':
        _,f,c= p.split()
        if f=='1':
            if inv:tail.append(c)
            else:head.appendleft(c)
        elif f=='2':
            if inv:head.appendleft(c)
            else:tail.append(c)
news = ''.join(head) + s + ''.join(tail)
if inv:print(news[::-1])
else:print(news)
### BUGGY CODE ###

N, Y = list(map(int, input().split()))
flag=0
try:
  for x in range(N+1):
    #if flag != 0:break
    for y in range(N+1-x):
      #if flag != 0:break
      for z in range(N+1-x-y):
        if x+y+z == N:
          if x*10000 + y*5000 + z*1000 == Y:
            print(x, y, z)
            flag = 1
            raise Exception
except Exception:
  pass
if flag == 0:
  print('-1 -1 -1')


### FIXED CODE ###

N, Y = list(map(int, input().split()))
flag=0
try:
  for x in range(N+1):
    for y in range(N+1-x):
      z = N - x- y
      if x*10000 + y*5000 + z*1000 == Y:
        print(x, y, z)
        flag = 1
        raise Exception
except Exception:
  pass
if flag == 0:
  print('-1 -1 -1')
### BUGGY CODE ###

N = int(input())
A = input().split()

a=int(A[0])
for i in range(N-1):
  a=a*int(A[i+1])
  
if a>10**18:
  print(-1)
else:
  print(a)

### FIXED CODE ###

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

if 0 in A:
  print(0)
else:
  result=1
  for i in A:
    result*=i
    if result>10**18:
      result=-1
      break
  print(result)