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

import sys,collections
input = sys.stdin.readline

def main():
    N,M,K = list(map(int,input().split()))
    fr = [[] for i in range(N+1)]
    bl = [[] for i in range(N+1)] 
          
    for _ in range(M):
        a,b = map(int,input().split())
        fr[a].append(b)
        fr[b].append(a)
    for _ in range(K):
        c,d = map(int,input().split())
        bl[c].append(d)
        bl[d].append(c)

    fl = [-1 for i in range(N+1)]
    fl[0] = 0
    fl[1] = 1
    nxt = 1
    dic = {}
    while nxt != 0:
        q = collections.deque([nxt])
        
        fl[nxt]=nxt
        cnt = 0
        while q:
            now = q.popleft()
            for f in fr[now]:
                if fl[f] == -1:
                    fl[f] = nxt
                    cnt +=1
                    q.append(f)
        dic[nxt] = cnt
        try:
            nxt = fl.index(-1)
        except:
            nxt = 0

    mbf = collections.deque()
    for i in range(1,N+1):
        ff = 0
        for j in bl[i]:
            if fl[j] == fl[i]:
                ff -= 1
        
        ff += dic[fl[i]]-len(fr[i])
        mbf.append(ff)
    print(*mbf)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys,collections
input = sys.stdin.readline

def main():
    N,M,K = list(map(int,input().split()))
    fr = [[] for i in range(N+1)]
    bl = [[] for i in range(N+1)]

          
    for _ in range(M):
        a,b = map(int,input().split())
        fr[a].append(b)
        fr[b].append(a)
    for _ in range(K):
        c,d = map(int,input().split())
        bl[c].append(d)
        bl[d].append(c)

    fl = [-1 for i in range(N+1)]
    fl[0] = 0
    fl[1] = 1
    nxt = 1
    dic = {}
    s = set(range(1,N+1))
    while nxt != 0:
        q = collections.deque([nxt])
        
        fl[nxt]=nxt
        cnt = 0
        while q:
            now = q.popleft()
            s.discard(now)
            for f in fr[now]:
                if fl[f] == -1:
                    fl[f] = nxt
                    cnt +=1
                    q.append(f)
        dic[nxt] = cnt
        #try:
            #nxt = fl.index(-1)
        #except:
            #nxt = 0
        if len(s) == 0:
            nxt = 0
        else:
            nxt = s.pop()


    mbf = collections.deque()
    for i in range(1,N+1):
        ff = 0
        for j in bl[i]:
            if fl[j] == fl[i]:
                ff -= 1
        
        ff += dic[fl[i]]-len(fr[i])
        mbf.append(ff)
    print(*mbf)

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

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
mod = 10 ** 9 + 7

a_list.sort(reverse=True)
b_list.sort(reverse=True)
a_list.append(-1)
b_list.append(-1)
ans = 1
a_i = 0
b_i = 0
for i in range(N*M, 0, -1):
    if i == a_list[a_i] and i == b_list[b_i]:
        a_i += 1
        b_i += 1
    elif i == a_list[a_i]:
        a_i += 1
        ans *= b_i % mod
    elif i == b_list[b_i]:
        b_i += 1
        ans *= a_i % mod
    else:
        ans *= (a_i*b_i - (N * M - i)) % mod
print(ans % mod)



### FIXED CODE ###

N, M = map(int, input().split())
a_list = tuple(map(int, input().split()))
b_list = tuple(map(int, input().split()))
mod = 10 ** 9 + 7

a_list = sorted(a_list, reverse=True)
b_list = sorted(b_list, reverse=True)
a_list.append(-1)
b_list.append(-1)
ans = 1
a_i = 0
b_i = 0
for i in range(N*M, 0, -1):
    if i == a_list[a_i] and i == b_list[b_i]:
        a_i += 1
        b_i += 1
    elif i == a_list[a_i]:
        a_i += 1
        ans *= b_i
        ans %= mod
    elif i == b_list[b_i]:
        b_i += 1
        ans *= a_i
        ans %= mod
    else:
        ans *= (a_i*b_i - (N * M - i))
        ans %= mod
print(ans % mod)
### BUGGY CODE ###

A,B,K = map(int,input().split())
L = []

for n in range(A,B+1):
  L.append(n)
  
ans = sorted(set(L[:K]+L[-K:]))
  
print(*ans,sep="\n")

### FIXED CODE ###

A,B,K = map(int,input().split())
L = []
M = []

for n in range(A,min(A+K,B+1)):
  L.append(n)
  
for n in range(max(A,B-K),B+1):
  M.append(n)
  
L = sorted(set(L[:K]+M[-K:]))
  
print(*L,sep="\n")
### BUGGY CODE ###

import math
N = int(input())

Psama = []

for i in range (0, N):
	Psama.append("". join(sorted(input())))

Achamo = list(set(Psama))

Wakashamo = [0]*len(Achamo)

for i in range (0, len(Psama)):
	for j in range (0, len(Achamo)):
		if Psama[i] == Achamo[j]:
			Wakashamo[j]+=1

counter =0

for i in range (0, len(Achamo)):
	if Wakashamo[i]!=1:
		counter+=math.factorial(Wakashamo[i])/(2*math.factorial(Wakashamo[i]-2))

print(int(counter))


### FIXED CODE ###

import math 
import collections

N = int(input())
String = []
for i in range (0, N):
	S = str(input())
	S = sorted(S)
	V = str(S[0])
	for j in range (1, 10):
		V = V+str(S[j])
	String.append(V)
    
cnt = collections.Counter()
for word in String:
	cnt[word] += 1

V = cnt.most_common()

count = 0

for i in range (0, len(V)):
	count+=math.comb(V[i][1], 2)
    
print(count)
### BUGGY CODE ###

def check(i, j, n, m):
  cnt = 0
  for a in [- 1, 0, 1]:
    for b in [- 1, 0, 1]:
      if(0 <= i + a and i + a < n and 0 <= j + b and j + b < m):
        cnt += 1
  if(cnt % 2 == 0):
    return 0
  else:
    return 1

n, m = list(map(int, input().split()))
cnt = 0
for i in range(n):
  for j in range(m):
    cnt += check(i, j, n, m)

print(cnt)


### FIXED CODE ###

n, m = list(map(int, input().split()))
print(abs((m * n) - (2 * (m + n) - 4)))
### BUGGY CODE ###

import sys
from bisect import bisect_left,bisect_right,insort
#input = sys.stdin.readline

def main():
    n,k=map(int,input().split())
    s=list(input())
    flg,cnt,chk='1',0,[0]    
    for i in range(n):
        if s[i]==flg:
            chk[cnt]+=1
        else:
            flg=str((int(flg)+1)%2)
            cnt+=1
            chk.append(1)
    lng=len(chk)
    if k*2>lng:
        print(n)
    else:
        i=1
        ans=0
        while i+2*(k-1)<=n-1:
            ans=max(ans,sum(chk[i-1:i+2*k]))
            i+=2
        print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from itertools import accumulate
from bisect import bisect_left,bisect_right,insort
#input = sys.stdin.readline

def main():
    n,k=map(int,input().split())
    s=list(input())
    flg,cnt,chk='1',0,[0]    
    for i in range(n):
        if s[i]==flg:
            chk[cnt]+=1
        else:
            flg=str((int(flg)+1)%2)
            cnt+=1
            chk.append(1)
    if s[-1]=='0':
        chk.append(0)
    lng=len(chk)
    if k*2>lng:
        print(n)
    else:
        ans=0
        acc=[0]+list(accumulate(chk))
        for i in range(0,len(chk)-2*k,2):
            ans=max(ans,acc[i+2*k+1]-acc[i])
        print(ans)

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

S = input()
Q = int(input())

reverse = False
for _ in range(Q):
    query= list(input().split()) 
    if query[0] == '1':
        reverse = not reverse
    elif query[0] == '2':
        if query[1] == '1':
            if reverse:
                S = ''.join([S,query[2]])
            else:
                S = ''.join([query[2],S])
        elif query[1] == '2':
            if reverse:
                S = ''.join([query[2],S])
            else:
                S = ''.join([S,query[2]])

if reverse:
    S = S[::-1]

print(S)

### FIXED CODE ###

def main():

    S = input()
    Q = int(input())

    reverse = False
    head = ''
    tail = ''

    for _ in range(Q):
        query= input()
        if query == '1':
            reverse = not reverse
            head, tail = tail, head
        else:
            _, f, c = query.split()
            if f == '1':
                head = ''.join([head,c])
            else:
                tail = ''.join([tail,c])

    if reverse:
        S = S[::-1]

    print(''.join([head[::-1], S, tail]))

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

import sys
count = int(sys.stdin.readline())
zenbu = []

for x in range(count):
    keihin = sys.stdin.readline()

    if not keihin in zenbu:
        zenbu.append(keihin)
print(len(zenbu))
        

### FIXED CODE ###

count = int(input())
zenbu = set()
 
for x in range(count):
    keihin = input()
    zenbu.add(keihin)
print(len(zenbu))
### BUGGY CODE ###

s_l = list(input())
result = [0] *len(s_l)
moving = [1] *len(s_l)

for i in range(len(s_l)):
    if moving[i] == 0:
        continue
    str_rl = s_l[i]
    shift = 0
    count = 0
    while str_rl == s_l[i]:
        if str_rl == 'R':
            shift += 1
        else:
            shift -= 1
        count += 1
        if count%2 == 0 and str_rl =='R':
            moving[i] += moving[i+shift]
            moving[i+shift] = 0
        str_rl = s_l[i+shift]
    if count%2 != 0:
        if str_rl == 'R':
            shift += 1
        else:
            shift -= 1
    result[i+shift] += moving[i]

print(' '.join(map(str,result)))



### FIXED CODE ###

s_l = list(input())
n = len(s_l)
result = [1] *len(s_l)

# only for R
for i in range(n):
    if s_l[i] == 'L':
        continue
    if s_l[i+1] == 'L':
        continue
    else:
        result[i+2] += result[i]
        result[i] = 0

# only for L
for i in range(n):
    j = n-1 - i
    if s_l[j] == 'R':
        continue
    if s_l[j-1] == 'R':
        continue
    else:
        result[j-2] += result[j]
        result[j] = 0

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

import numpy as np
N, K = map(int, input().split())
H = np.array([int(h) for h in input().split()])

dp = np.zeros(N, dtype=int)
k = np.array([i for i in range(1, K+1)])

for n in range(1, N):
    start = np.maximum(n-k, 0)
    if n < K:
        dp[n] = np.amin(dp[start] + np.abs(H[n]-H[start]))
    else:
        dp[n] = np.min(dp[n - k] + np.abs(H[n] - H[n - k]))


print(dp[N-1])



### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
# H = np.array([int(h) for h in input().split()])
H = np.array(list(map(int, input().split())))

dp = np.zeros(N, dtype=int)
k = np.array([i for i in range(1, K+1)])

for n in range(1, N):
    start = max(n-K, 0)
    #if n < K:
    #   dp[n] = np.amin(dp[start] + np.abs(H[n]-H[start]))
    #else:
    #   dp[n] = np.min(dp[n - k] + np.abs(H[n] - H[n - k]))
    dp[n] = np.min(dp[start:n] + np.abs(H[n]-H[start:n]))

print(dp[N-1])
### BUGGY CODE ###

N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
    w[i],v[i]=map(int,input().split())
dp=[[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j<w[i]:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i])
print(dp[N][W])


### FIXED CODE ###

INF = 2000000000
"""
メモ : Pythonでは無限大を表す float('inf') があるが, 処理がかなり重たいので
       代わりにsum(v)より真に大きい 2*10^9 を INFとする.
       (https://atcoder.jp/contests/dp/tasks/dp_e において,PyPyを使用して,
        前者だと1060ms, 後者だと570msで2倍近く差が出ている.)
"""
n,W = map(int,input().split())
w = [0]*n
v = [0]*n
for i in range(n):
    w[i], v[i] = map(int, input().split())
sum_v = sum(v)
dp = [[INF for i in range(sum_v + 1)] for j in range(n + 1)]
# dp[i][j]には重さが入る.
# dp[i][j]=(i番目までの品物から価値がちょうどｊになるための重さの最小値)

# ここからメイン
dp[0][0] = 0
for i in range(n):
    for j in range(sum_v + 1):
        if j < v[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i])

# n個まで使って,重さがlimit_wを超えないで価値が最大のものを求める.
max_value = 0
for i in range(sum_v + 1):
    if dp[n][i] <= W:
        max_value = i
print(max_value)
### BUGGY CODE ###

import numpy as np

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

left = np.array([[0] * W for i in range(H)])
for i in range(H):
    c = -1
    for j in range(W):
        if S[i][j] == '#':
            c = -1
        else:
            c += 1
        left[i][j] = c

right = np.array([[0] * W for i in range(H)])
for i in range(H):
    c = -1
    for j in range(W-1, -1, -1):
        if S[i][j] == '#':
            c = -1
        else:
            c += 1
        right[i][j] = c

up = np.array([[0] * W for i in range(H)])
for j in range(W):
    c = -1
    for i in range(H):
        if S[i][j] == '#':
            c = -1
        else:
            c += 1
        up[i][j] = c

down = np.array([[0] * W for i in range(H)])
for j in range(W):
    c = -1
    for i in range(H-1, -1, -1):
        if S[i][j] == '#':
            c = -1
        else:
            c += 1
        down[i][j] = c

n_all = right+left+up+down
print(np.max(n_all)+1)


### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)]) == "."

D = np.zeros((H, W), dtype=int)
U = np.zeros((H, W), dtype=int)
R = np.zeros((H, W), dtype=int)
L = np.zeros((H, W), dtype=int)

for i in range(H):
    U[i] = (U[i-1]+1)*S[i]
    D[-i - 1] = (D[-i] + 1) * S[-i - 1]

for i in range(W):
    L[:, i] = (L[:, i - 1] + 1) * S[:, i]
    R[:, -i - 1] = (R[:, -i] + 1) * S[:, -i - 1]

print(np.max(D + U + R + L) - 3)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
i=0
j=0
for i in range(n):
  b=-10000
  for j in range(n):
    if j==i:
      continue
    else:
      if b<=a[j]:
        b=a[j]
  print(b)

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
list=[]
i=0
j=0
l=0
m=0
o=0
c=max(a)
for i in range(n):
  if c!=a[i]:
    continue
  else:
    list.append(i)
if len(list)>1:
  for l in range(n):
    print(c)
else:
  del a[list[0]]
  d=max(a)
  for o in range(n):
    if o==list[0]:
      print(d)
    else:
      print(c)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,a,b=map(int,input().split())
s=input()
ok=0
x=0
ans=""
for i in range(n):
    ss=s[i]
    if ss=="a" and ok<a+b:
        ok+=1
        ans+="Yes\n"
    elif ss=="b" and ok<a+b and x<b:
        ok+=1
        x+=1
        ans+="Yes\n"
    else:
        ans+="No\n"

print(ans[:-1])


### FIXED CODE ###

import sys
input=sys.stdin.readline
n,a,b=map(int,input().split())
s=input()
ok=0
x=0
ans=[]
for i in range(n):
    ss=s[i]
    if ss=="a" and ok<a+b:
        ok+=1
        ans.append("Yes")
    elif ss=="b" and ok<a+b and x<b:
        ok+=1
        x+=1
        ans.append("Yes")
    else:
        ans.append("No")

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

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

# check reachability B -> A ?
# 隣接和table
P = [B[(i-1)%N] + B[(i+1)%N] for i in range(N)]

ans = 0
nmatch = 0 
while True:
    upd = False
    nmatch = 0 
    for i in range(N):
        if B[i] == A[i]:
            nmatch += 1
            continue
        if B[i] <= P[i]:
            continue
        if B[i] - P[i] >= A[i]:
            P[(i-1)%N] -= P[i]
            P[(i+1)%N] -= P[i]
            B[i] -= P[i]
            upd = True
            ans += 1
    if not upd:
        break

print(ans if nmatch == N else -1)


### FIXED CODE ###

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

# check reachability B -> A ?
# 隣接和table
P = [B[(i-1)%N] + B[(i+1)%N] for i in range(N)]
D = deque(i for i in range(N) if B[i] - P[i] >= A[i])
ans = 0
nmatch = [B[i] == A[i] for i in range(N)].count(True)
while D:
    upd = False
    i = D.popleft()
    if B[i] == A[i]:
        nmatch += 1
        continue
    if B[i] <= P[i]:
        continue
    if B[i] - P[i] >= A[i]:
        n = (B[i] - A[i]) // P[i]
        P[(i-1)%N] -= P[i] * n
        P[(i+1)%N] -= P[i] * n
        B[i] -= P[i] * n
        upd = True
        ans += n
        if B[i] == A[i]:
            nmatch += 1
        if B[(i-1)%N] - P[(i-1)%N] >= A[(i-1)%N]:
            D.append((i-1)%N)
        if B[(i+1)%N] - P[(i+1)%N] >= A[(i+1)%N]:
            D.append((i+1)%N)
    if not upd:
        break

print(ans if nmatch == N else -1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

s = input().split() 
s = list(s[0])
t = input().split() 
t = list(t[0])
f = [[] for _ in range(26)]

for i in range(len(s)):
    f[ord(s[i])-97].append(i)

g = [-1 for _ in range(len(t))]
if len(f[ord(t[0])-97]) == 0:
    print(-1)
    sys.exit()
g[0] = f[ord(t[0])-97][0]
cnt = 0
for i in range(1,len(t)):
    if len(f[ord(t[i])-97]) == 0:
        print(-1)
        sys.exit()

    if f[ord(t[i])-97][-1] > g[i-1]:
        for j in f[ord(t[i])-97]:
            if j > g[i-1]:
                g[i] = j
                break
    else:
        g[i] = f[ord(t[i])-97][0]
    if g[i] <= g[i-1]:
        cnt += 1

print(cnt*len(s)+g[-1]+1)


### FIXED CODE ###

import sys
input = sys.stdin.readline

import bisect

s = input().split() 
s = list(s[0])
t = input().split() 
t = list(t[0])
f = [[] for _ in range(26)]

for i in range(len(s)):
    f[ord(s[i])-97].append(i)

g = [-1 for _ in range(len(t))]
if len(f[ord(t[0])-97]) == 0:
    print(-1)
    sys.exit()
g[0] = f[ord(t[0])-97][0]
cnt = 0
for i in range(1,len(t)):
    if len(f[ord(t[i])-97]) == 0:
        print(-1)
        sys.exit()

    if f[ord(t[i])-97][-1] > g[i-1]:
        index = bisect.bisect_right(f[ord(t[i])-97], g[i-1])
        g[i] = f[ord(t[i])-97][index]
    else:
        g[i] = f[ord(t[i])-97][0]
    if g[i] <= g[i-1]:
        cnt += 1

print(cnt*len(s)+g[-1]+1)
### BUGGY CODE ###

A,B,K=(int(x) for x in input().split())

for i in range(K):
    if(A>0):
        A-=1
    elif(B>0):
        B-=1
    
print(A,B)

### FIXED CODE ###

A,B,K=(int(x) for x in input().split())

if(A>K):
    A-=K
    print(A,B)
elif(A+B>K):
    B-=K-A
    print(0,B)
else:
    print("0 0")
### BUGGY CODE ###

S = input('')
Q = int(input(''))
for i in range(Q):
    str = input('')
    if(str.count(' ') == 0 and str == '1'):
        S = S[::-1]
    else:
        T, F, C = str.split(' ')
        if(T == '2' and F == '1'):
            S = C + S
        elif(T == '2' and F == '2'):
            S = S + C
print(S)


### FIXED CODE ###

S = input('')
Q = int(input(''))
head, tail, rev_flag = '', '', 1
for i in range(Q):
    char = input()
    if char == '1':
        rev_flag *= -1
    else:
        t, f, c = char.split()
        if (f == '1' and rev_flag == 1) or (f == '2' and rev_flag == -1):
            head = c + head
        elif (f == '2' and rev_flag == 1) or (f == '1' and rev_flag == -1):
            tail = tail + c
if rev_flag == 1:
    print(head, S, tail, sep='')
else:
    print(tail[::-1], S[::-1], head[::-1], sep='')
### BUGGY CODE ###

import sys
import math
import bisect
import subprocess
import collections

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

### FIXED CODE ###

from collections import*
from bisect import*
s=input()
n=len(s)
t=input()
d=defaultdict(list)
for i,c in enumerate(s):
    d[c].append(i)
m=-1
o=0
for c in t:
    if not d[c]:
        print(-1)
        exit()
    i=bisect(d[c],m)
    if len(d[c])==i:
        o+=1
        m=d[c][0]
    else:
        m=d[c][i]
print(o*n+m+1)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline
h, w, k = map(int, input().split())
x1, y1, x2, y2 = [int(a) - 1 for a in input().split()]
c = [input() for _ in range(h)]

inf = 10 ** 8
d = [[inf for _ in range(w)] for _ in range(h)]
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]


que = deque()
for i in range(4):
    d[x1][y1] = 0
    que.append((x1, y1))
    
while len(que):
    cur_x, cur_y = que.popleft()
    if cur_x == x2 and cur_y == y2:
        break
    for dx, dy in move:
        to_x, to_y = cur_x, cur_y
        for _ in range(k):
            to_x, to_y = to_x + dx, to_y + dy
            if 0 <= to_x < h and 0 <= to_y < w and c[to_x][to_y] == '.' and d[to_x][to_y] > d[cur_x][cur_y]:
                    d[to_x][to_y] = d[cur_x][cur_y] + 1
                    que.append((to_x, to_y))
            else:
                break


print(-1 if d[x2][y2] == inf else d[x2][y2])

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
h, w, k = map(int, input().split())
x1, y1, x2, y2 = [int(a) - 1 for a in input().split()]
c = [input() for _ in range(h)]

inf = 10 ** 8
d = [[inf for _ in range(w)] for _ in range(h)]
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]


que = deque()
for i in range(4):
    d[x1][y1] = 0
    que.append((x1, y1))
    
while len(que):
    cur_x, cur_y = que.popleft()
    if cur_x == x2 and cur_y == y2:
        break
    for dx, dy in move:
        to_x, to_y = cur_x, cur_y
        for _ in range(k):
            to_x += dx
            to_y += dy
            if 0 <= to_x < h and 0 <= to_y < w and c[to_x][to_y] == '.':
                if d[to_x][to_y] > d[cur_x][cur_y] + 1:
                    d[to_x][to_y] = d[cur_x][cur_y] + 1
                    que.append((to_x, to_y))
                elif d[to_x][to_y] == d[cur_x][cur_y] + 1:
                    continue
                else:
                    break
            else:
                break


print(-1 if d[x2][y2] == inf else d[x2][y2])
### BUGGY CODE ###

import sys
def h(i):
 l=2*i;r=l+1
 if r<=H:
  if A[i]<A[l]:
   if A[l]<A[r]:A[i],A[r]=A[r],A[i];h(r)
   else:A[i],A[l]=A[l],A[i];h(l)
  elif A[i]<A[r]:A[i],A[r]=A[r],A[i];h(r)
 elif l<=H and A[i]<A[l]:A[i],A[l]=A[l],A[i];h(l)
H=0
A=[0]*2000001
for e in sys.stdin:
 if'i'==e[0]:
  H+=1;A[H]=int(e[7:]);k=H
  while k>1 and A[k//2]<A[k]:A[k],A[k//2]=A[k//2],A[k];k//=2
 elif'x'==e[1]:
  print(A[1])
  if H>1:A[1]=A[H]
  H-=1;h(1)


### FIXED CODE ###

import sys
from heapq import*
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
 else:print('\n'.join(map(str,O)))
### BUGGY CODE ###

h,w = map(int,input().split())
a = ['*'*(w+2)]+['*'+input()+'*' for _ in range(h)]+['*'*(w+2)]
ans = 0
while True:
    k = 1
    l = []
    for i in range(1,h+1):
        for j in range(1,w+1):
            if a[i][j]=='.':
                k = 0
            if a[i][j-1]=='#' or a[i][j+1]=='#' or a[i+1][j]=='#' or a[i-1][j]=='#':
                l.append([i,j])
    for l_ in l:
        a[l_[0]]=a[l_[0]][:l_[1]]+'#'+a[l_[0]][l_[1]+1:]
    if k:
        break
    ans += 1
print(ans)

### FIXED CODE ###

h,w = map(int,input().split())
a = [input() for _ in range(h)]
ans = 0
queue = []
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            queue.append([i,j])
from collections import deque
queue = deque(queue)
dxy = [(0,1), (0,-1), (1,0), (-1,0)]
dp = [[10**4]*w for _ in range(h)]
for i,j in queue:
    dp[i][j] = 0
while len(queue):
    y,x = queue.popleft()
    d = dp[y][x]
    for dx,dy in dxy:
        nx, ny = x+dx, y+dy
        if not 0<=nx<=w-1:
            continue
        elif not 0<=ny<=h-1:
            continue
        elif dp[ny][nx]<=d+1:
            continue
        dp[ny][nx] = d+1
        queue.append((ny,nx))
print(max([max(dp[row]) for row in range(h)]))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
cnt = 1
for i in range(n):
    cnt *= a[i]
    if cnt > 10**18:
        cnt = -1
print(cnt)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
cnt = 1
if 0 in a:
    print(0)
    exit()
for i in range(n):
    cnt *= a[i]
    if cnt > 10**18:
        cnt = -1
        break
print(cnt)