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


def factorization(n):
    arr = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt

    if temp!=1:
        arr[temp] = 1

    if not arr:
        arr[n] = 1

    return arr


n, m = map(int, input().split())
a = list(map(int, input().split()))
# a2 = [num//2 for num in a]
acount = [None]*n # aを2で割れる回数
anum = [None]*n # 割ったあとの残り(=奇数)
for i,num in enumerate(a):
    c = 0
    while num%2==0:
        num //=2
        c += 1
    acount[i] = c
    anum[i] = num
if all(item==acount[0] for item in acount):
    cc = {}
    for num in anum:
        tmp = factorization(num)
        for k,v in tmp.items():
            if k in cc:
                cc[k] = max(cc[k], v)
            else:
                cc[k] = v
    num = 1
    for k,v in cc.items():
        num *= pow(k,v)
    num0 = num * (pow(2, (acount[0]-1)))
    span = num0*2
    if m<num0:
        print(0)
    else:
        print(int((m-num0)//span + 1))
else:
    print(0)

### FIXED CODE ###


def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

def lcm(a, b):
    return a//gcd(a, b)*b

def lcms(a):
    l = a[0]
    for num in a[1:]:
        l = lcm(l, num)
    return l

n, m = map(int, input().split())
a = list(map(int, input().split()))
# a2 = [num//2 for num in a]
acount = [None]*n # aを2で割れる回数
anum = [None]*n # 割ったあとの残り(=奇数)
for i,num in enumerate(a):
    c = 0
    while num%2==0 and num>1:
        num //=2
        c += 1
    acount[i] = c
    anum[i] = num
if all(item==acount[0] for item in acount):
    l = lcms(anum)
    num0 = l * (pow(2, (acount[0]-1)))
    span = num0*2
    if m<num0:
        print(0)
    else:
        print(int((m-num0)//span + 1))
else:
    print(0)
### BUGGY CODE ###

from collections import deque
reverse = -1
S = list(input())
Q = int(input())
for _ in range(Q):
    Query = input().split()
    if Query[0] == "1":
        reverse *= -1
    else:
        if Query[1] == "1":
            if reverse == 1:
                S.append(Query[2])
            else:
                S.insert(0, Query[2])
        else:
            if reverse == 1:
                S.insert(0, Query[2])
            else:
                S.append(Query[2])

ans = "".join(S)
if reverse == 1:
    ans = ans[::-1]
print(ans)


### FIXED CODE ###

from collections import deque
reverse = -1
S = deque(input())
Q = int(input())
for _ in range(Q):
    Query = input().split()
    if Query[0] == "1":
        reverse *= -1
    else:
        if Query[1] == "1":
            if reverse == 1:
                S.append(Query[2])
            else:
                S.appendleft(Query[2])
        else:
            if reverse == 1:
                S.appendleft(Query[2])
            else:
                S.append(Query[2])

ans = "".join(S)
if reverse == 1:
    ans = ans[::-1]
print(ans)
### BUGGY CODE ###

import itertools
import math
import sys
from collections import Counter
from fractions import gcd
from functools import reduce
import sys
sys.setrecursionlimit(4100000)

n = int(input())
s = [int(input()) for i in range(n)]
ans = 0

def dfs(index, total):
    if index == n:
        if total % 10 != 0:
            global ans
            ans = max(ans, total)
        return
    dfs(index + 1, total + s[index]) or dfs(index + 1, total)

dfs(0, 0)
print(ans)


### FIXED CODE ###

import itertools
import math
import sys
from collections import Counter
from fractions import gcd
from functools import reduce
import sys
sys.setrecursionlimit(4100000)

INF = 1 << 60

# ここから書き始める
n = int(input())
s = [int(input()) for i in range(n)]
if sum(s) % 10 != 0:
    print(sum(s))
else:
    s.sort()
    for i in s:
        if i % 10 != 0:
            print(sum(s) - i)
            break
    else:
        print(0)
### BUGGY CODE ###

n = int(input())
l = 0
r = n-1

def get(i):
	print(i)
	s = input()
	if s == 'Vacant':
		exit()
	return s


def kind(i):
	return i%2 ^ get(i)=='Male'

while True:
	kl = kind(l)
	kr = kind(r)
	m = (l+r)//2
	if kind(m)==kl:
		l = m
	else:
		r = m



### FIXED CODE ###

n = int(input())
l = 0
r = n-1

def get(i):
	print(i)
	s = input()
	if s == 'Vacant':
		exit()
	return s


def kind(i):
	return (i%2) ^ (get(i)=='Male')


kl = kind(l)
kr = kind(r)

while True:
	m = (l+r)//2
	km = kind(m)
	if km==kl:
		l, kl = m, km
	else:
		r, kr = m, km
### BUGGY CODE ###

def main():
    n,k = map(int,input().split())
    h = [int(i) for i in input().split()]
    INF =  float('inf')
    dp = [INF for i in range(n)]
    dp[0] = 0
    for i in range(n):
        for j in range(1,k+1):
            if i+j<n:
                dp[i+j] = min(dp[i]+abs(h[i]-h[i+j]),dp[i+j])
                
    print(dp[n-1])

main()

### FIXED CODE ###

def main():
    n,k = map(int,input().split())
    h = [int(i) for i in input().split()]
    INF =  float('inf')
    dp = [INF for i in range(n)]
    dp[0] = 0
    dp[1] = abs(h[0]-h[1])
    for i in range(2,n):
        dp[i] = min(dp[i-j]+abs(h[i-j]-h[i]) for j in range(1,min(i,k)+1))
    print(dp[n-1])

main()
### BUGGY CODE ###

job = list()
salary = list()
k = 0
n,m = map(int,input().split())

for i in range(n):
    a,b = map(int,input().split())
    job.append((a,b))

job.sort(reverse = True)

for x in job:
    a,b = x
    salary.append(b)

    if a + k > m:
        salary.remove(min(salary))
    else:
        k += 1

print(sum(salary))


### FIXED CODE ###

import heapq
job = list()
salary = list()
n,m = map(int,input().split())

for i in range(n):
    a,b = map(int,input().split())
    job.append((a,b))

job.sort(reverse = True)

for x in job:
    s,t = x
    heapq.heappush(salary,t)
    if s - m > 0:
        heapq.heappop(salary)
    else:
        m -= 1

print(sum(salary))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
from fractions import gcd
from functools import reduce
def lcm(x,y):
  return (x*y)//gcd(x,y)
l = reduce(lcm, a)
mod = 10**9+7
ans = 0
for i in range(n):
  ans += l // a[i]
  ans %= mod
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
from fractions import gcd
from functools import reduce
def lcm(x,y):
  return (x*y)//gcd(x,y)
mod = 10**9+7
l = reduce(lcm, a) % mod
ans = 0
for i in range(n):
  ans += l * pow(a[i], mod - 2, mod)
  ans %= mod
print(ans)
### BUGGY CODE ###

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

import fractions
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(l):
    tmp = l[0]
    for i in range(1, len(l)):
        tmp = lcm_base(tmp, l[i])
    return tmp

lcm = lcm_list(a)
mod = 10**9+7


ans = 0
for i in range(n):
    tmp = lcm * pow(a[i], mod-2, mod)
    ans += tmp
    ans %= mod
print(ans)

### FIXED CODE ###

#%%
n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr



tmp = [0] * (10**6+1)
for i in range(n):
    t = factorization(a[i])
    for j in range(len(t)):
        tmp[t[j][0]] = max(tmp[t[j][0]], t[j][1])

#print(tmp[:20])

lcm = 1
for i in range(1, 10**6+1):
    x = i 
    y = tmp[i] 
    for j in range(y):
        lcm *= x
        lcm %= mod

#print(lcm)

ans = 0
for i in range(n):
    q = lcm * pow(a[i], mod-2, mod)
    ans += q
    ans %= mod
print(ans)
### BUGGY CODE ###

#python3

INF = int(1e9)

def main():

    n, k = map(int, input().split()) 
    a = [int(i) for i in input().split()]
    h = [0] * 110000
    for i in range(n):
        h[i] = a[i] 


    dp = [INF] * 110000
    dp[0] = 0
    for i in range(n):
        for j in range(1, k+1):
            dp[i+j] = min(dp[i+j], dp[i] + abs(h[i] - h[i+j]))

    print(dp[n-1])

main() 

### FIXED CODE ###

#python3

INF = int(1e9)

def main():

    n, k = map(int, input().split()) 
    h = [int(i) for i in input().split()] + [0]* 110


    dp = [INF] * 110000
    dp[0] = 0
    for i in range(n):
        for j in range(1, k+1):
            dp[i+j] = min(dp[i+j], dp[i] + abs(h[i] - h[i+j]))

    print(dp[n-1])

main()
### BUGGY CODE ###

import sys

input = sys.stdin.readline

n, q = map(int, input().split(" "))
s = input()

place_of_AC = []
for i in range(len(s) - 1):
  if s[i:i+2] == "AC":
    place_of_AC.append(1)
  else:
    place_of_AC.append(0)
    
for _ in range(q):
  l, r = map(int, input().split(" "))
  out = sum(place_of_AC[l-1:r-1])
  print(out)

### FIXED CODE ###

import sys

input = sys.stdin.readline

n, q = map(int, input().split(" "))
s = input()
cnt = 0
place_of_AC = [0] * n

for i in range(len(s) - 1):
  place_of_AC[i]=cnt
  if s[i:i+2] == "AC":
    cnt += 1


#print(place_of_AC)
  
for _ in range(q):
  l, r = map(int, input().split(" "))
  out = place_of_AC[r-1] - place_of_AC[l-1]
  print(out)
### BUGGY CODE ###

# N=頂点数、X,Y=座標
N, X, Y = map(int, input().split())
X -= 1
Y -= 1

# 未セットの値
INF = 10**4

# キューデータ(次の値、最短距離)
queue_list = []

# 最短距離ごとのリスト
min_e_list = [0 for i in range(N)]

for i in range(N):
    # キューデータ初期値をセット
    queue_list.append([i, 0])
    # 最短距離リスト(最短距離)
    min_dist_list = [INF for i in range(N)] 

    # キューデータが空になるまで繰り返す
    while(len(queue_list) != 0):
        
        # 先頭データを取り出す。
        pop_data = queue_list.pop(0)

        # 取り出した座標がセット済みの場合は何もしない
        if(min_dist_list[pop_data[0]] != INF):
            continue

        # 最短距離リストにデータセット
        min_dist_list[pop_data[0]] = pop_data[1]

        # 2重に数えないよう(i < 取り出した座標時)、最短距離ごとのリストにデータセット
        if(i < pop_data[0]):
            min_e_list[pop_data[1]] += 1

        # 1.隣の頂点(次の座標、+1,-1した値)
        if(pop_data[0]+1 < N):
            queue_list.append([pop_data[0]+1, pop_data[1]+1])
        if(pop_data[0] > 0 and pop_data[0]-1 < N):
            queue_list.append([pop_data[0]-1, pop_data[1]+1])
        
        # 2.X,Yで示した値
        if(pop_data[0] < Y and pop_data[0] == X):
            queue_list.append([Y, pop_data[1]+1])
        if(pop_data[0] < X and pop_data[0] == Y):
            queue_list.append([X, pop_data[1]+1])

# 出力
for i,v in enumerate(min_e_list):
    if(i != 0):
        print(v)

### FIXED CODE ###

# N=頂点数、X,Y=座標
N, X, Y = map(int, input().split())

# 最短距離データ
min_dist_list = [0 for i in range(N+1)]

for i in range(1,N+1):
    for j in range(i+1, N+1):
            t_dist = min(abs(j-i), 1+abs(X-i)+abs(Y-j), 1+abs(Y-i)+abs(X-j)) 
            min_dist_list[t_dist] += 1         

for i in range(1, N):
    print(min_dist_list[i])
### BUGGY CODE ###

import numpy as np
import sys
input = sys.stdin.readline
N = int(input())
S = [list(input().rstrip()) for i in range(N)]
T = [[""] * (N*2) for i in range(2*N)]
for i in range(2*N):
    if i < N:
        T[i] = S[i] + S[i]
    else:
        T[i] = S[i - N] + S[i-N]
ans = 0
s = np.array(T)
for A in range(N):
    for B in range(N):
        tmp = s[A:A+N, B:B+N]
        if (tmp != tmp.T).any() == False:
            ans += 1

print(ans)


### FIXED CODE ###

import collections
import sys
import numpy as np
input = sys.stdin.readline
table = collections.defaultdict(set)
N = int(input())
S = [list(input().rstrip()) for i in range(N)]
T = [[""] * (N*2) for i in range(2*N)]
table2 = [[set() for j in range(N)] for i in range(N)]

for i in range(2*N):
    if i < N:
        T[i] = S[i] + S[i]
    else:
        T[i] = S[i - N] + S[i-N]
ans = 0
T = np.array(T)
for i in range(N):
    tmp = T[i:i+N, N-1-i:2*N-1-i]

    if (tmp == tmp.T).all():
        ans += N - (N // 2)

    tmp = T[i+1:i+N+1, N-1-i:2*N-1-i]

    if (tmp == tmp.T).all():
        ans += N // 2
print(ans)
### BUGGY CODE ###

n = int(input())
Ai = list(map(int, input().split()))
sum_ans = 0
divied_num = 10**9 + 7
for i in range(n-1):
    for j in range(i+1, n):
        sum_ans += Ai[i] * Ai[j]
        sum_ans = sum_ans % divied_num

print(sum_ans)

### FIXED CODE ###

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

sum_ans = sum(Ai)
ans = 0
mod = 1000000007

for i in range(n-1):
    sum_ans -= Ai[i]
    ans += sum_ans * Ai[i]
    ans %= mod

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

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

l = []
for i in range(n):
    d = int(input())
    l.append(d)

p = max(l)
while True:
    sm_k = 0
    k_no = 1
    for li in l:
        if sm_k + li > p:
            k_no += 1
            sm_k = li
        else:
            sm_k += li

    # print(p, k_no)
    if k_no <= k:
        print(p)
        break

    p += 1



### FIXED CODE ###

MAX_P = 100000 * 10000

n, k = map(int, input().split())
w = list()
for _ in range(n):
    w.append(int(input()))


# k台のトラックに、積載量Pでいくつ荷物が載せられるか
# 0 <= r <= n
def check(p):
    k_no = 1
    tmp = 0
    for i, wi in enumerate(w):
        if wi > p:
            return i
        if tmp + wi > p:
            if k_no == k:
                return i
            else:
                k_no += 1
                tmp = wi
        else:
            tmp += wi
    return len(w)


def solve():
    left = 1
    right = MAX_P

    while right - left > 1:
        mid = (left + right) // 2
        v = check(mid)  # v個載せられる
        if v < n:
            left = mid
        else:
            right = mid

    # print("left", left)
    # print("right", right)
    if check(left) >= n:
        return left
    else:
        return right

# for i in range(10):
#     print(i, check(i))

print(solve())
### BUGGY CODE ###

from collections import deque
import queue
n,m = map(int,input().split())

uv = [[] for i in range(n)]

for i in range(m):
    u,v = map(int,input().split())
    #uv[v-1].append(u-1)
    uv[u-1].append(v-1)
    
s,t = map(int,input().split())

check = [[0 for i in range(3)] for j in range(n)]

d = queue.Queue()
d.put([0,0,s-1])
#check[s-1][0] = 1

while not d.empty():
    for i in range(d.qsize()):
        num,cnt,ver = d.get()
        check[ver][num] = 1
        num = (num+1)%3
        cnt += 1
        for j in range(len(uv[ver])):
            #print(cnt,num,ver,j,t-1,uv[ver][j])
            if uv[ver][j] == t-1 and num == 0:
                print(cnt//3)
                exit()
            if check[uv[ver][j]][num] == 0:
                #check[uv[ver][j]][num] = 1
                d.put([num,cnt,uv[ver][j]])
                
print(-1)

### FIXED CODE ###

# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

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

# vertexごとに3つの状態数を持つ
N, M = lr()
graph = [[] for _ in range((N+1)*3)]  # 1-indexed
for _ in range(M):
    a, b = lr()
    a *= 3; b *= 3
    for i in range(3):
        j = i+1 if i < 2 else 0
        graph[a+i].append(b+j)

INF = 10 ** 15

def dijkstra(start):
    dist = [INF] * (N+1) * 3
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for i in graph[prev]:
            #print(graph[prev],dist[next],next)
            d1 = d + 1
            if dist[i] > d1:
                dist[i] = d1
                heappush(que, (d1, i))
    return dist

S, T = lr()
dist = dijkstra(S*3)
answer = dist[T*3]
if answer == INF:
    answer = -1
else:
    answer //= 3
print(answer)
### BUGGY CODE ###

N=int(input())
x=[]
min=10000000
ans=0
for i in range(1,N+1//2):
  if N%i==0:
    j=int(N/i)
    a=[i,j]
    x.append(a)
for i,j in x:
  if i+j<=min:
    ans=i+j-2
    min=i+j
print(ans)

### FIXED CODE ###

import math
N=int(input())
x=[]
min=10000000000000000
ans=0
sqN=math.ceil(math.sqrt(N))
for i in range(1,sqN+1):
  if N%i==0:
    j=int(N/i)
    a=[i,j]
    x.append(a)
for i,j in x:
  if i+j<=min:
    ans=i+j-2
    min=i+j
print(ans)
### BUGGY CODE ###

import copy

import math


def main():
    import collections

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

    for k in range(N):
        tmp_A = ignore(A, k)
        tmp_A = collections.Counter(tmp_A)
        su = 0
        for c in tmp_A:
            pair = tmp_A[c]
            if pair >= 2:
                su += combinations_count(pair, 2)
        print(su)


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def ignore(A, i):
    x = copy.copy(A)
    # del x[i]
    # return x
    x[i] = 0
    return x


if __name__ == '__main__':
    main()


### FIXED CODE ###



def main():
    import collections

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

    allc = collections.Counter(A)
    # all_list = [0]*N
    allsu = 0
    for pairs in sorted(allc.values(), reverse=True):
        allsu += pairs*(pairs-1)//2

    for a in A:
        num = allc[a]
        print(allsu - (num-1))

    # for i in range(N):
    #     x = A[i]
    #     A[i] = 0
    #     tmp_A = cc(A)
    #     su = 0
    #     for pairs in sorted(tmp_A.values(), reverse=True):
    #         if pairs >= 2:
    #             su += pairs*(pairs-1)//2
    #         else:
    #             break
    #     A[i] = x
    #     print(su)


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

from functools import lru_cache

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

@lru_cache(None)
def f(l, r, xl, xr):
  if l+1 == r:
    return xl * A[l] + xr * A[r]
  tmp = float("inf")
  for m in range(l+1, r):
    v = f(l, m, xl, xl+xr) + f(m, r, xl+xr, xr) - (xl+xr) * A[m]
    tmp = min(tmp, v)
  return tmp

print(f(0, N-1, 1, 1))

### FIXED CODE ###

from functools import lru_cache
 
N = int(input())
A = list(map(int, input().split()))
 
@lru_cache(None)
def f(l, r, xl, xr):
  if l+1 == r:
    return xl * A[l] + xr * A[r]
  tmp = float("inf")
  for m in range(l+1, r):
    v = f(l, m, xl, xl+xr) + f(m, r, xl+xr, xr) - (xl+xr) * A[m]
    tmp = min(tmp, v)
  return tmp
 
print(f(0, N-1, 1, 1))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 0
while all(A%2 == 0 for A in a):
    a = (i/2 for i in a )
    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 0
while all(A%2 == 0 for A in a):
	a = [i/2 for i in a ]
	ans += 1
print(ans)
### BUGGY CODE ###

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

ans='Yes'
for n in range(N-1,0,-1):
    num=H[n]
    check=max(H[:n])
    if check > num+1:
        ans='No'
print(ans)

### FIXED CODE ###

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

max_h=0
ans='Yes'

for n in range(N):
    if H[n] > max_h:
        max_h = H[n]
        
    if H[n] < max_h-1:
        ans='No'
        
print(ans)
### BUGGY CODE ###

S = str(input())
i, ans = (0, 0)
while i>=0 and i<len(S)-1:
    if S[i]!=S[i+1]:
        S = S[:i]+S[i+2:] if i+2<len(S) else S[:i]
        ans += 2
        i = max(0, i-1)
    else:
        i+=1
print(ans)


### FIXED CODE ###

from collections import deque
sin = input()
queue = deque(maxlen=len(sin))
for s in sin:
    if len(queue)>0 and queue[-1] != s:
        queue.pop()
    else:
        queue.append(s)
#print("".join(arr))
print(len(sin)-len(queue))
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

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

def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()


def main():
    n,k = LI()
    a = sorted(LI(), key=lambda x: -x)
    s = [set() for _ in range(k)]
    rs = set()
    for i in range(n):
        ai = a[i]
        if ai >= k:
            rs.add(i)
            continue
        for j in range(k-1,0,-1):
            sj = s[j]
            if sj:
                if j+ai < k:
                    s[j+ai] |= sj
                    s[j+ai].add(i)
                else:
                    rs |= sj
                    rs.add(i)
        s[ai].add(i)

    return n-len(rs)


print(main())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

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

def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()


def main():
    n,k = LI()
    a = sorted(LI())
    sa = sum(a)
    if sa < k:
        return n
    if sa - a[0] < k:
        return 0

    mi = 0
    ma = n-1

    def f(m):
        am = a[m]
        if am >= k:
            return True

        t = [False] * (k-am)
        t[0] = True
        tl = len(t)
        for i in range(n):
            if i==m:
                continue
            ai = a[i]
            for j in range(tl-1,-1,-1):
                if not t[j]:
                    continue
                if k <= j+ai:
                    continue
                if j+ai >= tl:
                    return True

                t[j+ai] = True

        return False

    while mi < ma:
        m = (mi+ma) // 2
        if f(m):
            ma = m
        else:
            mi = m+1

    return mi


print(main())
### BUGGY CODE ###

N = int(input())
arr = list(map(int, input().split()))
INF = 10 ** 18
ans = 1
for num in arr:
    ans *= num
 
print(ans) if ans <= INF else print(-1)

### FIXED CODE ###

N = int(input())
arr = sorted(map(int, input().split()))
INF = 10 ** 18
ans = 1
for num in arr:
    ans *= num
    if num > 0 and ans > INF:
        ans = -1
        break
    elif ans == 0:
        break

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

#!/usr/bin/env python3
import sys
from collections import deque
def solve(N: int, S: "List[str]"):
    matrix = [[] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if S[i][j] == "1":
                matrix[i].append(j)

    answer = -1
    for start_node in range(N):
        group = [0]*N
        queue = deque([(start_node,1)])

        while queue:
            node,count = queue.popleft()
            if not group[node]:
                group[node] = count

            for next_node in matrix[node]:
                if not group[next_node]:
                    queue.append((next_node,count+1))
            # print(group)

        # 条件を満たしているか判定
        # print(answer)
        for i in range(N):
            for j in range(N):
                if S[i][j] == "1":
                    if abs(group[i]-group[j]) == 1:
                        continue
                    else:
                        break
            else:
                continue
            break
        else:
            answer = max(answer,max(group))
    print(answer)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(N)]  # type: "List[int]"
    solve(N, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque

def solve(N: int, S: "List[str]"):
    matrix = [[] for _ in range(N)]
    d = [[10**5]*N for _ in range(N)]

    for i in range(N):
        d[i][i] = 0
        for j in range(N):
            if S[i][j] == "1":
                matrix[i].append(j)
                d[i][j] = 1
                d[j][i] = 1
    
    # ２部グラフ 判定
    stack = [(0,1)]
    color = [-1]*N

    while stack:
        node,c = stack.pop()
        color[node] = c

        for next in matrix[node]:
            if color[next] == -1:
                stack.append((next,~c))
            else:
                if c^color[next] == 0:
                    print(-1)
                    return


    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    answer = 0
    for i in range(N):
        answer = max(answer,max(d[i]))
    print(answer+1)
    return

def main():
    N = int(input())
    S = [input() for _ in range(N)]
    solve(N, S)

if __name__ == '__main__':
    main()