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

from collections import Counter
n = int(input())
a = list(map(int,input().split()))
c = Counter(a)
c1,c2,c3 = c[1],c[2],c[3]
dp = [[[0 for i in range(c3+1)] for j in range(c2+c3+1)] for k in range(c1+c2+c3+1)]
#dp[i][j][k] := 1個×i皿、2個×j皿、3個×k皿における期待値
for k in range(c3+1):
  for j in range(c2+c3+1):
    for i in range(n+1):
      if i+j+k > n or i == j == k == 0:
        continue
      x = (n-i-j-k)/n
      dp[i][j][k] = 1
      if 0<i :
        dp[i][j][k] += dp[i-1][j][k]*(i/n)
      if 0<j and i+1<=n:
        dp[i][j][k] += dp[i+1][j-1][k]*(j/n)
      if 0<k and j+1<=c2+c3:
        dp[i][j][k] += dp[i][j+1][k-1]*(k/n)
      dp[i][j][k] /= 1-x
print(dp[c1][c2][c3])

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))
c = Counter(a)
c1,c2,c3 = c[1],c[2],c[3]
dp = [[[0 for i in range(c3+1)] for j in range(c2+c3+1)] for k in range(c1+c2+c3+1)]
#dp[i][j][k] := 1個×i皿、2個×j皿、3個×k皿における期待値
for k in range(c3+1):
  for j in range(c2+c3+1):
    for i in range(n+1):
      if i+j+k > n or i == j == k == 0:
        continue
      x = (n-i-j-k)/n
      dp[i][j][k] = 1
      if 0<i :
        dp[i][j][k] += dp[i-1][j][k]*(i/n)
      if 0<j and i+1<=n:
        dp[i][j][k] += dp[i+1][j-1][k]*(j/n)
      if 0<k and j+1<=c2+c3:
        dp[i][j][k] += dp[i][j+1][k-1]*(k/n)
      dp[i][j][k] /= 1-x
print(dp[c1][c2][c3])
### BUGGY CODE ###


from collections import defaultdict
import sys
sys.setrecursionlimit(100000)

N, M = map(int, input().rstrip().split(' '))

A = [0] * (N + 1)
for _ in range(M):
    A[int(input())] = 1

dp = defaultdict(lambda: -1)
def dfs(n):
    if n > N:
        return 0
    if A[n] == 1:
        return 0
    if n == N:
        return 1
    if dp[n] != -1:
        return dp[n]
        
    count = 0
    count += dfs(n + 1)
    count += dfs(n + 2)
    
    dp[n] = count
    
    return count
    
print(dfs(0) % (1000000007))

### FIXED CODE ###

# coding: utf-8
# Your code here!

from collections import defaultdict

N, M = map(int, input().rstrip().split(' '))
if M == 0:
    A = [0]
else:
    A = sorted([int(input()) for _ in range(M)]) + [N + 1]
    
dp = [0] * (N+1)
dp[0] = 1
if A[0] != 1:
    dp[1] = 1
    index_A = 0
else:
    dp[1] = -1
    index_A = 1
    
for i in range(2,N+1):
    if A[index_A] == i:
        dp[i] = -1
        index_A += 1
    else:
        if dp[i-1] != -1:
            dp[i] += dp[i-1]
        if dp[i-2] != -1:
            dp[i] += dp[i-2]
            
print(dp[N] %  (1000000007))
### BUGGY CODE ###

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

N=int(input())
M=N*(N-1)//2
D=[[]for i in range(M)]
F=[[]for i in range(M)]
for i in range(N):
  x=list(map(int,input().split()))
  for j in range(N-2):
    a,b,c=i+1,x[j],x[j+1]
    x1,x2=min(i+1,x[j]),max(i+1,x[j])
    y1,y2=min(i+1,x[j+1]),max(i+1,x[j+1])
    e=M-(N-x1)*(N-x1+1)//2
    f=e+(x2-x1-1)
    g=M-(N-y1)*(N-y1+1)//2
    h=g+(y2-y1-1)
    D[f].append(h)
    F[h].append(f)
P=[-1]*M
ans=0
def bfs(u):
  P[u]=0
  B.append(u)
  queue=deque([u])
  while queue:
    v=queue.popleft()    
    for i in D[v]:
      if i in B:
        ans==-1
        break
      if P[v]+1>P[i]:
        P[v]+1>P[i]
        P[i]=P[v]+1
        queue.append(i)
for i in range(M):
  B=[]
  if len(F[i])==0:
    bfs(i)
  if ans==-1:
    print(-1)
    exit()
if min(P)==-1:
  print(-1)
else:
  print(max(P)+1)

### FIXED CODE ###

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

N=int(input())
M=N*(N-1)//2
D=[[]for i in range(M)]
F=[[]for i in range(M)]
for i in range(N):
  x=list(map(int,input().split()))
  for j in range(N-2):
    a,b,c=i+1,x[j],x[j+1]
    x1,x2=min(i+1,x[j]),max(i+1,x[j])
    y1,y2=min(i+1,x[j+1]),max(i+1,x[j+1])
    e=M-(N-x1)*(N-x1+1)//2
    f=e+(x2-x1-1)
    g=M-(N-y1)*(N-y1+1)//2
    h=g+(y2-y1-1)
    D[f].append(h)
    F[h].append(f)
    
q=deque()
P=[0]*M
for i in range(M):
  if len(F[i])==0:
    q.append((i,0))

r=[]
while q:
  v1,cnt=q.popleft()
  r.append((v1,cnt))
  for v2 in D[v1]:
    P[v2]+=1
    if P[v2]==len(F[v2]):
      q.append((v2,cnt+1))

if len(r)!=M:
  print(-1)
else:
  print(r[-1][-1]+1)
### BUGGY CODE ###

n = int(input())
lis = []
for i in range(n):
    a,b =map(int,input().split())
    lis.append([a-b,a+b])
lis.sort(key = lambda x:x[1])
dp = {(-2 * 10 ** 9,0)}
for aa,bb in lis:
    now = set()
    for nowa,ans in dp:
        if nowa <= aa:
            now.add((bb,ans+1))
        now.add((nowa,ans))
    dp = now
an = 0
for aaa,ans in dp:
    an = max(an,ans)
print(an)

### FIXED CODE ###

n = int(input())
lis = []
for i in range(n):
    a,b =map(int,input().split())
    lis.append([a-b,a+b])
lis.sort(key = lambda x:x[1])
ans = 0
now = -10 ** 10
for a,b in lis:
    if now <= a:
        ans += 1
        now = b
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]*N

for i in range(1,N):
    dp[i] = min(dp[j] + abs(h[i] - h[j]) for j in range(max(i - K, 0), i))

print(dp[-1])


### FIXED CODE ###

def solve():
  N, K = [int(i) for i in input().split()]
  H = [int(i) for i in input().split()]
  dp = [0] * N
 
  for i in range(1, N):
    dp[i] = min(dp[j] + abs(H[i] - H[j]) for j in range(max(i - K, 0), i))
 
  return dp[N - 1]
 
print(solve())
### BUGGY CODE ###

if __name__ == '__main__':
    n= int(input())
    s = [int(i) for i in input().split(" ")]
    dict = {}
    for i in s:
        if i in dict:
            dict[i] = dict[i]+1
        else:
            dict[i] = 1
    sum = 0
    for i in dict.values():
        if i > 1:
            sum = sum + (i-1)*i//2
    ans = ""

    for i in s:
        num = sum
        if i in dict :
            num = num -dict[i] +1
        if ans =="":
            ans = str(num)
        else:
            ans = ans + " " + str(num)
        print(num)


### FIXED CODE ###

if __name__ == '__main__':
    n= int(input())
    s = [int(i) for i in input().split(" ")]
    dict = {}
    for i in s:
        if i in dict:
            dict[i] = dict[i]+1
        else:
            dict[i] = 1
    sum = 0
    for i in dict.values():
        if i > 1:
            sum = sum + (i-1)*i//2

    for i in s:
        num = sum
        if i in dict :
            num = num -dict[i] +1
        print(num)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from itertools import combinations

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

xl = []
yl = []
xy = []
for _ in range(n):
    x,y = map(int, input().split())
    xl.append(x)
    yl.append(y)
    xy.append((x,y))

res = None
for cx in combinations(xl, 2):
    for cy in combinations(yl, 2):
        x1,x2 = cx
        y1,y2 = cy

        if x2>x1:
            x1,x2 = x2,x1
        if y2>y1:
            y1,y2 = y2,y1

        cnt = 0
        for cc in xy:
            x,y = cc
            if x1>=x>=x2 and y1>=y>=y2:
                cnt += 1
            if cnt>=k:
                break
        if cnt>=k:
            s = (x1-x2)*(y1-y2)
            if res is None:
                res = s
            else:
                res = min(res, s)

print(res)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import combinations

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

xl = []
yl = []
xy = []
for _ in range(n):
    x,y = map(int, input().split())
    xl.append(x)
    yl.append(y)
    xy.append((x,y))
yl.sort()
xy.sort(key=lambda x:x[1])

res = None
for cx in combinations(xl, 2):
    x1,x2 = cx
    if x2>x1:
        x1,x2 = x2,x1

    for y2 in yl:
        cnt = 0
        for c in xy:
            x,y = c
            if x1>=x>=x2 and y>=y2:
                cnt += 1

            if cnt==k:
                y1 = y
                s = (x1-x2)*(y1-y2)
                if res is None:
                    res = s
                else:
                    res = min(res, s)
                break

print(res)
### BUGGY CODE ###

def run():
    n = int(input())
    nodes = []
    for _ in range(n):
        order = [o.strip() for o in input().split()]
        if order[0] == 'insert':
            nodes.append(int(order[1]))
        elif order[0] == 'delete':
            nodes.reverse()
            if int(order[1]) in nodes:
                nodes.remove(int(order[1]))
            nodes.reverse()
        elif order[0] == 'deleteFirst':
            nodes.pop()
        elif order[0] == 'deleteLast':
            nodes.pop(0)
    nodes.reverse()
    print(' '.join([str(n) for n in nodes]))
    
if __name__ == '__main__':
    run()




### FIXED CODE ###

from collections import deque

def run():
    n = int(input())
    dq = deque()
    for _ in range(n):
        order = input()
        if order[0] == 'i':
            dq.appendleft(order[7:])
        elif order[6] == ' ':
            key = order.split()[1]
            if not key in dq:
                continue
            for i in range(len(dq)):
                if dq[i] == key:
                    dq.remove(key)
                    break
        elif order[6] == 'F':
            dq.popleft()
        elif order[6] == 'L':
            dq.pop()

    print(' '.join(dq))

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

n,C=map(int,input().split())
d=[]
c=[]
ans=float("inf")
for i in range(C):
    d.append(list(map(int,input().split())))
for i in range(n):
    c.append(list(map(int,input().split())))
for i in range(1,C+1):
    for j in range(1,C+1):
        if i==j:
            continue
        for k in range(1,C+1):
            if k==i or k==j:
                continue
            t=0
            for ii in range(n):
                for jj in range(n):
                    z=(ii+jj+2)%3
                    if z==0:
                        t+=d[c[ii][jj]-1][i-1]
                    elif z==1:
                        t+=d[c[ii][jj]-1][j-1]
                    elif z==2:
                        t+=d[c[ii][jj]-1][k-1]
            if t<ans:
                ans=t
print(ans)

### FIXED CODE ###

N,C = map(int,input().split())
d = [list(map(int,input().split())) for _ in range(C)]
g0 = [0]*C
g1 = [0]*C
g2 = [0]*C
for i in range(N):
    col = list(map(int,input().split()))
    for j in range(N):
        col[j] -= 1
        if (i+j)%3==0:
            g0[col[j]] += 1
        elif (i+j)%3 ==1:
            g1[col[j]] += 1
        else:
            g2[col[j]] += 1
ans = float('inf')
for i in range(C):
    for j in range(C): 
        for k in range(C):
            if i==j or j==k or i==k:
                continue
            s=0
            for l in range(C):
                s += d[l][i]*g0[l] + d[l][j]*g1[l] + d[l][k]*g2[l]
            ans = min(ans,s)
print(ans)
### BUGGY CODE ###

N = int(input())
sum=0

while N > 0:
    sum += N % 10
    N //= 10

if sum % 9 == 0:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

N = int(input())

if sum(list(map(int, str(N)))) % 9 ==0:
    print('Yes')
else:print('No')
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

N,mod=map(int,input().split())
EDGE=[list(map(int,input().split())) for i in range(N-1)]

#N=10**5
#mod=10**8
#import random
#EDGE=[[i,random.randint(1,i-1)] for i in range(2,N+1)]

EDGELIST=[[] for i in range(N+1)]
DPDICT=dict()

for x,y in EDGE:
    EDGELIST[x].append(y)
    EDGELIST[y].append(x)

for i in range(1,N+1):
    if len(EDGELIST)==1:
        DPDICT[(i,EDGELIST[i][0])]=2    


def SCORE(point):
    ANS=1
    for to in EDGELIST[point]:
        ANS=ANS*dp(to,point)%mod
    return ANS

def dp(x,y):
    if DPDICT.get((x,y))!=None:
        return DPDICT[(x,y)]

    ANS=1
    for to in EDGELIST[x]:
        if to==y:
            continue
        ANS=ANS*dp(to,x)%mod

    DPDICT[(x,y)]=ANS+1
    return ANS+1

for i in range(1,N+1):
    print(SCORE(i))

### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

N,mod=map(int,input().split())
EDGE=[list(map(int,input().split())) for i in range(N-1)]

if N==1:
    print(1)
    sys.exit()

EDGELIST=[[] for i in range(N+1)]
for x,y in EDGE:
    EDGELIST[x].append(y)
    EDGELIST[y].append(x)

SCORELIST=[[-1]*len(EDGELIST[i]) for i in range(N+1)]
PRODLIST=[[-1]*len(EDGELIST[i]) for i in range(N+1)]
PRODLIST_rev=[[-1]*len(EDGELIST[i]) for i in range(N+1)]
EDICT=dict()

for i in range(1,N+1):
    for j in range(len(EDGELIST[i])):
        EDICT[(i,EDGELIST[i][j])]=j

def dp(x,y):
    if SCORELIST[y][EDICT[(y,x)]]!=-1:
        return SCORELIST[y][EDICT[(y,x)]]

    ANS=1
    for to in EDGELIST[x]:
        if to==y:
            continue
        ANS=ANS*dp(to,x)%mod

    SCORELIST[y][EDICT[(y,x)]]=ANS+1   
    return ANS+1

def dp2(x,y):
    if PRODLIST[x][0]==-1:
        PRODLIST[x][0]=(SCORELIST[x][0])%mod
        for i in range(1,len(EDGELIST[x])):
            PRODLIST[x][i]=PRODLIST[x][i-1]*SCORELIST[x][i]%mod

        PRODLIST_rev[x][-1]=SCORELIST[x][-1]
        for i in range(len(EDGELIST[x])-2,-1,-1):
            PRODLIST_rev[x][i]=PRODLIST_rev[x][i+1]*SCORELIST[x][i]%mod

    if len(EDGELIST[x])==1:
        ANS=1
    elif EDICT[(x,y)]==0:
        ANS=PRODLIST_rev[x][1]
    elif EDICT[(x,y)]==len(EDGELIST[x])-1:
        ANS=PRODLIST[x][EDICT[(x,y)]-1]
    else:
        ANS=PRODLIST[x][EDICT[(x,y)]-1]*PRODLIST_rev[x][EDICT[(x,y)]+1]%mod

    SCORELIST[y][EDICT[(y,x)]]=ANS+1

for to in EDGELIST[1]:
    dp(to,1)

QUE=deque([1])
check=[0]*(N+1)

while QUE:
    x=QUE.pop()
    if check[x]==1:
        continue
    for to in EDGELIST[x]:
        if check[x]==0 or check[to]==0:
            dp2(x,to)
            QUE.append(to)
    check[x]=1

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

s=input()
n=len(s)
c=[0 for i in range(n)]
d=[0 for i in range(n)]
bc=[0 for i in range(n)]
bd=[0 for i in range(n)]
dc=[0 for i in range(n)]
dd=[0 for i in range(n)]
if s[-1]=="C":
    c[-1]=1
if s[-1]=="?":
    d[-1]=1
for i in range(-2,-n-1,-1):
    c[i]=c[i+1]
    d[i]=d[i+1]
    bc[i]=bc[i+1]
    bd[i]=bd[i+1]
    dc[i]=dc[i+1]
    dd[i]=dd[i+1]
    if s[i]=="B":
        bc[i]+=c[i+1]
        bd[i]+=d[i+1]
    if s[i]=="C":
        c[i]+=1
    if s[i]=="?":
        d[i]+=1
        dc[i]+=c[i+1]
        dd[i]+=d[i+1]
mul=3**d[0]
res=0
for i in range(n-2):
    if s[i]=="A":
        res+=bc[i+1]*mul+(dc[i+1]+bd[i+1])*(mul//3)+dd[i+1]*(mul//9)
    if s[i]=="?":
        res+=bc[i+1]*(mul//3)+(dc[i+1]+bd[i+1])*(mul//9)+dd[i+1]*(mul//27)
    res%=1000000007
print(res)


### FIXED CODE ###

s=input()
n=len(s)
c=[0 for i in range(n)]
d=[0 for i in range(n)]
bc=[0 for i in range(n)]
bd=[0 for i in range(n)]
dc=[0 for i in range(n)]
dd=[0 for i in range(n)]
if s[-1]=="C":
    c[-1]=1
if s[-1]=="?":
    d[-1]=1
for i in range(-2,-n-1,-1):
    c[i]=c[i+1]
    d[i]=d[i+1]
    bc[i]=bc[i+1]
    bd[i]=bd[i+1]
    dc[i]=dc[i+1]
    dd[i]=dd[i+1]
    if s[i]=="B":
        bc[i]+=c[i+1]
        bd[i]+=d[i+1]
    if s[i]=="C":
        c[i]+=1
    if s[i]=="?":
        d[i]+=1
        dc[i]+=c[i+1]
        dd[i]+=d[i+1]
mul=[1,1,1,1]
for i in range(d[0]):
    mul[3]*=3
    mul[3]%=1000000007
for i in range(2,-1,-1):
    if mul[i+1]%3==0:
        mul[i]=mul[i+1]//3
    elif mul[i+1]%3==1:
        mul[i]=(mul[i+1]+1000000007)//3
    else:
        mul[i]=(mul[i+1]+2000000014)//3
res=0
for i in range(n-2):
    if s[i]=="A":
        res+=bc[i+1]*mul[3]+(dc[i+1]+bd[i+1])*mul[2]+dd[i+1]*mul[1]
    if s[i]=="?":
        res+=bc[i+1]*mul[2]+(dc[i+1]+bd[i+1])*mul[1]+dd[i+1]*mul[0]
    res%=1000000007
print(res)
### BUGGY CODE ###

import fractions
import math

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

res = 0
tmp = math.ceil(m/n)
for i in range(1, tmp+1):
    res = (max(res, fractions.gcd(i, m-((n-1)*i))))
print(res)


### FIXED CODE ###

import math

n, m = map(int, input().split())
array = []
for i in range(1, int(math.sqrt(m)+1)):
    if m % i == 0:
        array.append([i, m//i])

diff = float("inf")
res = 0
for i, j in array:
    if i >= n:
        res = max(res, j)
    if j >= n:
        res = max(res, i)
print(res)
### BUGGY CODE ###

import random

def is_prime(q,k=50):
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

n,m=(int(i) for i in input().split(' '))
for i in range(1,n):
  if m%i==0 and is_prime(i) and is_prime(m//i) and (i==1 or m//i<n):
    print('1')
    exit()
for i in range(n,m+1):
  if i==m:
    print(1)
    break
  if m%i==0:
    print(m//i)
    break


### FIXED CODE ###

import random

def is_prime(q,k=50):
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

n,m=(int(i) for i in input().split(' '))
for i in range(1,n):
  if m%i==0 and (is_prime(i) or i==1) and is_prime(m//i) and (i==1 or m//i<n):
    print('1')
    exit()
for i in range(n,m+1):
  if i==m:
    print(1)
    break
  if m%i==0:
    print(m//i)
    break
  if m-i-n>0 and m%(m-i-n)==0 and m//(m-i-n)>n:
    print(m-i-n)
    break
### BUGGY CODE ###

a,b,q=[int(it) for it in input().split()]
dummy=10**20
s=[-dummy] + [int(input()) for it in range(a)] + [dummy]
t=[-dummy] + [int(input()) for it in range(b)] + [dummy]
x=[int(input()) for it in range(q)]

for xi in x:
    s_w = [it for it in s if it < xi][-1]
    s_e = [it for it in s if it > xi][0]
    t_w = [it for it in t if it < xi][-1]
    t_e = [it for it in t if it > xi][0]

    d = min(
        abs(xi - s_w) + abs(s_w - t_w),
        abs(xi - s_e) + abs(s_e - t_w),
        abs(xi - s_w) + abs(s_w - t_e),
        abs(xi - s_e) + abs(s_e - t_e),
        abs(xi - t_w) + abs(t_w - s_w),
        abs(xi - t_e) + abs(t_e - s_w),
        abs(xi - t_w) + abs(t_w - s_e),
        abs(xi - t_e) + abs(t_e - s_e)
    )
    print(d)


### FIXED CODE ###

import bisect

a,b,q=[int(it) for it in input().split()]
dummy=10**20
s=[-dummy] + [int(input()) for it in range(a)] + [dummy]
t=[-dummy] + [int(input()) for it in range(b)] + [dummy]
x=[int(input()) for it in range(q)]

for xi in x:
    s_w = s[bisect.bisect_left(s, xi)-1]
    s_e = s[bisect.bisect_left(s, xi)]
    t_w = t[bisect.bisect_left(t, xi)-1]
    t_e = t[bisect.bisect_left(t, xi)]

    d = min(
        abs(xi - s_w) + abs(s_w - t_w),
        abs(xi - s_e) + abs(s_e - t_w),
        abs(xi - s_w) + abs(s_w - t_e),
        abs(xi - s_e) + abs(s_e - t_e),
        abs(xi - t_w) + abs(t_w - s_w),
        abs(xi - t_e) + abs(t_e - s_w),
        abs(xi - t_w) + abs(t_w - s_e),
        abs(xi - t_e) + abs(t_e - s_e)
    )
    print(d)
### BUGGY CODE ###

import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))


v=[[1,0],[-1,0],[0,1],[0,-1]]
h,w=mp()
grid=["#"*(w+2)]
ans=[]
for i in range(h):
    grid.append("#"+input()+"#")
grid.append("#"*(w+2))
for i in range(h*w-1):
    for j in range(i+1,h*w):
        if grid[i//w+1][i%w+1]=="." and grid[j//w+1][j%w+1]==".":
            sx,sy,gx,gy=i//w+1,i%w+1,j//w+1,j%w+1
            que=deque([[sx,sy,0]])
            while len(que):
                q=que.popleft()
                if q[0]==gx and q[1]==gy:
                    ans.append(q[2])
                    break
                for x,y in v:
                    if grid[q[0]+x][q[1]+y]==".":
                        que.append([q[0]+x,q[1]+y,q[2]+1])
print(max(ans))

### FIXED CODE ###

import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))


v=[[1,0],[-1,0],[0,1],[0,-1]]
h,w=mp()
grid=["#"*(w+2)]
ans=[]
for i in range(h):
    grid.append("#"+input()+"#")
grid.append("#"*(w+2))
for i in range(h*w):
    ch=[[0]*(w+2) for i in range(h+2)]
    if grid[i//w+1][i%w+1]==".":
        sx,sy=i//w+1,i%w+1
        que=deque([[sx,sy,0]])
        while len(que):
            q=que.popleft()
            ch[q[0]][q[1]]=1
            ans.append(q[2])
            for x,y in v:
                if grid[q[0]+x][q[1]+y]=="." and ch[q[0]+x][q[1]+y]==0:
                    ch[q[0]+x][q[1]+y]=1
                    que.append([q[0]+x,q[1]+y,q[2]+1])
            
print(max(ans))
### BUGGY CODE ###

import heapq

N, K = map(int, input().split())
sushi = []
for i in range(N):
    t, d = map(int, input().split())
    heapq.heappush(sushi, (-d, t))

total = 0
types = []
remain = []
for i in range(K):
    d, t = heapq.heappop(sushi)
    total -= d
    if t not in types:
        types.append(t)
    else:
        # 余りの寿司はremainにappend
        heapq.heappush(remain, -d)

types_len = len(types)
ans = total + types_len ** 2

while sushi and remain:
    d, t = heapq.heappop(sushi)
    if t not in types:
        types.append(t)
        remain_d = heapq.heappop(remain)
        total = total - d - remain_d
        types_len += 1
        ans = max(ans, total + types_len ** 2)

print(ans)


### FIXED CODE ###

import heapq

N, K = map(int, input().split())
sushi = []
for i in range(N):
    t, d = map(int, input().split())
    heapq.heappush(sushi, (-d, t))

total = 0
types = set()
remain = []
for i in range(K):
    d, t = heapq.heappop(sushi)
    total -= d
    if t not in types:
        types.add(t)
    else:
        # 余りの寿司はremainにappend
        heapq.heappush(remain, -d)

types_len = len(types)
ans = total + types_len ** 2

while sushi and remain:
    d, t = heapq.heappop(sushi)
    if t not in types:
        types.add(t)
        remain_d = heapq.heappop(remain)
        total = total - d - remain_d
        types_len += 1
        ans = max(ans, total + types_len ** 2)

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

N=int(input())
S = [input() for i in range(N)]
S.sort()
max_count=0
ans=[]
for s in S:
	max_count= max(max_count, S.count(s))
for s in set(S):
	if S.count(s)==max_count:
		ans.append(s)
ans.sort()
for a in ans:
	print(a)


### FIXED CODE ###

N=int(input())
dict={}
for i in range(N):
	s = input()
	if s in dict:dict[s]+=1
	else:dict[s]=1
max_count = max(dict.values())
for k,v in sorted(dict.items()):
	if v==max_count:print(k)
### BUGGY CODE ###

S = input()
Q = int(input())
R = 1
for _ in range(Q):
  inp = input()
  if inp[0]=='1':
    R *= -1
  else:
    o, f, c = inp.split()
    if f=='1' and R==-1 or f=='2' and R==1:
      S = S+c
    else:
      S = c+S
print(S) if R==1 else print(S[::-1])

### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())
R = 1
Top = deque()
Top.append(S)
for _ in range(Q):
  inp = input()
  if inp[0]=='1':
    R *= -1
  else:
    o, f, c = inp.split()
    if f=='1' and R==-1 or f=='2' and R==1:
      Top.append(c)
    else:
      Top.appendleft(c)
S = ''.join(Top)
S = S if R==1 else S[::-1]
print(S)
### BUGGY CODE ###

class RollingHash():
    def __init__(self,s):
        self.n=n=len(s)
        self.b=b=129
        self.M=M=2**61-1
        x,y=1,0
        self.f=f=[x]*(n+1)
        self.h=h=[y]*(n+1)
        for i,c in enumerate(s.encode()):
            f[i+1]=x=x*b%M
            h[i+1]=y=(y*b+c)%M
    def get(self,l,r):
        return(self.h[r]-self.h[l]*self.f[r-l])%self.M
def main():
    n=int(input())
    s=RollingHash(input())
    for i in range(1,n):
        d={}
        for j in range(0,n-i+1):
            k=s.get(j,j+i)
            if k in d:
                if d[k]+i<=j:
                    break
            else:
                d[k]=j
        else:
            print(i-1)
            break
main()

### FIXED CODE ###

from subprocess import*
with open('e.cpp','w')as f:f.write(r"""
#include<iostream>
using namespace std;
main(){
  int n;
  string s;
  cin>>n>>s;
  int a=0;
  for(int i=0;i<n;++i){
    int t=0;
    for(int j=0;j<n-i;++j){
      t=(t+1)*(s[j]==s[j+i]);
      a=max(a,min(t,i));
    }
  }
  cout<<a;
}""")
call(('g++','e.cpp'))
call('./a.out')