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

import sys
from math import sqrt

testcases = [[int(x) for x in line.split()] for line in sys.stdin.readlines()]

for testcase in testcases:
    box, *cakes = testcase
    N = len(cakes)
    INF = box + 1
    dp = [[INF] * N for _ in range(1 << N)]
    dp[(1 << N) - 1][0] = 0
    for state in reversed(range(1 << N)):
        for v in range(N):
            for u in range(N):
                if not (state >> u & 1):
                    dp[state][v] = min(dp[state][v], dp[state | 1 << u][u] + sqrt(pow(cakes[u] + cakes[v], 2) - pow(cakes[u] - cakes[v], 2)))
    print(*dp[0])
    print('OK' if min(dp[0]) <= box else 'NA')

### FIXED CODE ###

import sys
from math import sqrt


def rec(state, v):
    if state == (1 << N) - 1:
        return cakes[v]
    if dp[state][v] != -1:
        return dp[state][v]

    ret = INF
    for u in range(N):
        if state == 0:
            ret = min(ret, rec(1 << u, u) + cakes[u])
        elif not (state >> u & 1):
            ret = min(ret, rec(state | 1 << u, u) + sqrt(pow(cakes[u] + cakes[v], 2) - pow(cakes[u] - cakes[v], 2)))
    dp[state][v] = ret
    return ret


testcases = [[int(x) for x in line.split()] for line in sys.stdin.readlines()]

for testcase in testcases:
    box, *cakes = testcase
    N = len(cakes)
    INF = box + 1
    dp = [[-1] * N for _ in range(1 << N)]
    print('OK' if rec(0, 0) <= box else 'NA')
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
count = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        for k in range(j + 1, n):
            if l[i] < l[j] + l[k] and l[j] < l[i] + l[k] and l[k] < l[i] + l[j]:
                count += 1
print(count)

### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int, input().split()))
l.sort()
count = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        itr = bisect.bisect_left(l, l[i] + l[j])
        count += itr - 1 - j
print(count)
### BUGGY CODE ###

N= int(input())
dp = [-1]*N
cnt =0
for _ in range(N):
    a = int(input())
    for i in range(N):
        if dp[i]<a:
            dp[i]=a
            cnt = max(cnt,i)
            break
print(cnt+1)


### FIXED CODE ###

import bisect
N= int(input())
dp = [-1]*N
cnt =0
for _ in range(N):
    a = int(input())
    idx = bisect.bisect_left(dp,a)
    dp[idx-1]=a
print(len(dp[bisect.bisect_left(dp,0):]))
### BUGGY CODE ###

import math

n = int(input())
s = [x for x in input()]
mod = 10**9+7

for i in range(n*2):
    if i%2 == 0:
        if s[i] == "B":
            s[i] = "W"
        else:
            s[i] = "B"

cnt_w = 0
cnt_ans = 1

if s.count("B") != s.count("W"):
    print(0)
    exit()
    
for i in range(n*2):
    if s[i] == "W":
        cnt_w += 1
        continue
    if s[i] == "B":
        cnt_ans *= cnt_w
        cnt_w -= 1
    
print((cnt_ans*math.factorial(n))%mod)


### FIXED CODE ###

MOD = 10**9 + 7

N = int(input())
S = input().rstrip()

is_left = [(i%2 == 0) ^ (x == "W") for i, x in enumerate(S)]

answer = 1
left = 0
for bl in is_left:
    if bl:
        left += 1
    else:
        answer *= left
        left -= 1
        answer %= MOD

if left != 0:
    answer = 0
    
for i in range(1, N+1):
    answer *= i
    answer %= MOD

print(answer)
### BUGGY CODE ###

from collections import defaultdict
import math
N=int(input())

div_dic=defaultdict(int)
def add_fact(x):
  for i in range(1,int(x**0.5)+1):
    if x%i==0:
      div_dic[i]+=1
      if i!=x//i:
        div_dic[x//i]+=1
  return

alist=[]
int_list=[]
for _ in range(N):
  a=input()
  if "." in a:
    seisu,shosu=a.split(".")
    seisu=int(seisu)
    shosu=int(shosu.ljust(9,'0'))
    
    bunshi=10**9*seisu+shosu
    bumbo=10**9
    gcd_bb=math.gcd(bunshi,bumbo)
    bunshi//=gcd_bb
    bumbo//=gcd_bb
    
    if bumbo==1:
      int_list.append(bunshi)
      add_fact(bunshi)
    else:
      alist.append((bunshi,bumbo))
  else:
    seisu=int(a)
    int_list.append(seisu)
    add_fact(seisu)
#print(int_list,alist,div_dic)

num_int=len(int_list)
answer=num_int*(num_int-1)//2
for bunshi,bumbo in alist:
  answer+=div_dic[bumbo]

#shosudoshi
def set_fact(x):
  ret={x}
  for i in range(2,int(x**0.5)+1):
    if x%i==0:
      ret.add(i)
      ret.add(x//i)
  return ret

#print(alist)
div_dic2=defaultdict(int)
for bunshi,bumbo in alist:
  div_set=set_fact(bunshi)  
  for d in div_set:    
    answer+=div_dic2[(bumbo,d)]
    
  for d in div_set:    
    div_dic2[(d,bumbo)]+=1
#print(div_dic2)
  
print(answer)


### FIXED CODE ###

from collections import defaultdict
N=int(input())

def pow25(x):
  f2=f5=0
  while x%2==0:
    x//=2
    f2+=1
  while x%5==0:
    x//=5
    f5+=1
  return f2,f5

pow25_dic=defaultdict(int)
for _ in range(N):
  a=input()
  if "." in a:
    seisu,shosu=a.split(".")
    seisu=int(seisu)
    shosu=int(shosu.ljust(9,'0'))    
    bunshi=10**9*seisu+shosu
  else:
    bunshi=10**9*int(a)
    
  pow25_dic[pow25(bunshi)]+=1
#print(pow25_dic)

pow25_key_list=[]
for key in pow25_dic:
  pow25_key_list.append(key)
#print(pow25_key_list)

answer=0
for i in range(len(pow25_key_list)):
  f2,f5=pow25_key_list[i]
  value=pow25_dic[(f2,f5)]
  if f2>=9 and f5>=9:    
    answer+=value*(value-1)//2
    
  for j in range(i+1,len(pow25_key_list)):
    f2_2,f5_2=pow25_key_list[j]
    if f2+f2_2>=18 and f5+f5_2>=18:
      value2=pow25_dic[(f2_2,f5_2)]
      answer+=value*value2
      
print(answer)
### BUGGY CODE ###

N, K = map(int, input().split())
H = [int(input()) for _ in range(N)]
H = sorted(H)
ans = 10**10
for i in range(N - K + 1):
    ans = min(ans, H[i:i+K][-1] - H[i:i+K][0])
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
H = [int(input()) for _ in range(N)]
H = sorted(H)
ans = 10**10
for i in range(N - K + 1):
    ans = min(ans, H[i+K-1] - H[i])
print(ans)
### BUGGY CODE ###

MOD = 10 ** 9 + 7
S = input()
dp = [0] * 13
dp[0] = 1

for i in range(len(S)):
    cdp = [0] * 13
    tmpS = 0
    if S[i] == '?':
        tmpS = -1
    else:
        tmpS = int(S[i])
    for j in range(10):
        if tmpS != -1 and tmpS != j: continue
        for k in range(13):
            cdp[(k * 10 + j) % 13] += dp[k]
            cdp[(k * 10 + j) % 13] %= MOD

    dp = cdp[:]
print(dp[5])

### FIXED CODE ###

S = input()
INF = 10 ** 9 + 7

dp = [[0 for _ in range(13)] for _ in range(len(S) + 1)]
index = 1
dp[0][0] = 1
for i in range(len(S)):
    c = S[-i - 1]
    if c == '?':
        for j in range(10):
            for k in range(13):
                dp[i + 1][(j * index + k) % 13] += dp[i][k]
                dp[i + 1][(j * index + k) % 13] %= INF
    else:
        c = int(c)
        for k in range(13):
            dp[i + 1][(c * index + k) % 13] += dp[i][k]
            dp[i + 1][(c * index + k) % 13] %= INF
    index *= 10
    index %= 13

print(dp[len(S)][5])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def my_sort(L, p, q):
    C = [[i, -1] for i in range(q - p + 1)]
    if p < q:
        mid = (p + q) // 2
        A = my_sort(L, p, mid)
        B = my_sort(L, mid + 1, q)
        i = 0
        j = 0
        k = 0
        while k < q - p + 1:
            if i >= mid - p + 1:
                C[k] = B[j]
                j += 1
            elif j >= q - mid:
                C[k] = A[i]
                i += 1
            else:
                if A[i][1] <= B[j][1]:
                    C[k] = A[i]
                    i += 1
                else:
                    C[k] = B[j]
                    j += 1
            k += 1
        return C
    else:
        return [L[p]]

n = int(input())
task = []
time_total = [0 for i in range(n)]
for i in range(n):
    task.append([int(i) for i in input().split()])
task = my_sort(task, 0, n - 1)
time_total[0] = task[0][0]
for i in range(n - 1):
    time_total[i + 1] = time_total[i] + task[i + 1][0]
while i < n:
    if time_total[i] > task[i][1]:
        print("No")
        sys.exit()
    i += 1
print("Yes")

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
task = []
time_total = [-1 for i in range(n)]
for i in range(n):
    task.append([int(i) for i in input().split()])
task_sorted = sorted(task, key = lambda x:x[1])
time_total[0] = task_sorted[0][0]
for i in range(n - 1):
    time_total[i + 1] = time_total[i] + task_sorted[i + 1][0]
for i in range(n):
    if time_total[i] > task_sorted[i][1]:
        print("No")
        sys.exit()
print("Yes")
### BUGGY CODE ###

# input
N, K, C = map(int, input().split())
S = input()

# process
def isZero(l):
    return l.count(0) == len(l)

daysL = [0]*(N+1)
daysR = [0]*(N+1)
tR = 1
tL = K
for i in range(N):
    if S[i] == 'o' and isZero(daysL[max(0,i-C+1):i+1]):
        daysL[i+1] = tR
        tR += 1
    else:
        daysL[i+1] = 0

    j = N-i
    if S[j-1] == 'o' and isZero(daysR[j:min(N+1,j+C)]):
        daysR[j-1] = tL
        tL -= 1
    else:
        daysR[j-1] = 0

# output
# print(daysL)
# print(daysR)
if max(daysL) == K:    
    for i in range(N):
        if S[i] == 'o' and daysL[i+1] != 0 and daysL[i+1] == daysR[i]:
            print(i+1)


### FIXED CODE ###

# input
N, K, C = map(int, input().split())
S = input()

# process
l = [i+1 for i in range(N) if S[i] == 'o']
left = [l[0]]
right = [l[-1]]
for i in range(1, len(l)):
    if l[i] > left[-1]+C:
        left.append(l[i])
    if l[-i-1] < right[-1]-C:
        right.append(l[-i-1])

# output
# print(l)
# print(left)
# print(right)
if len(left) == K:
    for i in range(len(left)):
        if left[i] == right[-i-1]:
            print(left[i])
### BUGGY CODE ###

import sys
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
skip=[]

def find_max(b,a):
    idx=-1
    buf=-1
    for i in range(0,n):
        if b[i]<a[i]:
            idx=i
            break
        if b[i]==a[i]:
            continue
        if buf<b[i]:
            buf=b[i]
            idx=i
    return idx

loop=0 
while(1):
    #print(b)
    loop+=1
    idx=find_max(b,a)
    if idx==-1:
        break
    if b[idx]>a[idx]:
        b[idx]-=b[(idx-1)%n]+b[(idx+1)%n]
    elif b[idx]<a[idx]:
        print(-1)
        sys.exit()
print(loop-1)

### FIXED CODE ###

import sys
import heapq

def main():
    n=int(input())
    a=list(map(int,input().split()))
    b=list(map(int,input().split()))

    h=[]
    for i in range(n):
        if b[i]>a[i]:
            heapq.heappush(h,(b[i]*-1,i))

    loop=0
    idx=0
    while(1):
    #print(b)
        if not h:
            break
        buf,idx=heapq.heappop(h)
        buf=-1*buf

        x=(buf-a[idx])//(b[(idx-1)%n]+b[(idx+1)%n])
        buf-=x*(b[(idx-1)%n]+b[(idx+1)%n])
        loop+=x
        b[idx]=buf
        if x==0:
            #print(b)
            print(-1)
            sys.exit()
        elif buf>a[idx]:
            heapq.heappush(h,(buf*-1,idx))

    print(loop)

if __name__ == '__main__':
    main()
### 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]
for e in sys.stdin:
 if'i'==e[0]:
  H+=1;A+=[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.pop()
  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 ###

a,op,b = input().split()

a,b = int(a),int(b)

while True:
	if op == '+':
		print(a+b)
	elif op == '-':
		print(a-b)
	elif op == '*':
		print(a*b)
	elif op == '/':
		print(a/b)
	if op == '?':
		break



### FIXED CODE ###

'''
a,op,b = input().split()

a,b = int(a),int(b)
'''
###############################################################
#whileの中に入れないと同じデータセットでの計算をずっとし続ける#
###############################################################

while True:
	a,op,b = input().split()

	a= int(a)
	b = int(b)

	if op == '+':
		print(a+b)
	elif op == '-':
		print(a-b)
	elif op == '*':
		print(a*b)
	elif op == '/':
		print(a//b)
	elif op == '?':
		break
### BUGGY CODE ###

n,k = map(int, input().split())
h = [0] * n
ans = 0
for i in range(n):
  h[i] = int(input())
h.sort()
for i in range(n-k+1):
  temp = max(h[i:i+k]) - min(h[i:i+k])
  if temp == 0:
    ans = temp
    break
  elif i == 0:
    ans = temp
  elif ans > temp:
    ans = temp
print(ans)

### FIXED CODE ###

n,k = map(int, input().split())
h = [0] * n
ans = []
for i in range(n):
  h[i] = int(input())
h.sort()
for i in range(n-k+1):
  ans.append(h[i+k-1] - h[i])
print(min(ans))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

h,w = map(int, input().split())
board = [[int(j=="#") for j in input()] for i in range(h)]
dxdy = [(0,1),(1,0),(0,-1),(-1,0)]

def dfs(i, j, k, prev):
    if used[i][j] or board[i][j] == prev:
        return
    used[i][j] = 1
    k[board[i][j]] += 1
    for dx, dy in dxdy:
        nx, ny = i+dx, j+dy
        if 0 <= nx < h and 0 <= ny < w and board[nx][ny] != board[i][j]:
            dfs(nx,ny,k,board[i][j])

used = [[0]*w for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if used[i][j]:
            continue
        k = [0]*2
        dfs(i,j,k, -1)
        ans += k[0]*k[1]
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

h,w = map(int, input().split())
board = [[int(j=="#") for j in input()] for i in range(h)]
dxdy = [[0,1], [0,-1], [1,0], [-1,0]]

def dfs(i, j, k, prev):
    if used[i][j] or board[i][j] == prev:
        return
    used[i][j] = 1
    k[board[i][j]] += 1
    for dx, dy in dxdy:
        nx, ny = i+dx, j+dy
        if 0 <= nx < h and 0 <= ny < w and not used[nx][ny] and board[nx][ny] != board[i][j]:
            dfs(nx,ny,k,board[i][j])

used = [[0]*w for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if used[i][j]:
            continue
        k = [0]*2
        dfs(i,j,k, -1)
        ans += k[0]*k[1]
print(ans)
### BUGGY CODE ###

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

a = [i-1 for i in a]

p = 0
b = []
while p not in b:
    b.append(p)
    p = a[p]
avant = b.index(p)
loop_count = len(b) - avant
c = b[avant:]

if k <= avant:
    print(b[k]+1)
else:
    k -= avant
    k %= loop_count
    print(c[k]+1)


### FIXED CODE ###

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

a = [i-1 for i in a]

d = [1]*n
p = 0
b = []
while d[p]:
    b.append(p)
    d[p] = 0
    p = a[p]
avant = b.index(p)
loop_count = len(b) - avant
c = b[avant:]

if k <= avant:
    print(b[k]+1)
else:
    k -= avant
    k %= loop_count
    print(c[k]+1)
### BUGGY CODE ###

S,K=input().split()
K=int(K)
K=min(K,300)
mod=998244353
a=[]
val=0
for i in range(len(S)):
    if S[i]=="0":
        a.append(val)
        val=0
    else:
        val+=1

if val!=0:
    a.append(val)
m=len(a)

dp=[[[0 for i in range(K+1)] for j in range(K+1)] for k in range(m+1)]

for j in range(K+1):
    dp[m][j][j]=1

for i in range(m-1,-1,-1):
    for j in range(K+1):
        for k in range(K+1):
            M=max(k-j,-a[i])
            if M>=0:
                for l in range(max(0,M),K-j+1):
                    dp[i][j][k]+=dp[i+1][j+l][k]
                    dp[i][j][k]%=mod
            else:
                for l in range(max(0,M),K-j+1):
                    dp[i][j][k]+=dp[i+1][j+l][k]
                    dp[i][j][k]%=mod
                for l in range(1,min(K-k,-M)+1):
                    dp[i][j][k]+=dp[i+1][j][k+l]
                    dp[i][j][k]%=mod

print(dp[0][0][0])


### FIXED CODE ###

S,K=input().split()
K=int(K)
K=min(K,300)
mod=998244353
a=[]
val=0
for i in range(len(S)):
    if S[i]=="0":
        a.append(val)
        val=0
    else:
        val+=1

if val!=0:
    a.append(val)
m=len(a)
K=min(sum(a),K)

dp=[[[0 for i in range(K+1)] for j in range(K+1)] for k in range(m+1)]

for j in range(K+1):
    dp[m][j][j]=1

b=[a[i] for i in range(m)]
c=[a[i] for i in range(m)]
for i in range(1,m):
    b[i]+=b[i-1]
b=[0]+b
for i in range(m-2,-1,-1):
    c[i]+=c[i+1]
for i in range(m-1,-1,-1):
    for j in range(K+1):
        for k in range(min(b[i],K)+1):
            M=max(k-j,-a[i])
            dp[i][j][k]=sum(dp[i+1][j+l][k] for l in range(max(0,M),K-j+1))+sum(dp[i+1][j][k+l] for l in range(1,min(K-k,-M)+1))
            dp[i][j][k]%=mod

print(dp[0][0][0])
### BUGGY CODE ###

def gcd(x, y):
    while y > 0:
        tmp = x % y
        x = y
        y = tmp
    return x

def lcm(x, y):
    if x == 0 or y == 0:
        return 0
    else:
        return x // gcd(x, y) * y

def main():
    mod = int(1e9 + 7)
    n = int(input())
    a = list(map(int, input().split()))
    l = 1
    for i in range(n):
        l = lcm(l, a[i])

    ans = 0

    for i in range(n):
        ans += l // a[i]

    ans %= mod

    print(int(ans))

if __name__ == '__main__':
    main()


### FIXED CODE ###

def gcd(x, y):
    while y > 0:
        tmp = x % y
        x = y
        y = tmp
    return x

def lcm(x, y):
    if x == 0 or y == 0:
        return 0
    else:
        return x // gcd(x, y) * y

def main():
    mod = int(1e9 + 7)
    n = int(input())
    a = list(map(int, input().split()))
    l = 1
    for i in range(n):
        l = lcm(l, a[i])

    ans = 0

    for i in range(n):
        ans += l // a[i]

    ans %= mod

    print(int(ans))

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

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

for k in range(N):
    count = [0]*(N+1)
    for i in range(N):
        #print(i)
        if i != k:
            count[A[i]] += 1
    print(int(sum([x*(x-1)/2 for x in count])))

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
count = [0]*(N+1)
for i in range(N):
    count[A[i]] += 1

s = sum([x*(x-1)/2 for x in count])

for k in range(N):
    print(int(s-count[A[k]]+1))
### BUGGY CODE ###

N = int(raw_input())
a = map(int, raw_input().split())

diff = [abs(sum(a[select:])-sum(a[:select])) for select in range(1,N)]
print min(diff)

### FIXED CODE ###

N = int(raw_input())
a = map(int, raw_input().split())

sum1 = a[0]
sum2 = sum(a[1:])
diff = [abs(sum1-sum2)]
for i in range(1,N-1):
  sum1 += a[i]
  sum2 -= a[i]
  diff.append(abs(sum1-sum2))

# diff = [abs(sum(a[select:])-sum(a[:select])) for select in range(1,N)]
print min(diff)
### BUGGY CODE ###

L, R = map(int, input().split())

MOD = 2019
MIN = float('inf')
for i in range(L, R):
    for j in range(i+1, R+1):
        buf = (i*j) % MOD
        MIN = min(buf, MIN)

print(MIN)

### FIXED CODE ###

L, R = map(int, input().split())

MIN = 2018
if R-L > 4039:
    MIN = 0


MOD = 2019
L = L%MOD
R = R%MOD
if L > R:
    L, R = R, L
elif L == R:
    MIN = 0


for i in range(L, R):
    for j in range(i+1, R+1):
        buf = (i*j) % MOD
        #print(i, j)
        MIN = min(buf, MIN)

print(MIN)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
 
N = int(input())
h = list(map(int,input().split()))
 
N -= 1
 
def step(i):
  if i == 0:
    return 0
  elif i == 1:
    return abs(h[1]-h[0])
  elif step(i-1)+abs(h[i-1]-h[i]) <= step(i-2)+abs(h[i-2]-h[i]):
    return step(i-1) + abs(h[i-1]-h[i])
  else:
    return step(i-2) + abs(h[i-2]-h[i])
  
print(step(N))



### FIXED CODE ###

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

dp = [0]*N

dp[0] = 0
dp[1] = abs(h[1]-h[0])

for i in range(2,N):
  dp[i] = min(dp[i-2]+abs(h[i]-h[i-2]),dp[i-1]+abs(h[i]-h[i-1]))

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

import sys
from collections import deque
sys.setrecursionlimit(10**7)
inf=10**7


def BFS():
    color=[["white" for _ in range(w+2)] for _ in range(h+2)]
    D=[[inf for _ in range(w+2)] for _ in range(h+2)]

    queue=deque([])
    for i in range(1,h+1):
        for j in range(1,w+1):
            if A[i][j]=="#":
                queue.append([i,j])
                D[i][j]=0
                color[i][j]="gray"

    cnt=0
    while len(queue)!=0:
        a,b=queue.popleft()
        for c,d in ((1,0),(0,1),(-1,0),(0,-1)):
            X,Y=a+c,b+d
            if A[X][Y]=="." and color[X][Y]=="white":
                color[X][Y]="gray"
                D[X][Y]=D[a][b]+1
                cnt=max(cnt,D[X][Y])
                queue.append([X,Y])
        color[a][b]="black"
    return cnt


h,w=map(int,input().split())
A=[["#"]+list(input())+["#"] for _ in range(h)]
A.insert(0,["#"]*(w+2))
A.append(["#"]*(w+2))
print(BFS())

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**7)
inf=10**7


def BFS():
    color=[["white" for _ in range(w+2)] for _ in range(h+2)]
    D=[[inf for _ in range(w+2)] for _ in range(h+2)]

    queue=deque([])
    for i in range(1,h+1):
        for j in range(1,w+1):
            if A[i][j]=="#":
                queue.append([i,j])
                D[i][j]=0
                color[i][j]="gray"

    cnt=0
    while len(queue)!=0:
        a,b=queue.popleft()
        for c,d in ((1,0),(0,1),(-1,0),(0,-1)):
            X,Y=a+c,b+d
            if A[X][Y]=="." and color[X][Y]=="white":
                color[X][Y]="gray"
                D[X][Y]=D[a][b]+1
                cnt=max(cnt,D[X][Y])
                queue.append([X,Y])
        color[a][b]="black"

    return cnt


h,w=map(int,input().split())
A=[["#"]+list(input())+["#"] for _ in range(h)]
A.insert(0,["#"]*(w+2))
A.append(["#"]*(w+2))
print(BFS())
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
if n == 1:
  print(1)
  exit()
  
chk = set([])
for i in range(n):
  a = int(input())
  chk.add((i,a))
  
from bisect import bisect_left,insort_left
from operator import itemgetter
chk = sorted(list(chk),key=itemgetter(0))
ans = 1

c = []
for j in chk:
  i,a = j
  if i == 0:
    c.append((a,n-i))
  else:
    ind = bisect_left(c,(a,n-i))
    if ind == 0:
      ans += 1
      insort_left(c,(a,n-i))
    else:
      c[ind-1] = (a,n-i)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
if n == 1:
  print(1)
  exit()
  
chk = []
for i in range(n):
  a = int(input())
  chk.append((i,a))
  
from bisect import bisect_left,insort_left
from collections import deque
ans = 1

c = deque([])
for j in chk:
  i,a = j
  if i == 0:
    c.append((a,n-i))
  else:
    ind = bisect_left(c,(a,n-i))
    if ind == 0:
      ans += 1
      c.appendleft((a,n-i))
    else:
      c[ind-1] = (a,n-i)
      
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 1
for i in range(N):
    ans = ans*A[i]
# print(len(str(ans))-1)
if ans<=10**18:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 1
Flag = True
zero_flag = False
for i in range(N):
    if A[i]==0:
        zero_flag = True
        break
for i in range(N):
    ans = ans*A[i]
    if ans > 10**18:
        Flag = False
        break
        
# print(len(str(ans))-1)
if zero_flag:
    print(0)
elif ans<=10**18 or Flag:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

# C
N = int(input())
S = list(input())
S1 = S[:N]
S2 = S[2*N-1:N-1:-1]

dict_1 = dict()

res = 0

for i in range(2**N):
    sb = bin(2**N+i)
    red = "".join([S1[j] for j in range(N) if sb[j+3]=="0"])
    blue = "".join([S1[j] for j in range(N) if sb[j+3]=="1"])
    sss = red+"|"+blue
    if sss not in dict_1.keys():
        dict_1[sss] = 1
    else:
        dict_1[sss] += 1
        
for i in range(2**N):
    sb = bin(2**N+i)
    red = "".join([S2[j] for j in range(N) if sb[j+3]=="0"])
    blue = "".join([S2[j] for j in range(N) if sb[j+3]=="1"])
    sss = red+"|"+blue
    res += dict_1.get(sss, 0)
print(res)

### FIXED CODE ###

# C
N = int(input())
S = list(input())
S1 = S[:N]
S2 = S[2*N-1:N-1:-1]

dict_1 = dict()
q_list = [""]*(2**N)
res = 0

for i in range(2**N):
    sb = bin(2**N+i)[3:]
    red = []
    blue = []
    red2 = []
    blue2 = []
    for j in range(N):
        if sb[j]=="0":
            red.append(S1[j])
            red2.append(S2[j])
        else:
            blue.append(S1[j])
            blue2.append(S2[j])
    sss = "".join(red+["|"]+blue)
    sss2 = "".join(red2+["|"]+blue2)
    if sss not in dict_1.keys():
        dict_1[sss] = 1
    else:
        dict_1[sss] += 1
    q_list[i] = sss2
for q in q_list:
    res += dict_1.get(q, 0)
print(res)