Harryxun/sft_time huggingface dataset:
### 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 
    elif i == b_list[b_i]:
        b_i += 1
        ans *= a_i 
    else:
        ans *= (a_i*b_i - (N * M - i)) 
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 ###

#import numpy as np
import math
from bisect import bisect

N, D, A = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(N)]
xh.sort(key=lambda x: x[0])
x = [i[0] for i in xh]
h = [i[1] for i in xh]
#h_int = np.ceil(h/A)

cnt=0
for i in range(len(x)):
    if h[i]<=0: continue
    h_int =  math.ceil(h[i]/A)
    cnt+=h_int
    r = bisect(x, x[i]+2*D)
    for j in range(i+1, r):
      if j>N-1:break
      h[j] = h[j]-h_int*A

print(int(cnt))

### FIXED CODE ###

#import numpy as np
import math
from bisect import bisect

N, D, A = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(N)]
xh.sort(key=lambda x: x[0])
x = [i[0] for i in xh]
h = [i[1] for i in xh]
#h_int = np.ceil(h/A)

cnt=0
damage=[0]*(N+1)

for i in range(len(x)):
    damage[i] += damage[i-1]
    h[i] -= damage[i]
    if h[i]<=0: continue
    h_int =  math.ceil(h[i]/A)
    cnt+=h_int
    damage[i]+=h_int*A
    r=bisect(x,x[i]+2*D)
    #print(damage[i])
    damage[r]-= A*h_int
    

print(int(cnt))
### BUGGY CODE ###

from collections import deque
import math

def explore(C, D):
    queue = deque([[C[0]-1, C[1]-1]])
    maze_visited[C[0]-1][C[1]-1] = 0
    while queue:
        y, x = queue.popleft()
        mv_cur = maze_visited[y][x]
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            n_x, n_y = x + i, y + j
            if n_x >= 0 and n_y >= 0 and n_x < W and n_y < H:
                mv_n = maze_visited[n_y][n_x]
                if S[n_y][n_x] == '.':
                    if mv_n > mv_cur:
                        maze_visited[n_y][n_x] = mv_cur
                        queue.append([n_y, n_x])
        for i in range(-2, 3):
            for j in range(-2, 3):
                if abs(i) + abs(j) <= 1:
                    continue
                n_x, n_y = x + i, y + j
                if n_x >= 0 and n_y >= 0 and n_x < W and n_y < H:
                    mv_n = maze_visited[n_y][n_x]
                    if S[n_y][n_x] == '.':
                        if mv_n > mv_cur + 1:
                            maze_visited[n_y][n_x] = mv_cur + 1
                            queue.append([n_y, n_x])
    
H, W = list(map(int, input().split()))
C = list(map(int, input().split()))
D = list(map(int, input().split()))

S = [list(input()) for i in range(H)]

maze_visited = [[math.inf] * W for i in range(H)]

explore(C,D)

if maze_visited[D[0] - 1][D[1] - 1] == math.inf:
    print('-1')
else:
    print(maze_visited[D[0] - 1][D[1] - 1])

### FIXED CODE ###

from collections import deque
import math
 
def explore(C, D):
    queue = deque([(C[0]-1, C[1]-1)])
    maze_visited[C[0]-1][C[1]-1] = 0
    while queue:
        y, x = queue.popleft()
        mv_cur = maze_visited[y][x]
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            n_x, n_y = x + i, y + j
            if n_x >= 0 and n_y >= 0 and n_x < W and n_y < H:
                mv_n = maze_visited[n_y][n_x]
                if mv_n > mv_cur:
                    if S[n_y][n_x] == '.':
                        maze_visited[n_y][n_x] = mv_cur
                        queue.appendleft((n_y, n_x))
        for i in range(-2, 3):
            for j in range(-2, 3):
                if abs(i) + abs(j) <= 1:
                    continue
                n_x, n_y = x + i, y + j
                if n_x >= 0 and n_y >= 0 and n_x < W and n_y < H:
                    mv_n = maze_visited[n_y][n_x]
                    if mv_n > mv_cur + 1:
                        if S[n_y][n_x] == '.':
                            maze_visited[n_y][n_x] = mv_cur + 1
                            queue.append((n_y, n_x))
    
H, W = list(map(int, input().split()))
C = list(map(int, input().split()))
D = list(map(int, input().split()))
 
S = [list(input()) for i in range(H)]
 
maze_visited = [[math.inf] * W for i in range(H)]
 
explore(C,D)
 
if maze_visited[D[0] - 1][D[1] - 1] == math.inf:
    print('-1')
else:
    print(maze_visited[D[0] - 1][D[1] - 1])
### BUGGY CODE ###

*D, = open(0)
n, m = map(int, D[0].split())
edges = [list(map(int, it.split())) for it in D[1:]]
edges = sorted(edges, key=lambda x:x[1])

cnt = 0
while len(edges)>0:
    cnt += 1
    new_edges = []
    bridge = edges[0][1]
    for it in edges:
        if it[0]>=bridge:
            new_edges.append(it)
            
    edges = new_edges
print(cnt)

### FIXED CODE ###

*D, = open(0)
n, m = map(int, D[0].split())
edges = [list(map(int, it.split())) for it in D[1:]]
edges = sorted(edges, key=lambda x:x[1])

cnt = 0
while len(edges)>0:
    cnt += 1
    new_edges = []
    bridge = edges[0][1]
    for it in edges:
        if it[0]>=bridge:
            new_edges.append(it)
            
    edges = new_edges
print(cnt)
### BUGGY CODE ###

n = input()
a = input()
q = int(input())
bb = []
cc = []
for i in range(q):
    btmp, ctmp = input().split()
    bb.append(btmp)
    cc.append(ctmp)

for b,c in zip(bb,cc):
    a = a.replace(b,c)
    print(sum([int(j) for j in a.split()])) 


### FIXED CODE ###

n = input()
a = [int(i) for i in input().split()]
q = int(input())
bb = []
cc = []
for i in range(q):
    btmp, ctmp = [int(j) for j in input().split()]
    bb.append(btmp)
    cc.append(ctmp)


amap = {}
for i in a :
    if i not in amap :
        amap[i] = 1
    else:
        amap[i] += 1

atol = sum(a)

for b,c in zip(bb,cc):
    
    if b in amap:
        atol +=  (c - b) * amap[b]
    
        if c in amap :
            amap[c] += amap[b]
        else:
            amap[c] = amap[b]
        
        amap.pop(b)
        
    print(atol)
### BUGGY CODE ###

n,k=map(int,input().split())
A=list(map(int,input().split()))
B=[]
for i in range(n-k+1):
  Sum=0
  for j in range(k):
    Sum+=A[i+j]
  B.append((Sum+k)/2)
print(max(B))

### FIXED CODE ###

n,k=map(int,input().split())
p = [(int(s)+1)/2 for s in input().split()]
l = [sum(p[:k])]
for i in range(n-k):
  l.append(l[i]-p[i]+p[i+k])
print(max(l))
### BUGGY CODE ###

N, M = map(int, input().split())
A_list = []
B_list = []
for i in range(N):
    A, B = map(int, input().split())
    A_list.append(A)
    B_list.append(B)

sorted_A_list = sorted(A_list)
new_sorted_A_list = []
for i in sorted_A_list:
    if i not in new_sorted_A_list:
        new_sorted_A_list.append(i)
    else:
        pass

def counter(x, l=A_list): #リストlに格納されている_xのインデックスを全て取得する
    return [i for i, _x in enumerate(l) if _x == x]


count_list = [0]
count = 0
ans = 0
if N == 1:
    ans = A_list[0] * M
else:
    for i in range(N):
        index_B_list = counter(new_sorted_A_list[i])
        for j in index_B_list: 
            count += B_list[j]
        count_list.append(count)
            
        if count_list[i+1] < M:
            ans += new_sorted_A_list[i] * (count_list[i+1] - count_list[i])
        else:
            ans += new_sorted_A_list[i] * (M - count_list[i])
            break

print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
ab = sorted([list(map(int, input().split())) for _ in range(N)]) #入力する時から気をつける

count = 0
ans = 0
for _ab in ab:
    diff = M - count
    if _ab[1] < diff:
        count += _ab[1]  
        ans += _ab[0] * _ab[1]
    else:
        ans += _ab[0] * diff
        break

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

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

ac_list = []

for i in range(len(s)-1):
    if s[i] == 'A' and s[i+1] == 'C':
        ac_list.append(1)
    else:
        ac_list.append(0)

for i in range(q):
    l, r = map(int, input().split())
    print(sum(ac_list[l-1:r-1]))


### FIXED CODE ###

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

ac_list = [0]

for i in range(0, len(s)-1):
    if s[i] == 'A' and s[i+1] == 'C':
        ac_list.append(ac_list[i]+1)
    else:
        ac_list.append(ac_list[i])

#print(ac_list)

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

from functools import lru_cache

n, k = map(int, input().split())
h = [0] + list(map(int, input().split())) + [0]
INF = 10 ** 18


@lru_cache(maxsize=10**9)
def solve(i, nokori):
    if i == 0:
       return 0
    res = INF
    for j in range(nokori + 1):
        if i - 1 - j < 0:
            break
        diff = max(h[i] - h[i - 1 - j], 0)
        res = min(solve(i - 1 - j, nokori - j) + diff, res)
    return res


print(solve(n + 1, k))

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
INF = 10**18

k = n - k

dp = [[INF]*(k+1) for i in range(n+1)]
dp[0][0] = 0

# i番目のブロックを必ず選ぶ
for i in range(n):
    # すでにj回選んでいる
    for j in range(k):
        if j == 0:
            dp[i+1][j+1] = min(dp[0][j] + h[i], dp[i+1][j+1])
            continue
        #最後に選んだブロックはlast_i番目
        for last_i in range(i):
            if last_i + 1 < j:
                continue
            dp[i+1][j+1] = min(dp[last_i+1][j] + max(h[i] - h[last_i], 0), dp[i+1][j+1])

ans = 10**18
for i in range(n+1):
    ans = min(dp[i][k], ans)

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

import sys

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

H, W, D = lr()
A = [lr() for _ in range(H)]
Q = ir()
grid = [None] * (H*W + 1) # 1-indexed
for i in range(H):
    for j in range(W):
        grid[A[i][j]] = (i, j)

next_D = [0] * (H*W + 1)
for i in range(1, H*W + 1 - D):
    next_D[i] = abs(grid[i+D][0] - grid[i][0]) + abs(grid[i+D][1] - grid[i][1])

for i in range(Q):
    l, r = lr()
    answer = sum(next_D[l:r:D])
    print(answer)

# 49

### FIXED CODE ###

import sys

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

H, W, D = lr()
A = [lr() for _ in range(H)]
Q = ir()
grid = [None] * (H*W + 1) # 1-indexed
for i in range(H):
    for j in range(W):
        grid[A[i][j]] = (i, j)

next_D = [0] * (H*W + 1)
for i in range(1+D, H*W + 1):
    next_D[i] = abs(grid[i][0] - grid[i-D][0]) + abs(grid[i][1] - grid[i-D][1])
    next_D[i] += next_D[i-D]

for i in range(Q):
    l, r = lr()
    answer = next_D[r] - next_D[l]
    print(answer)

# 49
### BUGGY CODE ###

from collections import Counter
from operator import mul
from functools import reduce
from math import factorial


def solve(s):
    n, m = map(int, s.split())
    if m == 1:
        return 1
    divisor = []
    for i in range(2, int(m**0.5) + 1):
        if m % i == 0:
            divisor.append(i)
    divisor += [m // d for d in divisor[::-1]] + [m]
    divisor = sorted(list(set(divisor)))
    ld = len(divisor)

    def search(ded, use, j):
        if ded == 1:
            # print("{} {} {}".format(ded, use, j))
            count = Counter(use)
            base = reduce(mul, range(n - len(use) + 1, n + 1))
            for v in list(count.values()):
                base //= factorial(v)
            # print(base)
            return base
        if len(use) >= n:
            return 0

        tmp = [
            search(ded // divisor[i], use + [divisor[i]], i)
            for i in range(j, ld)
            if ded % divisor[i] == 0
        ]
        return sum(tmp) if tmp else 0

    return search(m, [], 0) % (10**9 + 7)


print(solve(input()))


### FIXED CODE ###

import math

# import time


def get_primes(n):
    primes = []
    checks = [True for _ in range(int(math.sqrt(n)) + 1)]
    checks[0] = checks[1] = False
    for i in range(2, len(checks)):
        if checks[i]:
            primes.append(i)
            tmp = 0
            while i + tmp * i < len(checks):
                checks[i + tmp * i] = False
                tmp += 1
    return primes


def combination(a, b):
    i = 1
    for _i in range(a - b + 1, a + 1):
        i *= _i
    return i // math.factorial(b)


n, m = map(int, input().split())
# start = time.time()
primes = get_primes(m)
elems = []
m_copy = m
divides = dict()
for _p in primes:
    while m_copy % _p == 0:
        m_copy = m_copy // _p
        if str(_p) in divides.keys():
            divides[str(_p)] += 1
        else:
            divides[str(_p)] = 1
if m_copy > 1:
    divides[str(m_copy)] = 1
# print(primes)

# print(time.time() - start)
ans = 1
for i in divides.values():
    ans *= combination(i + n - 1, i)
print(ans % (1000000007))
# print(time.time() - start)
### BUGGY CODE ###

import bisect

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

ans = 0
while(len(A) > 0):
    a = A.pop()
    b = (1 << a.bit_length()) - a
    i = bisect.bisect_left(A, b)
    if i < len(A) and A[i] == b:
        ans += 1
        A.pop(i)

print(ans)

### FIXED CODE ###

from collections import Counter

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
c = Counter(A)

ans = 0
for a in A:
    b = (1 << a.bit_length()) - a
    if a == b and c[a] > 1:
        c[a] -= 2
        ans += 1
    elif a != b and c[a] > 0 and c[b] > 0:
        c[a] -= 1
        c[b] -= 1
        ans += 1

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

import numpy as np
#import math
N, K = map(int, input().split())
A = np.array(sorted(list(map(int, input().split()))))
F = np.array(sorted(list(map(int, input().split())), reverse=True))



left = - 1
right = 10**12

def f(x):
    return sum(np.maximum(0, A - x//F)) <= K

while right - left > 1:
    mid = (left + right)//2
    if f(mid):
        right = mid
    else:
        left = mid
    
print(right)

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
A = np.array(sorted(list(map(int, input().split()))))
F = np.array(sorted(list(map(int, input().split())), reverse=True))

left = - 1
right = 10**12

def f(x):
    return np.maximum(0, A - x//F) .sum()<= K

while right - left > 1:
    mid = (left + right)//2
    if f(mid):
        right = mid
    else:
        left = mid
    
print(right)
### BUGGY CODE ###

from fractions import gcd
k=int(input())
ans=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for l in range(1,k+1):
        a=(i,j,l)
        if len(a)==1:
            ans=ans+i
        elif len(a)==2:
            ans=ans+gcd(a[0],a[1])
        else:
            ans=ans+gcd(a[0],gcd(a[1],a[2]))
print(ans)


### FIXED CODE ###

from math import gcd
k=int(input())
ans=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for l in range(1,k+1):
      ans=ans+gcd(gcd(i,j),l)
print(ans)
### BUGGY CODE ###

N, Y = map(int, input().split())

for i in range(Y // 10000 + 1):
    for j in range(Y // 5000 + 1):
        k = (Y - i*10000 - j*5000) // 1000
        if (Y - i*10000 - j*5000) % 1000 == 0 and i+j+k == N and k>=0:
            print(i, j, k)
            exit()
        else:
            pass
                
print(-1, -1, -1)

### FIXED CODE ###

N, Y = map(int, input().split())

for i in range(Y // 10000 + 1):
    for j in range((Y - i*10000) // 5000 + 1):
        remain_money = (Y - i*10000 - j*5000)
        k = remain_money // 1000
        if remain_money % 1000 == 0 and i+j+k == N:
            print(i, j, k)
            exit()
        else:
            pass
                
print(-1, -1, -1)
### BUGGY CODE ###

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

dp = [0]*n 

for i in range(1,n):
    temp = dp[i-1]+abs(h[i]-h[i-1])
    for j in range(2,k+1):
        if i-j>=0:
            temp = min(dp[i-j]+abs(h[i]-h[i-j]), temp)
    
    dp[i] = temp
    
print(dp[-1])

### FIXED CODE ###

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

dp = [0]*n 

for i in range(1,n):
    dp[i] = dp[i-1]+abs(h[i]-h[i-1])
    for j in range(2,k+1):
        if i-j>=0:
            dp[i] = min(dp[i-j]+abs(h[i]-h[i-j]), dp[i])
    
print(dp[-1])
### BUGGY CODE ###


import itertools
n = int(input())
a = list(map(int, input().split(" ")))

ans = 0
for i, j in itertools.combinations(range(n), 2):
    ans += (a[i] * a[j]) % (10**9+7)

print(ans % (10**9 + 7))

### FIXED CODE ###

import itertools
x = 10**9 + 7
n = int(input())
a = list(map(lambda i: i % x , map(int, input().split(" "))))
sum_a = []
prev = 0
for i in a:
    sum_a.append(prev + i)
    prev = prev + i

ans = 0
for i in range(n):
    ans += (a[i] * (sum_a[n-1] - sum_a[i] )) % x
print(ans % x)
### BUGGY CODE ###

N, M = map(int, input().split())
key = []
for _ in range(M):
  a, b = map(int, input().split())
  s = 0
  C = list(map(lambda x:int(x)-1, input().split()))
  for c in C:
    s |= 1<<c
  key += [(s, a)]
  
dp = [float('inf')]*(1<<N)
dp[0] = 0
for s in range(1<<N):
  for i in range(M):
    t = s | key[i][0] # 遷移先
    cost = dp[s] + key[i][1]
    dp[t] = min(dp[t], cost)
if dp[-1] == float('inf'):
  print(-1)
else:
  print(dp[-1])






### FIXED CODE ###

N, M = map(int, input().split())
key = []
for _ in range(M):
  a, b = map(int, input().split())
  s = 0
  C = list(map(lambda x:int(x)-1, input().split()))
  for c in C:
    s |= 1<<c
  key += [(s, a)]
  
dp = [float('inf')]*(1<<N)
dp[0] = 0
for s in range(1<<N):
  for i in range(M):
    t = s | key[i][0] # 遷移先
    cost = dp[s] + key[i][1]
    dp[t] = min(dp[t], cost)
if dp[-1] == float('inf'):
  print(-1)
else:
  print(dp[-1])
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort()
ans=1
for i in range(N):
    ans=ans*A[i]
if ans>pow(10,18):
    ans='-1'
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort()
if A[0]!=0:
    ans=1
    for i in range(N):
        ans=ans*A[i]
        if ans>pow(10,18):
            ans='-1'
            break
else:
    ans=0
print(ans)
### BUGGY CODE ###

import numpy as np
N, M, K = list(map(int, input().split()))
mod = 998244353
d = np.zeros(K+2)
d[1] = M
for _ in range(N-1):
    d[1:] = (d[:-1] + d[1:] * (M-1)) % mod
print(int(sum(d) % mod))

### FIXED CODE ###

N, M, K = list(map(int, input().split()))
mod = 998244353

c = 1
answer = 0

for i in range(K+1):
    answer += (M * c  * pow(M-1, N - i - 1, mod)) % mod
    answer %= mod
    c = (c * (N-i-1) * pow(i+1, mod-2, mod)) % mod
    
print(answer)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
from operator import itemgetter
from collections import deque
from collections import Counter
import math
import pprint
from functools import reduce
# stdin = open("sample.txt")

def keta(kazu):
    kazu_str = str(kazu)
    kazu_list = [int(kazu_str[i]) for i in range(0, len(kazu_str))]
    return kazu_list

def gcd(*numbers):
    return reduce(math.gcd, numbers)

N = int(stdin.readline().rstrip())
A = list(map(int,[int(x) for x in stdin.readline().rstrip().split()]))
attack = 0
menber = 0

while attack < N and menber < N:
    attack += 1
    ans = A.count(attack)
    print(ans)
    menber += ans
    
if attack < N:
    print('0\n'*(N-attack))

### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
from operator import itemgetter
from collections import deque
from collections import Counter
import math
import pprint
from functools import reduce
# stdin = open("sample.txt")

def keta(kazu):
    kazu_str = str(kazu)
    kazu_list = [int(kazu_str[i]) for i in range(0, len(kazu_str))]
    return kazu_list

def gcd(*numbers):
    return reduce(math.gcd, numbers)

N = int(stdin.readline().rstrip())
A = list(map(int,[int(x) for x in stdin.readline().rstrip().split()]))

A_ = Counter(A)

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

N, M = map(int, input().split())
A = []
for i in range(M):
	curr = int(input())
	A.append(curr)

mod = 1000000007

ans = [0] * (N + 1)

ans[0] = 1

for i in range(len(ans)):
	if i in A:
		continue
	ans[i] %= mod
	if(i+1 < len(ans) and i+1 not in A):
		ans[i+1] += ans[i]
	if(i+2 < len(ans) and i+2 not in A):
		ans[i+2] += ans[i]

print(ans[N])

### FIXED CODE ###

N, M = map(int, input().split())
A = []
for i in range(M):
	curr = int(input())
	A.append(curr)

mod = 1000000007

ans = [0] * (N + 1)

ans[0] = 1

for a in A:
	ans[a] = -1

for i in range(len(ans)):
	if ans[i] == -1:
		continue
	if(i+1 < len(ans) and ans[i+1] != -1):
		ans[i+1] += ans[i]
		ans[i+1] %= mod
	if(i+2 < len(ans) and ans[i+2] != -1):
		ans[i+2] += ans[i]
		ans[i+2] %=mod

print(ans[N])
### BUGGY CODE ###

from collections import deque
def main():
    h,w=map(int,input().split())
    hw=h*w
    maze=[]
    r_append=maze.append
    for i in range(h):
        #r_append=maze.append
        #row=input()
        r_append(input())
    #print(maze)
    #root=[[-1 for i in range(h*w)] for i in range(h*w)]
    root=[0]*(hw)
    ina=[0]*hw
    for i in range(hw):
        root[i]=[-1]*(hw)
        ina[i]=[i]
    
    for i in range(h):
        for j in range(w):
        # print(maze[i][j])
            now=w*i+j
            hidari=w*i+j-1
            migi=w*i+j+1
            ue=w*(i-1)+j
            sita=w*(i+1)+j
            if maze[i][j]==".":
                if j>0:
                    if maze[i][j-1]!="#":
                        root[now][hidari]=0
                if i+1<h:
                    if maze[i+1][j]!="#":
                        root[now][sita]=0
                if j+1<w:
                    if maze[i][j+1]!="#":
                        root[now][migi]=0
                if 0<i:
                    if maze[i-1][j]!="#":
                        root[now][ue]=0
            else:
                ina[now]=-1
                if j>0:
                    root[now][hidari]=-1
                if i+1<h:
                    root[now][sita]=-1
                if j+1<w:
                    root[now][migi]=-1
                if 0<i:
                    root[now][ue]=-1
    #print(root)
    max=0
    
    for start in range(hw):
        if ina[start]==-1:
           # print(start,"is unreachable")
            continue
        dist=[0]*(hw)
        now=start
        dist[start]=0
        visted=[0]*(hw)
        toVis=deque()
        tv_append=toVis.append
        visted[now]=1
        for i in range(hw):
            if root[now][i]!=-1:
                tv_append(i)
                dist[i]=dist[now]+1
        while len(toVis)>0:
            now=toVis.popleft()
            visted[now]=1
            le=dist[now]
            for i in range(hw):
                if root[now][i]!=-1 and visted[i]!=1:
                    tv_append(i)
                    dist[i]=le+1
        farest=dist[now]
        if max<farest:
            max=farest
    print(max)
            
if __name__=="__main__":
    main()


    

### FIXED CODE ###

h,w=map(int,input().split())
n=h*w
inf=10**6
field=[]
for i in range(h):
    field.append(input())
dist=[[inf]*n for i in range(n)]
for i in range(h):
    for j in range(w):
        if field[i][j]=="#":continue
        if j+1<w and field[i][j+1]!="#":
            dist[i*w+j][i*w+j+1]=1
            dist[i*w+j+1][i*w+j]=1
        if i+1<h and field[i+1][j]!="#":
            dist[i*w+j][(i+1)*w+j]=1
            dist[(i+1)*w+j][i*w+j]=1
for i in range(n):
    for j in range(n):
        for k in range(n):
            dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k])
ans=0
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        if dist[i][j]==inf:
            continue
        ans=max(ans,dist[i][j])
print(ans)