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

charseq = raw_input()
start = -1
end = -1

for i in xrange(len(charseq)):
    for j in xrange(i+2, len(charseq)+1):
        part = charseq[i:j]
        chars = list(part)
        counter = {}  
        for char in chars:
            counter[char] = counter.get(char, 0)+1
        for key in counter.keys():
            if counter[key] > (j-i)/2:
                start = i+1 
                end = j 
                break
        if not start == -1: 
            break
    
print start, end 
    


### FIXED CODE ###

charseq = raw_input()
start = -1
end = -1

for i in range(len(charseq)-1):
    if charseq[i] == charseq[i+1]:
        start = i+1 
        end = i+2 
        break
if start == -1: 
    for i in range(len(charseq)-2):
        if charseq[i] == charseq[i+2]:
            start = i+1 
            end = i+3 
            break

print start, end
### BUGGY CODE ###

import heapq  # heapqライブラリのimport
X,Y,Z,K=map(int,input().split())
A= list(map(int,input().split()))
B= list(map(int,input().split()))
C= list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
check=[[0,0,0]]
lst =[(-(A[0]+B[0]+C[0]),0,0,0)]
heapq.heapify(lst)
for r in range(K):
 a=lst[0][1]
 b=lst[0][2]
 c=lst[0][3] 
 print(lst[0][0]*(-1))
 heapq.heappop(lst)
 if a<X-1 :
  if [a+1,b,c] not in check:
   heapq.heappush(lst, (-(A[a+1]+B[b]+C[c]),a+1,b,c))
   check.append([a+1,b,c])
 if b<Y-1 :
  if [a,b+1,c] not in check:
   heapq.heappush(lst, (-(A[a]+B[b+1]+C[c]),a,b+1,c))
   check.append([a,b+1,c])
 if c<Z-1 :
  if [a,b,c+1] not in check:
   heapq.heappush(lst, (-(A[a]+B[b]+C[c+1]),a,b,c+1))
   check.append([a,b,c+1])

### FIXED CODE ###

X,Y,Z,K=map(int,input().split())
A= list(map(int,input().split()))
B= list(map(int,input().split()))
C= list(map(int,input().split()))
AB=[0]*(X*Y)
t=0
for i in A:
 for j in B:
  AB[t]=i+j
  t+=1
AB.sort(reverse=True)
ABA=AB[0:min(K,X*Y)]
D=[0]*(Z*len(ABA))
t=0
for i in ABA:
 for j in C:
  D[t]=i+j
  t+=1
D.sort(reverse=True)
for i in range(K):
 print(D[i])
### BUGGY CODE ###

a,b,c,d,e,f = map(int,input().split())
x=[]
for i in range(int(f)):
    for j in range(int(f)):
        if (100*a*i+100*b*j)<= f:
            x.append(100*a*i+100*b*j)
y=[]
for i in range(int(f)):
    for j in range(int(f)):
        if (c*i+d*j)<= f:
            y.append(c*i+d*j)
p=e/(100+e)
maxp=0
mj=0
mi=0
for i in x:
    for j in y:
        if((i+j<=f) and (i+j)>0 and (j/(i+j)<=p)):
            if(j/(i+j)>=maxp):
                mj=j
                mi=i
                maxp=j/(i+j)
print(str(mj+mi)+" "+str(mj))

### FIXED CODE ###

a,b,c,d,e,f = map(int,input().split())
x=[]
for i in range(int(f/100+0.9)):
    for j in range(int(f/100+0.9)):
        if (100*a*i+100*b*j)<= f:
            x.append(100*a*i+100*b*j)
y=[]
for i in range(int(f/c+0.9)):
    for j in range(int(f/d+0.9)):
        if (c*i+d*j)<= f:
            y.append(c*i+d*j)
p=e/(100+e)
maxp=0
mj=0
mi=0
for i in x:
    for j in y:
        if((i+j<=f) and (i+j)>0 and (j/(i+j)<=p)):
            if(j/(i+j)>=maxp):
                mj=j
                mi=i
                maxp=j/(i+j)
print(str(mj+mi)+" "+str(mj))
### BUGGY CODE ###

import math
import functools
import copy

N=int(input())
a=list(map(int,input().split()))
b=copy.copy(a)
ans=list()

for i in range(N):
  del b[i]
  gcd=functools.reduce(math.gcd,b)
  ans.append(gcd)
  b.insert(i,a[i])

print(max(ans))

### FIXED CODE ###

import math
from itertools import accumulate

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

fromleft = list(accumulate(a, math.gcd))
fromright = list(accumulate(a[::-1], math.gcd))[::-1]

gcd = []

gcd.append(fromright[1])
for i in range(1, n-1):
    gcd.append(math.gcd(fromleft[i-1], fromright[i+1]))
gcd.append(fromleft[n-2])

print(max(gcd))
### BUGGY CODE ###

s = input()
k = int(input())
t = sorted(list(s))
num = []
while len(num) < k:
    a = t.pop(0)
    indexes = [i for i, x in enumerate(s) if x == a]
    z = 0
    while z < len(indexes):
        i = indexes[z]
        q = 1
        while i + q <= len(s):
            if s[i:i + q] not in num:
                num.append(s[i:i + q])
            q += 1
        z += 1

num = sorted(num)
print(num[k - 1])

### FIXED CODE ###

s = input()
k = int(input())
t = sorted(list(s))
num = []
while len(num) < k:
    a = t.pop(0)
    indexes = [i for i, x in enumerate(s) if x == a]
    z = 0
    while z < len(indexes):
        i = indexes[z]
        q = 1
        while q <= 5:
            if s[i:i + q] not in num:
                num.append(s[i:i + q])
            q += 1
        z += 1

num = sorted(num)
print(num[k - 1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Oct  7 22:06:12 2018
ABC073D
@author: maezawa
"""
import itertools as itr
import sys
input = sys.stdin.readline

n, m, r = list(map(int, input().split()))
rarray = list(map(int, input().split()))
adjmatrix = [[float("inf")]*n for _ in range(n)]
#for i in range(n):
#    adjmatrix[i][i] = 0

for i in range(m):
    a, b, c = list(map(int, input().split()))
    adjmatrix[a-1][b-1] = c
    adjmatrix[b-1][a-1] = c

#print(abc)

# Warshall-Floyd Algorithm
for k in range(len(adjmatrix)):
    for i in range(len(adjmatrix)):
        for j in range(len(adjmatrix[i])):
            if adjmatrix[i][j] > adjmatrix[i][k] + adjmatrix[k][j]:
                adjmatrix[i][j] = adjmatrix[i][k] + adjmatrix[k][j]
                adjmatrix[j][i] = adjmatrix[i][k] + adjmatrix[k][j]				

        
#print(*adjmatrix, sep='\n')
    
# search for ri to rj
mincnt = float("inf")
for route in itr.permutations(rarray):
    cnt = 0
    for i in range(len(rarray)-1):
        cnt += adjmatrix[route[i]-1][route[i+1]-1]
    if cnt < mincnt:
        mincnt = cnt

print(mincnt)
        
        

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Mon Oct  8 10:17:39 2018

@author: maezawa
"""

import math
from itertools import permutations

#フロイド・ワーシャル
def warshall_floyd(glath):
	
	for k in range(len(glath)):
		for i in range(len(glath)):
			for j in range(len(glath[i])):
				if glath[i][j] > glath[i][k] + glath[k][j]:
                                   glath[i][j] = glath[i][k] + glath[k][j]
                                   glath[j][i] = glath[i][k] + glath[k][j]				
	return glath

N, M ,R= [int(x) for x in str(input()).split()]  #グラフの大きさ 
r=[int(x) for x in str(input()).split()]
graph=[[float("inf")]*N for i in range(N)]


for i in range(M):
	a,b,c=[int(x) for x in str(input()).split()]
	#if a in r and b in r:
	graph[a-1][b-1]=c
	graph[b-1][a-1]=c

#all_cost=warshall_floyd(select_graph)
all_cost=warshall_floyd(graph)


max_count=float("inf")
for i in permutations(r):
        cost=0
        for j in range(len(i)-1):                
                cost+= all_cost[i[j]-1][i[j+1]-1]       
        max_count=min(max_count,cost)

print(max_count)
### BUGGY CODE ###

import numpy as np

N = int(input())
A = list(map(int, input().split()))
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

#K = int(input())
#S = input()

##一次元配列の初期化
#a=[0]*5
#[i for i in range(100) if i%2==1] #奇数のみ
##二次元配列の初期化
mod = np.array([[-1 for i in range(N)] for i in range(N)])

count = 0
for i in range(N):
        mod[i] = np.mod(A,A[i])
for i in range(N):
    c = list(mod[:,i]).count(0)
    if c == 1:
        count += 1
        
print(count)

### FIXED CODE ###

#import numpy as np

N = int(input())
A = list(map(int, input().split()))
A.sort()#わるほう

#kouho = sorted([x for x in set(A) if A.count(x) == 1])
#maxA = 10**5

#target = kouho[:]
maxA = A[-1]
work=[0]*(A[-1]+1)

for i in range(len(A)):
    if work[A[i]]<=1:
        maxN = int(maxA/A[i])
        for n in range(1,maxN+1):
            buf = A[i]*n
            #remove_list.append(buf)
            work[buf]+=1
                #print(A[i]*n)

#target = kouho[:]
#kouho = list(set(kouho) - set(remove_list))

sm=0
for s in A:
    if work[s]==1: sm+=1
print(sm)

#print(len(kouho))
### BUGGY CODE ###

import numpy as np

n,k,q=map(int,input().split())
a=np.ones(n)*k
for i in range(q):
	b=int(input())
	a=a-1
	a[b-1]+=1
	
for j in range(n):
	if a[j]>0:
		print('Yes')
	else:
		print('No')

### FIXED CODE ###

import numpy as np

n,k,q=map(int,input().split())
a=np.ones(n)*k - q
for i in range(q):
	b=int(input())
	a[b-1]+=1
b=a>0

for j in range(n):
	if b[j]:
		print('Yes')
	else:
		print('No')
### BUGGY CODE ###

N,K = input().split()
N = int(N)
K = int(K)

H = input().split()
H = [int(s) for s in H]
H.sort(reverse=True)

if N < K:
  print(0)
else:
  for i in range(0,K):
    H.pop(0)

  sumdata = 0
  for i in range(0,len(H)):
    sumdata += H[i]
  print(sumdata)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,K = input().split()
N = int(N)
K = int(K)

H = input().split()
H = [int(s) for s in H]
H.sort(reverse=True)

if N < K:
  print(0)
else:
  for i in range(0,K):
    H[i] = 0

  sumdata = 0
  for i in range(0,len(H)):
    sumdata += H[i]
  print(sumdata)
### BUGGY CODE ###

import sys
from collections import deque

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

graph = {}
count = 1
for value in input().split():
    graph[count] = int(value)
    count += 1

queue = deque()
queue.append(1)
now_pos = 1
start = 0

for i in range(N + 1):
    next_pos = graph[now_pos]
    if not next_pos in queue:
        queue.append(next_pos)
        now_pos = next_pos

    # 循環した
    else:
        start = next_pos
        break

if K <= N:
    print(queue[K])
    sys.exit()

before_len = queue.index(start)
roop = len(queue) - before_len

print(queue[before_len + (K - before_len) % roop])


### FIXED CODE ###

import sys
import time

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

queue = {}

start = -1
count = 1

now_town = 1

for i in range(K):
    if town_list[now_town - 1] in queue:
        start = town_list[now_town - 1]
        break
    queue[town_list[now_town - 1]] = count
    now_town = town_list[now_town - 1]
    count += 1

if start == -1:
    print(now_town)
    sys.exit()

roop = len(queue) - (queue[start] - 1)
before_len = queue[start]

print(list(queue.keys())[(K - before_len) % roop + before_len - 1])
### BUGGY CODE ###

n,k=map(int,input().split())
l=[input().split() for _ in range(n)]
ans=0
for a in range(0,k):
     for b in range(0,k):
         i=0
         total=0
         while i<n:
           m=(((int(l[i][0])-a)//k)+((int(l[i][1])-b)//k))%2
           if (m==0 and str(l[i][2])=="W") or (m==1 and str(l[i][2])=="B"):
               total=total+1
               i=i+1
           else:
               i=i+1

         else:
              ans=max(ans,total,n-total)
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
imos = [[0 for i in range(k)] for j in range(k)]
white = 0
for i in range(n):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    if c == "W":
        c = 1
    else:
        c = 0
    x %= 2*k
    y %= 2*k

    if x > k-1:
        x -= k
        c += 1
    if y > k-1:
        y -=k
        c += 1
    c %= 2

    if c == 1:
        white += 1
        imos[x][y] -= 1
    else:
        imos[x][y] += 1

for i in range(k):
    for j in range(k-1):
        imos[i][j+1] += imos[i][j]

for j in range(k):
    for i in range(k-1):
        imos[i+1][j] += imos[i][j]

ans = 0
for i in range(k):
    for j in range(k):
        exp = imos[k-1][k-1] - imos[k-1][j] - imos[i][k-1] + 2 * imos[i][j] + white
        ans = max(ans, max(exp, n - exp))

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

n,k = map(int,input().split())
p = list(map(int,input().split()))
ans = 0
d = [0]
for i in p:
  d.append(d[-1]+i)
t = 0
max_i = 0
for i in range(n-k+1):
  if d[i+k]-d[i] > t:
    t = d[i+k]-d[i]
    max_i = i
ans = sum([sum(range(i+1))/i for i in p[max_i:max_i+k]])
print(ans)



### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
p_ = [(i+1)/2 for i in p]
d = [0]
for i in p_:
  d.append(d[-1]+i)
ans = 0
for i in range(k,n+1):
  if ans < d[i]-d[i-k]:
    ans = d[i]-d[i-k]
print(ans)
### BUGGY CODE ###

n,k=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
mark=[0]*(n-k+1)
m=[1]*(k+1)
for i in range(k):
  m[i+1]=a[i]*m[i]
mark[0]=m[k]
for j in range(1,n-k+1):
  mark[j]=(mark[j-1]/a[j-1])*a[j+k-1]
for j in range(n-k):
  if mark[j]<mark[j+1]:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

n,k=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
for i in range(n-k):
  if a[i]<a[i+k]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
l_li=[]
r_li=[]
for i in range(q):
    l,r=map(int,input().split())
    l_li.append(l)
    r_li.append(r)
    
dp =[[0 for i in range(n)] for j in range(n)]

for j in range(n):
    if s[j]=="C" and j!=0 and s[j-1]=="A":
        dp[0][j]=dp[0][j-1]+1
    else:
        dp[0][j]=dp[0][j-1]

for i in range(1,n):
    if s[i]=="C" and s[i-1]=="A":   
        dp[i][i:n]=list(map(lambda x: x-1,dp[i-1][i:n]))
    else:
        dp[i][i:n]=dp[i-1][i:n]       
        
        
for i in range(q):
    print(dp[l_li[i]-1][r_li[i]-1])


### FIXED CODE ###

n,q=map(int,input().split())
s=input()
    
dp =[0 for j in range(n)]


for j in range(n):
    t=0
    if s[j]=="C" and j!=0:
        if s[j-1]=="A":
            t=1

    dp[j]=dp[j-1]+t
        

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

str = input()
a = str.split(" ")
n = (int)(a[0])
k = (int)(a[1])
str = input();
for ii in range(k-1):
  s = str + str[::-1]
  s1 = s[0:n]
  for i in range(1,n+1):
    s2 = s[i:n+i]
    if(s1>s2):
      s1 = s2
  str = s1[::-1]

s = str + str[::-1]
s1 = s[0:n]
for i in range(1,n+1):
  s2 = s[i:n+i]
  if(s1>s2):
    s1 = s2
print(s1)

### FIXED CODE ###

str = input()
a = str.split(" ")
n = (int)(a[0])
k = (int)(a[1])
str = input()
before = ""
for ii in range(k-1):
  s = str + str[::-1]
  s1 = s[0:n]
  for i in range(1,n+1):
    s2 = s[i:n+i]
    if(s1>s2):
      s1 = s2
  str = s1[::-1]
  if(before==str):
    break
  before = str

s = str + str[::-1]
s1 = s[0:n]
for i in range(1,n+1):
  s2 = s[i:n+i]
  if(s1>s2):
    s1 = s2
print(s1)
### BUGGY CODE ###

from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

### FIXED CODE ###

from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [input() for _ in range(H)]

    Q = deque([[Ch - 1, Cw - 1, 0]])  # 座標とワープ回数

    cost = [[-1 for _ in range(W)] for _ in range(H)]  # ワープ回数を記録

    while Q:
        r, c, cnt = Q.popleft()

        if cost[r][c] != -1:  # 訪れたことがある
            continue

        cost[r][c] = cnt

        for dr in range(-2, 3):
            for dc in range(-2, 3):
                nr = r + dr
                nc = c + dc

                if 0 <= nr < H and 0 <= nc < W and S[nr][nc] == ".":
                    if abs(dr) + abs(dc) == 1:  # 上下左右
                        Q.appendleft([nr, nc, cnt])
                    elif abs(dr) + abs(dc) >= 2:  # ワープ
                        Q.append([nr, nc, cnt + 1])

    print(cost[Dh - 1][Dw - 1])


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

# -*- coding: utf-8 -*-

H,W,K = map(int, input().split())
x1,y1,x2,y2 = map(int, input().split())

C = [input() for _ in range(H)]
T = [[-1 for _ in range(W)] for _ in range(H)]
T[x1-1][y1-1] = 0

que = [(x1-1,y1-1)]
step = 1

while len(que)>0:
  que_next = []
  for q in que:
    x,y = q[0],q[1]
    for i in range(1,K+1):
      if x-i<0:
        break
      if C[x-i][y]=='@' or T[x-i][y]==1:
        break
      if x-i==x2-1 and y==y2-1:
        print(step)
        exit()
      que_next.append((x-i,y))
    for i in range(1,K+1):
      if x+i>H-1:
        break
      if C[x+i][y]=='@' or T[x+i][y]==1:
        break
      if x+i==x2-1 and y==y2-1:
        print(step)
        exit()
      que_next.append((x+i,y))
    for i in range(1,K+1):
      if y-i<0:
        break
      if C[x][y-i]=='@' or T[x][y-i]==1:
        break
      if x==x2-1 and y-i==y2-1:
        print(step)
        exit()
      que_next.append((x,y-i))
    for i in range(1,K+1):
      if y+i>W-1:
        break
      if C[x][y+i]=='@' or T[x][y+i]==1:
        break
      if x==x2-1 and y+i==y2-1:
        print(step)
        exit()
      que_next.append((x,y+i))
  que = que_next
  for q in que:
    T[q[0]][q[1]] = 1
  step += 1

print(-1)

### FIXED CODE ###

# -*- coding: utf-8 -*-

H,W,K = map(int, input().split())
x1,y1,x2,y2 = map(int, input().split())

C = [input() for _ in range(H)]
T = [[-1 for _ in range(W)] for _ in range(H)]
T[x1-1][y1-1] = 0

que = {(x1-1,y1-1):0}
step = 1

while len(que)>0:
  que_next = {}
  for q in que.keys():
    x,y = q[0],q[1]
    for i in range(1,K+1):
      if x-i<0:
        break
      if C[x-i][y]=='@' or T[x-i][y]==1:
        break
      if x-i==x2-1 and y==y2-1:
        print(step)
        exit()
      que_next[(x-i,y)] = 0
    for i in range(1,K+1):
      if x+i>H-1:
        break
      if C[x+i][y]=='@' or T[x+i][y]==1:
        break
      if x+i==x2-1 and y==y2-1:
        print(step)
        exit()
      que_next[(x+i,y)] = 0
    for i in range(1,K+1):
      if y-i<0:
        break
      if C[x][y-i]=='@' or T[x][y-i]==1:
        break
      if x==x2-1 and y-i==y2-1:
        print(step)
        exit()
      que_next[(x,y-i)] = 0
    for i in range(1,K+1):
      if y+i>W-1:
        break
      if C[x][y+i]=='@' or T[x][y+i]==1:
        break
      if x==x2-1 and y+i==y2-1:
        print(step)
        exit()
      que_next[(x,y+i)] = 0
  que = que_next
  for q in que.keys():
    T[q[0]][q[1]] = 1
  step += 1

print(-1)
### BUGGY CODE ###

n, m = map(int, input().split())
ans = 1
if m % n == 0:
    print(m // n)
    exit()
for i in range(1, m // 2 + 1):
    if m % i == 0:
        if m // i >= n:
            ans = i
        else:
            break
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
ans = 1
for i in range(1, int(m ** .5) + 1):
    if m % i == 0:
        b = m // i
        if i * n <= m:
            ans = max(ans, i)
        if b * n <= m:
            ans = max(ans, b)
print(ans)
### BUGGY CODE ###

#2問目
N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [float("inf")] * N
dp[0] = 0;
for i in range(1, N):
    for j in range(max(i-K, 0), i):
        dp[i] = min(dp[i], abs(h[j] - h[i]) + dp[j])
print(dp[N-1])

### FIXED CODE ###

NK = input().split()
N,K = int(NK[0]), int(NK[1])
A = list(map(int, input().split()))
#コストの配列 全部無限にしておく
cost = [float("inf") for _ in range(N)]
cost[0] = 0

for i in range(N-1):
    if(i + K >= N):
        K = N-1-i
    for j in range(1, K+1):
        cost[i + j] = min(cost[i + j], cost[i] + abs(A[i+j] - A[i]))
print(cost[N-1])
### BUGGY CODE ###

import numpy as np
h, w = map(int, input().split())

M = h + w
blck = [M] * (w + 2)
data = [blck]
for ln in range(1, h+1):
    line = list(input().rstrip())
    lineN = [0] * (w+2)
    lineN[0] = lineN[-1]= M
    for r, letter in zip(range(1, w+1), line):
        if letter == '.':
            lineN[r] = M
    data.append(lineN)
data.append(blck)

data = np.array(data)

for d in range(1, -2, -2):
    if d == 1:
        cur, curW, addS, addE, mov= [[1, 1], [h+1, w+1], [0, 1], [1, 0], [1, -1]]
    else:
        cur, curW, addS, addE, mov= [[h, w], [0, 0], [0, -1], [-1, 0], [-1, 1]]
    curS = np.array(cur)
    curE = curS.copy()
    addS = np.array(addS)
    addE = np.array(addE)
    mov = np.array(mov)
    for i in range(w+h-1):

        cur = curS.copy()

        while True:
            x, y = cur

            data[x][y] = min(data[x][y], data[x-d][y]+1, data[x][y-d]+1)

            if np.alltrue(cur==curE):
                break
            cur += mov

        curS += addS
        if np.max(curS == curW):
            curS -= addS
            addS = np.array([addS[1], -addS[0]])
            curS += addS


        curE += addE
        if np.max(curE== curW):
            curE -= addE
            addE = np.array([-addE[1], addE[0]])
            curE += addE

print(np.max(data[1:h+1,1:w+1]))


### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = [None] * (H*W)
matS = matE = 0
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat[matE] = (h, w, 0)
            matE+=1
    dp[h] = s

def search(dp, mat, nH, nW, cnt):
    global matE
    if dp[nH][nW] == ".":
        mat[matE] = (nH, nW, cnt+1)
        matE+=1
        dp[nH][nW] = "#"

while matS < matE:
    h, w, cnt = mat[matS]
    matS += 1

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

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

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

n, a, b = map(int, input().split())
p = 10 ** 9 + 7
ans = 0

for j in range(1, n+1) :
    if j == a or j == b :
        continue
    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]
    
    for i in range(2, n+1):
        fact.append((fact[-1] * i) % p)
        inv.append((-inv[p % i] * (p // i)) % p)
        factinv.append((factinv[-1] * inv[-1]) % p)
    
    plus = cmb(n, j, p)
    ans += plus

print(int(ans))

### FIXED CODE ###

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

def comb(n, r, mod) :
    ans1 = 1
    ans2 = 1
    for i in range(r) :
        ans1 = (ans1 * (n-i)) % mod
        ans2 = (ans2 * (i+1)) % mod
    return ans1 * pow(ans2, mod-2, mod)

ans = pow(2, n, mod) - comb(n, a, mod) - comb(n, b, mod) - 1
print(ans%mod)
### BUGGY CODE ###

import numpy as np
n,m = map(int,input().split())
a = []
b = []
for i in range(m):
    a_ , b_ = map(int,input().split())
    a.append(a_)
    b.append(b_)

a = np.array(a) - 1
b = np.array(b) - 1 
cnt = 0
in_task = np.zeros(m).astype(np.bool)

for i in range(n-1):
    if(np.any(a == i)):
        in_task += (a == i).astype(np.bool)
    if(np.any(b == i+1)):
        cnt += 1
        tmp = np.logical_not(in_task)
        a = a[tmp]
        b = b[tmp]
        in_task = np.zeros(a.shape).astype(np.bool)
print(cnt)

### FIXED CODE ###

import numpy as np
n,m = map(int,input().split())
a = np.zeros(m)
b = np.zeros(m)
for i in range(m):
    a[i] , b[i] = map(int ,input().split())

a -= 1
b -= 1 
cnt = 0

while(a.shape[0]):
    min_b = np.min(b)
    in_task = (a < min_b).astype(np.bool)
    cnt += 1
    tmp = np.logical_not(in_task)
    a = a[tmp]
    b = b[tmp]
    
print(cnt)