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

import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

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

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


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
B = list(map(int, sys.stdin.buffer.readline().split()))


# 逆から貪欲に操作可能
def solve():
    heap = [(-b, i) for i, b in enumerate(B)]
    heapq.heapify(heap)
    ret = 0
    while heap:
        b, i = heapq.heappop(heap)
        b *= -1
        a = A[i]
        if b < a:
            return -1
        if b == a:
            continue
        step = B[(i - 1) % N] + B[(i + 1) % N]
        if (b - a) // step == 0:
            return -1
        cnt = (b - a) // step
        ret += cnt
        b -= cnt * step
        B[i] = b
        heapq.heappush(heap, (-b, i))
    return ret


ans = solve()
print(ans)


### FIXED CODE ###

import heapq
import os
import sys

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

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


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
B = list(map(int, sys.stdin.buffer.readline().split()))


# 逆から貪欲に操作可能
def solve():
    heap = [(-b, i) for i, b in enumerate(B)]
    heapq.heapify(heap)
    ret = 0
    while heap:
        b, i = heapq.heappop(heap)
        b *= -1
        a = A[i]
        if b < a:
            return -1
        if b == a:
            continue
        step = B[(i - 1) % N] + B[(i + 1) % N]
        if (b - a) // step == 0:
            return -1
        cnt = (b - a) // step
        ret += cnt
        b -= cnt * step
        B[i] = b
        heapq.heappush(heap, (-b, i))
    return ret


ans = solve()
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
sumA=0
for i in range(N-1):
    for j in range(i+1,N):
        sumA=(A[i]*A[j])%(10**9+7)+sumA
print(sumA%(10**9+7))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
sumA=0
sumB=[0]
for i in range(N):
    sumB.append(sumB[i]+A[i])
    i=i+1
for j in range(N-1):
    sumA=sumA+(A[j]*(sumB[N]-sumB[j+1]))%(10**9+7)
    j=j+1
print(sumA%(10**9+7))
### BUGGY CODE ###

import sys

alp = [[] for _ in range(26)]

s = input()
t = input()
#s = 'contest'
#t = 'programming'

for i, x in enumerate(s):
    alp[ord(x) - 97].append(i)

ind_prev = -1
ind_prev_each_letter = [0 for _ in range(26)]
loop = 0
flag = True
for x in t:
    letter = alp[ord(x) - 97]

    if len(letter) == 0:
        print(-1)
        flag = False
        break
        
    if ind_prev >= letter[-1]:
        ind_prev = -1
        ind_prev_each_letter = [0 for _ in range(26)]
        loop += 1

    for i in range(ind_prev_each_letter[ord(x) - 97], len(letter)):
        y = letter[i]
        if y > ind_prev:
            ind_prev = y
            ind_prev_each_letter[ord(x) - 97] += 1
            break

if flag:
    print(loop * len(s) + ind_prev + 1)



### FIXED CODE ###

import numpy as np
from bisect import bisect_right

alp = [[] for _ in range(26)]

s = input()
t = input()
#s = 'contest'
#t = 'programming'

for i, x in enumerate(s):
    alp[ord(x) - 97].append(i)

ind_prev = -1
loop = 0
flag = True
for x in t:
    letter = alp[ord(x) - 97]

    if len(letter) == 0:
        print(-1)
        flag = False
        break
        
    if ind_prev >= letter[-1]:
        ind_prev = -1
        ind_prev_each_letter = [0 for _ in range(26)]
        loop += 1

    ind = bisect_right(letter, ind_prev)
    ind_prev = letter[ind]

if flag:
    print(loop * len(s) + ind_prev + 1)
### BUGGY CODE ###

#!/usr/bin/env python3
N, M = map(int, input().rstrip().split())
A = list(map(int, input().rstrip().split()))

B = []
C = []
for _ in range(M):
    b, c = map(int, input().rstrip().split())
    B.append(b)
    C.append(c)

Index = sorted(range(M), key=lambda i: C[i], reverse=True)

sum = 0
A.sort()
for index in Index:
    count = 0
    i = 0
    while True:
        if i >= len(A):
            break
        if A[i] < C[index] and count < B[index]:
            sum += C[index]
            A.pop(i)
            # print(A)
            count += 1
            continue
        if A[i] >= C[index] or count >= B[index]:
            break
        i += 1

if A:
    for a in A:
        sum += a

print(sum)


### FIXED CODE ###

#!/usr/bin/env python3
N, M = map(int, input().rstrip().split())
A = list(map(int, input().rstrip().split()))

B = []
C = []
for _ in range(M):
    b, c = map(int, input().rstrip().split())
    B.append(b)
    C.append(c)

Index = sorted(range(M), key=lambda i: C[i], reverse=True)

sum = 0
A.sort()
for index in Index:
    if A and A[0] >= C[index]:
        break
    count = 0
    i = 0
    while True:
        if i >= len(A):
            break
        if A[i] < C[index] and count < B[index]:
            sum += C[index]
            A.pop(i)
            # print(A)
            count += 1
            continue
        if A[i] >= C[index] or count >= B[index]:
            break
        i += 1

if A:
    for a in A:
        sum += a

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

import itertools
N=int(input())
an=[int(x) for x in map(int,input().split()[:N])]

def judgeXOR(v):
    for x in range(N):
        if x==0:
            if (v[N-1] ^ v[x+1] ) != (x+1):
                return False
        elif x==(N-1):
            if (v[0] ^ v[x-1]) !=(x+1):
                return False
        else:
            if (v[x-1] ^ v[x+1])!=(x+1):
                return False
    return True

for v in itertools.permutations(an,N):
    if v[0] !=an[0]:
        continue
    if judgeXOR(v):
        print("Yes")
        exit()

print("No")


### FIXED CODE ###

import itertools
N=int(input())
an=[int(x) for x in map(int,input().split()[:N])]

ret=an[0]
for x in range(1,N):
    ret= an[x] ^ ret

if ret==0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    n0=0
    print(n0)
    s=input()
    if s=="Vacant":sys.exit()
    left,right=0,n
    mid=(right+left)//2
    sl=s
    print(mid)
    sm=input()
    while sm!="Vacant" and right>left:
        if ((mid-left)%2==0 and sm==sl) or ((mid-left)%2==1 and sm!=sl):
            left=mid
            sl=sm
        else:
            sr=mid
        mid=(right+left)//2
        print(mid)
        sm=input()        


if __name__=='__main__':
    main()

### FIXED CODE ###

N=int(input())
l,r=0,N
print(0)
s=input()
ls=s
if s!='Vacant':
    for i in range(19):
        x=l+(r-l)//2
        print(x)
        s=input()
        if s=='Vacant':
            break
        elif (x-l)%2==0 and s==ls or (x-l)%2==1 and s!=ls:
            l=x
            ls=s
        else:
            r=x
### BUGGY CODE ###

import heapq

n, m = map(int, input().split())
ans = 0
jobs = []
to_do = []
heapq.heapify(to_do)
for i in range(n):
    array = list(map(int, input().split()))
    array[1] *= -1
    jobs.append(array)

for i in range(1, m+1):
    addition = [j for j in jobs if j[0] == i]
    if len(addition) > 0:
        for x, y in addition:
            heapq.heappush(to_do, y)
    if len(to_do) > 0:
        ans += -1 * heapq.heappop(to_do)

print(ans)



### FIXED CODE ###

import heapq
from collections import defaultdict

n, m = map(int, input().split())
ans = 0
jobs = defaultdict(list)
to_do = []
heapq.heapify(to_do)
for i in range(n):
    array = list(map(int, input().split()))
    array[1] *= -1
    jobs[array[0]].append(array[1])

for i in range(1, m+1):
    if len(jobs[i]) > 0:
        for j in jobs[i]:
            heapq.heappush(to_do, j)
    if len(to_do) > 0:
        ans += -1 * heapq.heappop(to_do)

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

import collections
N = int(input())
s = [input() for i in range(N)]
counter = collections.Counter(s)
max_k_list = [kv[0] for kv in dict(counter).items() if kv[1] == max(dict(counter).values())]
for i in range (len(max_k_list)):
  print(sorted(max_k_list)[i])

### FIXED CODE ###

import collections
N = int(input())
s = [input() for i in range(N)]
counter = collections.Counter(s)
max = max(dict(counter).values())
keys = [k for k, v in dict(counter).items() if v == max]
ans = sorted(keys)
for i in range (len(keys)):
  print(ans[i])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
IND = list(set(A))
# CNT = [A.count(x) for x in IND]
# print(IND)
# print(CNT)
CONB = [A.count(x)*(A.count(x)-1)//2 for x in IND]
# print(CONB)
SUM = sum(CONB)
CALC = [-1]*(N+1)
for i in A:
    if CALC[i] != -1:
        print(CALC[i])
    else:
        # n = CNT[IND.index(i)]
        # ans = SUM - CONB[IND.index(i)] + (n-1)*(n-2)//2
        ans = SUM - CONB[IND.index(i)] + (A.count(i)-1)*(A.count(i)-2)//2
        CALC[i] = ans
        print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
CNT = [0]*(N+1)
# IND = list(set(A))
# CNT = [A.count(x) for x in IND]
for i in A:
    CNT[i] += 1
# print(IND)
# print(CNT)
# CONB = [A.count(x)*(A.count(x)-1)//2 for x in IND]
CONB = [CNT[x]*(CNT[x]-1)//2 for x in range(len(CNT))]
# print(CONB)
SUM = sum(CONB)
for i in A:
    ans = SUM - CNT[i] + 1
    print(ans)
### BUGGY CODE ###

N = int(input())
H = list(map(int, input().split()))
for i in range(N):
    if H[i] > H[min(N - 1, i + 1)] + 1:
        print("No")
        exit()
    if i > 0:
        if H[i] < max(H[:i]) - 1:
            print("No")
            exit()
print("Yes")


### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
M = 0
for i in range(1, N):
    M = max(M, H[i - 1])
    if H[i] < M - 1:
        print("No")
        exit()
print("Yes")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
  h,n = map(int,input().split())

  dg = 10**5

  ba = []
  for _ in [0]*n:
      a,b = map(int,input().split())
      ba.append(b*dg+a)

  d = [10**9]*(h+1)

  d[0] = 0

  for i in range(1,h+1):
      for e in ba:
          a,b = e%dg,e//dg
          if i<=a:
              if d[i] > b:
                  d[i] = b
          else:
              if d[i] > d[i-a]+b:
                  d[i] = d[i-a]+b

  print(d[-1])
if __name__ == '__main__':
  main()


### FIXED CODE ###

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

dg = 10**5

ba = []
for _ in [0]*n:
    a,b = map(int,input().split())
    if a >= h:
        a = h
    ba.append(b*dg+a)
ba.sort()

d = [10**9]*(h+1)

d[0] = 0

for i in range(1,h+1):
    for e in ba:
        a,b = e%dg,e//dg
        if i<=a:
            if d[i] > b:
                d[i] = b
        else:
            if d[i] > d[i-a]+b:
                d[i] = d[i-a]+b

print(d[-1])
### BUGGY CODE ###

K, N = map(int, input().split())
lists = list(map(int, input().split()))

a = []
a = 1000000
for i in range(len(lists)):
    if abs(K - lists[i]) == 0:
        continue
    elif abs(K - lists[i]) < a:
        a = abs(K - lists[i])
b = 1000000
for i in range(len(lists)):
    for j in range(len(lists)):
        if abs(lists[i] - lists[j]) == 0:
            continue
        elif abs(lists[i] - lists[j]) < b:
            b = abs(lists[i] - lists[j])

# print(a)
# print(b)
c = a+b
print(c)

### FIXED CODE ###

K, N = map(int, input().split())
lists = list(map(int, input().split()))

lists_slic = lists[1:] + lists[0:1]

# print(lists_slic)
a = 0
for i in range(len(lists)):
    if lists_slic[i] - lists[i] < 0:
        b = lists_slic[i] - lists[i] + K
        if b > a:
            a = b
    else:
        if (lists_slic[i] - lists[i])>a:
            a = lists_slic[i] - lists[i]

c = K - a

print(c)
### BUGGY CODE ###

# def cmb(n, k, mod):
#     numerator = 1
#     for i in range(k):
#         numerator = (numerator * (n - i)) % mod

#     denominator = 1
#     for i in range(1, k + 1):
#         denominator = (denominator * i) % mod

#     return (numerator * pow(denominator, mod - 2, mod)) % mod

import math


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


import sys
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
a = list(map(int, input().split()))
freq = {}
for i in a:
    if i in freq:
        freq[i] += 1
    else:
        freq[i] = 1

inf = 1001001001
dp = [inf for _ in range(200005)]
dp2 = [inf for _ in range(200005)]
mod = 10**13 + 3

base = 0
for k, v in freq.items():
    if v > 2:
        dp[k] = combinations_count(v, 2)
        dp2[k] = combinations_count(v - 1, 2)
    elif v == 2:
        dp[k] = 1
        dp2[k] = 0
    else:
        dp[k] = 0
        dp2[k] = 0
    base += dp[k]

for i in a:
    print(base - dp[i] + dp2[i])


### FIXED CODE ###

# def cmb(n, k, mod):
#     numerator = 1
#     for i in range(k):
#         numerator = (numerator * (n - i)) % mod

#     denominator = 1
#     for i in range(1, k + 1):
#         denominator = (denominator * i) % mod

#     return (numerator * pow(denominator, mod - 2, mod)) % mod


def ncr(n, r):
    r = min(r, n - r)
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + i + 1 for i in range(r)]
    denominator = [i + 1 for i in range(r)]
    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= numerator[k]
    return int(result)


import math


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


import sys
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
a = list(map(int, input().split()))
freq = {}
for i in a:
    if i in freq:
        freq[i] += 1
    else:
        freq[i] = 1

inf = 1001001001
dp = [inf for _ in range(200005)]
dp2 = [inf for _ in range(200005)]
mod = 10**13 + 3

base = 0
for k, v in freq.items():
    if v > 2:
        dp[k] = ncr(v, 2)
        dp2[k] = ncr(v - 1, 2)
    elif v == 2:
        dp[k] = 1
        dp2[k] = 0
    else:
        dp[k] = 0
        dp2[k] = 0
    base += dp[k]

for i in a:
    print(base - dp[i] + dp2[i])
### BUGGY CODE ###

L,R = map(int,input().split())
ans = []
for i in range(L,R):
    for j in range(L+1,R+1):
        ans.append((i*j)%2019)
ans.sort()
print(ans[0])

### FIXED CODE ###

L,R = map(int,input().split())
ans = (L*(L+1))%2019
if R-L >= 2019:
    print(0)
    exit()
else:
    for i in range(L,R):
        for j in range(L+1,R+1):
            if ans > (i*j)%2019:
                ans = (i*j)%2019
print(ans)
### BUGGY CODE ###

from collections import deque

H,W=map(int,input().split())
CH,CW=map(int,input().split())
DH,DW=map(int,input().split())

S=[list(input()) for _ in range(H)]
MAX_COST = 10 ** 9
Cost=[ [ MAX_COST for _ in range(W)] for _ in range(H)]

# print(S)

ans = -1

deq = deque()

deq.append((CH-1,CW-1,0))
Cost[CH-1][CW-1] = 0;

# used = set()
five_five = [ (i,j) for i in range(-2,3,1) for j in range(-2,3,1) ]
# print(five_five)

while 0 < len(deq):
	h,w,c=deq.popleft()
	# print(h,w,c)
	for i,j in five_five:
		# print(i,j)
		if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
			if S[h+i][w+j] == '.':
				if (j == 0 and abs(i)==1) or (i==0 and abs(j)==1):
					if c < Cost[h+i][w+j]:
						Cost[h+i][w+j] = c
						deq.appendleft((h+i,w+j,Cost[h+i][w+j]))
				elif c + 1 < Cost[h+i][w+j]:
					Cost[h+i][w+j] = c + 1
					deq.append((h+i,w+j,Cost[h+i][w+j]))
					# print("updr ", h+i,w+j,Cost[h+i][w+j])

if Cost[DH-1][DW-1] == MAX_COST:
	print(-1)
else:
	print(Cost[DH-1][DW-1])

### FIXED CODE ###

from collections import deque

H,W=map(int,input().split())
CH,CW=map(int,input().split())
DH,DW=map(int,input().split())

S=[list(input()) for _ in range(H)]
MAX_COST = 10 ** 9
Cost=[ [ MAX_COST for _ in range(W)] for _ in range(H)]

# print(S)

ans = -1

deq = deque()

deq.append((CH-1,CW-1,0))
Cost[CH-1][CW-1] = 0;

walk=[(1,0),(0,1),(-1,0),(0,-1)]

# used = set()

while 0 < len(deq):
	h,w,c=deq.popleft()
	# print(h,w,c)
	for i,j in walk:
		if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
			if S[h+i][w+j] == '.' and c < Cost[h+i][w+j]:
				Cost[h+i][w+j] = c
				# print("updl ", i,j,h+i,w+j,c)
				deq.appendleft((h+i,w+j,Cost[h+i][w+j]))
	for i in range(-2,3,1):
		for j in range(-2,3,1):
			# print(i,j)
			if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
				if S[h+i][w+j] == '.':
					if c + 1 < Cost[h+i][w+j]:
						Cost[h+i][w+j] = c + 1
						deq.append((h+i,w+j,Cost[h+i][w+j]))
						# print("updr ", h+i,w+j,Cost[h+i][w+j])

if Cost[DH-1][DW-1] == MAX_COST:
	print(-1)
else:
	print(Cost[DH-1][DW-1])
### BUGGY CODE ###

import networkx as nx

n,m=map(int,input().split())
a=[[tuple(i) for i in input().split()] for _ in range(m)]
g=nx.Graph()
g.add_edges_from(a)
o=1
for i in list(nx.connected_components(g)):
     o=max(o,len(i))
print(o)

### FIXED CODE ###

import networkx as nx
n,m=map(int,input().split())
if m==0:print(1);exit()
a=[[i for i in input().split()] for _ in range(m)]
g=nx.Graph()
for x in a:
     g.add_edge(x[0],x[1])
print(len(sorted(nx.connected_components(g),key=len,reverse=True)[0]))
### BUGGY CODE ###

a,b = map(int,input().split())
now=1
ans=0
while now < b:
  for i in range(21):
    now - 1 + a
    ans+=1
print(ans)

### FIXED CODE ###

a,b = map(int,input().split())
now=1
ans=0
while now < b:
  now = now - 1 + a
  ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())

lis = []
for i in range(N):
    a = int(input())
    if a in lis:
        lis.remove(a)
    else:
        lis.append(a)
    
nsum = len(lis)
print(nsum)


### FIXED CODE ###

import collections

N = int(input())

def mod2(n):
    a = n % 2
    return a

lis = []
for i in range(N):
    a = int(input())
    lis.append(a)

count = collections.Counter(lis)

print(sum(map(mod2, count.values())))
### BUGGY CODE ###

def prime(n):
    prime_lst = []
    num_lst = []
    for i in range(2,n+1):
        if i not in num_lst:
            prime_lst.append(i)
            for j in range(i*i, n+1, i):
                #add all the dividers 
                num_lst.append(j)
        #print(prime_lst)
        #print(num_lst)
    return prime_lst
    
    
Q = int(input())
for i in range(Q):
    x = []
    l,r = map(int,input().split())
    for i in range(l,r+1,2):
        #print(i)
        lst = prime(i)
        if i in lst and (i+1)/2 in lst:
            x.append(i)

    print(len(x))

### FIXED CODE ###

import math
from itertools import accumulate

def is_prime(n):
    if n == 1:
        return 0
    for k in range(2,int(math.sqrt(n))+1):
        if n % k == 0:
            return 0
    return 1
    
Q = int(input())    
L = [0]*Q
R = [0]*Q

for i in range(Q):
    L[i], R[i] = list(map(int, input().split()))

min_L = min(L)
max_R = max(R)

check = []
for i in range(min_L,max_R+ 1):
    if (i%2 ==1):
        flg = (is_prime(i) and is_prime((i+1)/2))
    else:
        flg = 0
    check.append(flg)
    
#print(check)

check = [0] + check
check = list(accumulate(check))
#print(check)
#print(R,L,min_L)

for i in range(Q):
    print(check[R[i]-min_L+1]-check[L[i]-min_L])
### BUGGY CODE ###

a = input()
a_list = list(map(int, input().split()))
ans = 0
checked_list = []

for i in a_list:
    ans = max(ans, a_list.count(i-1) + a_list.count(i) + a_list.count(i+1))
  
print(ans)

### FIXED CODE ###

from collections import Counter
a = input()
a_list = list(map(int, input().split()))
ans = 0
b_list = []
c_list = []

for i in a_list:
    b_list.append(i+1)
    c_list.append(i-1)

ans_list = a_list + b_list + c_list
counter = Counter(ans_list)
print(counter.most_common()[0][1])
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)
import itertools

N,M = map(int,readline().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(int(x) for x in readline().split()))
    C.append(sum(1<<(int(x)-1) for  x in readline().split()))

INF = 10**18
dp = [INF] * (1<<N)
dp[0] = 0

for n,((a,b),c) in itertools.product(range(1<<N),zip(AB,C)):
    m = n|c
    dp[m] = min(dp[m],dp[n]+a)

answer = dp[-1]
if answer == INF:
    answer = -1
print(answer)


### FIXED CODE ###

import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N,M = map(int,readline().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(int(x) for x in readline().split()))
    C.append(sum(1<<(int(x)-1) for  x in readline().split()))

INF = 10**18
dp = [INF] * (1<<N)
dp[0] = 0

for n in range(1<<N):
    for (a,b),c in zip(AB,C):
        m = n|c
        dp[m] = min(dp[m],dp[n]+a)

answer = dp[-1]
if answer == INF:
    answer = -1
print(answer)
### BUGGY CODE ###

from copy import deepcopy

while True:
    m = int(raw_input())
    n = int(raw_input())

    if m == 0 and n == 0:
        break

    begin = [[False] * m for y in xrange(n)]

    for y in xrange(n):
        line = map(int, raw_input().split(' '))
        for x in xrange(m):
            if line[x] == 1:
                begin[y][x] = True

    # (stage, current position(x, y), current point)
    que = []
    for x in xrange(m):
        for y in xrange(n):
            if begin[y][x]:
                stage = deepcopy(begin)
                stage[y][x] = False
                que.append((stage, (x, y), 1))


    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    ans = 0

    while que:
        stage = que.pop()
        for i in xrange(4):
            nx = dx[i] + stage[1][0]
            ny = dy[i] + stage[1][1]
            if 0 <= nx < m and 0 <= ny < n and stage[0][ny][nx]:
                field = deepcopy(stage[0])
                field[ny][nx] = False
                ans = max(ans, stage[2] + 1)
                que.append((field, (nx, ny), stage[2] + 1))

    print ans

### FIXED CODE ###

from copy import deepcopy

while True:

    m = int(raw_input())
    n = int(raw_input())

    if m == 0 and n == 0:
        break

    field = [[False] * m for y in xrange(n)]

    for y in xrange(n):
        line = map(int, raw_input().split(' '))
        for x in xrange(m):
            if line[x] == 1:
                field[y][x] = True

    ans = 0

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    def search(x, y, d):
        global ans

        if d > ans:
            ans = d

        for i in xrange(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < m and 0 <= ny < n and field[ny][nx]:
                field[ny][nx] = False
                search(nx, ny, d + 1)
                field[ny][nx] = True

    for x in xrange(m):
        for y in xrange(n):
            if field[y][x]:
                field[y][x] = False
                search(x, y, 1)
                field[y][x] = True

    print ans
### BUGGY CODE ###

import heapq
import math
n,m = map(int,input().split())
lst = [int(x) * (-1) for x in input().split()]
heapq.heapify(lst)
for i in range(m):
    num = heapq.heappop(lst) * (-1)
    nxt_num = math.floor(num / 2)
    heapq.heappush(lst,nxt_num * -1)
    if sum(lst) == 0:
        break
print(sum(lst) * (-1))

### FIXED CODE ###

import heapq
import math
n,m = map(int,input().split())
lst = [int(x) * (-1) for x in input().split()]
heapq.heapify(lst)
for use_cnt in range(m):
    num = heapq.heappop(lst) * -1
    nxt_num = math.floor(num / 2)
    heapq.heappush(lst,nxt_num * -1)
print(sum(lst) * (-1))
### BUGGY CODE ###

from bisect import bisect
from math import factorial as f

def combi(n_k):
    n, k = n_k
    return f(n) // f(n-k) // f(k)

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

*else_A, max_A = sorted(A)

x = bisect(else_A, max_A//2)

print(*max([(max_A, else_A[y]) for y in [x-1, x] if 0 <= y < N-1], key=combi))



### FIXED CODE ###

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

*else_A, max_A = sorted(A)

print(max_A, min(else_A, key=lambda a: abs(max_A/2 - a) ))