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

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7
EPS = 1e-6


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = LIST()
    c = [["@"] + [c for c in input()] + ["@"] for i in range(H)]
    c = [["@"] * (W + 2)] + c + [["@"] * (W + 2)]
    dd = [cc[:] for cc in c]

    # 0123: 上下左右
    stack = [(0, x1, y1, 0), (0, x1, y1, 1),
             (0, x1, y1, 2), (0, x1, y1, 3)]
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    head = 0
    while stack:
        head = 0
        new_stack = []
        while head < len(stack):
            curr, x, y, d = stack[head]
            head += 1
            flag = True
            a = curr + 1
            for k in range(1, K + 1):
                xx, yy = x + k * DX[d], y + k * DY[d]
                if c[xx][yy] == "@":
                    flag = False
                    break
                if (xx, yy) == (x2, y2):
                    print(a)
                    return
                new_stack.append((a, xx, yy, (d - 1) % 4))
                new_stack.append((a, xx, yy, (d + 1) % 4))
            if flag:
                new_stack.append((a, xx, yy, d))
        stack = new_stack

    print(-1)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


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

N,K = map(int,input().split())
A = list(map(int,input().split()))
temp = 1
for i in range(N):
    before = temp
    temp *= A[i]
    if i >= K:
        temp /= A[i-K]
        if temp > before:
            print("Yes")
        else:
            print("No")


### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
for i in range(N):
    if i >= K:
        if A[i] > A[i-K]:
            print("Yes")
        else:
            print("No")
### BUGGY CODE ###

from sys import stdin
N = int(stdin.readline().rstrip())
print(0)
s = input()
N = (N-1)//2
if s == "Male":
    while True:
        print(N)
        s = input()
        if s == "Male" and N % 2 == 0:
            N += max(L-(N//2),1)
        elif s == "Female" and N % 2 != 0:
            N += max(L-(N//2),1)
        elif s == "Vacant":
            break
        else:
            N -= max((N//2),1)
        
elif s == "Female":
    while True:
        print(N)
        s = input()
        if s == "Female" and N % 2 == 0:
            N += max(1,L-(N//2))
        elif s == "Male" and N % 2 != 0:
            N += max(L-(N//2),1)
        elif s == "Vacant":
            break
        else:
            N -= max((N//2),1)

### FIXED CODE ###

from sys import stdin
N = int(stdin.readline().rstrip())
r = N-1
l = 0
print(0)
s = input()
cnt = 0
mid = (r+l)//2
if s == "Male":
    for _ in range(25):
        print(mid)
        s = input()
        if s == "Male" and mid % 2 == 0:
            l += max((r-l)//2,1)
        elif s == "Female" and mid % 2 != 0:
            l += max((r-l)//2,1)
        elif s == "Vacant":
            break
        else:
            r -= max((r-l)//2,1)
        mid = (r+l)//2
        
elif s == "Female":
    for _ in range(25):
        print(mid)
        s = input()
        if s == "Female" and mid % 2 == 0:
            l += max((r-l)//2,1)
        elif s == "Male" and mid % 2 != 0:
            l += max((r-l)//2,1)
        elif s == "Vacant":
            break
        else:
            r -= max((r-l)//2,1)
        mid = (r+l)//2
### BUGGY CODE ###

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


### FIXED CODE ###

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

n = int(input())
out = 0
for i in range(n):
    j = 1
    while (i + 1) * j <= n:
        out += (i + 1) * j
        j += 1

print(out)


### FIXED CODE ###

n = int(input())
out = 0
for i in range(n):
    k = n // (i + 1)
    out += (i + 1) * k * (k + 1)/2

print(int(out))
### BUGGY CODE ###

from copy import deepcopy
from collections import deque
def main():
    n = int(input())
    s = list(input())
    sr = [0] * n
    sg = [0] * n
    sb = [0] * n
    for i1 in range(n):
        ts = s[i1]
        if ts == 'R':
            sr[i1] = 1
        elif ts == 'G':
            sg[i1] = 1
        else:
            sb[i1] = 1
    if n <= 3:
        print(0)
        exit()
    r = 0
    for ia in range(0,n-3):
        ta = s[ia]
        if ta == 'R':
            tal = sr
        elif ta == 'G':
            tal = sg
        else:
            tal = sb
        for ib in range(ia+1, n-1):
            if tal[ib]:
                pass
            else:
                tb = s[ib]
                t = (ta, tb)
                sa = ib - ia

                if 'R' in t and 'G' in t:
                    r += sum(sb[ib+1:])
                    if ib + sa < n:
                        r -= sb[ib + sa]
                elif 'G' in t and 'B' in t:
                    r += sum(sr[ib+1:])
                    if ib + sa < n:
                        r -= sr[ib + sa]
                else:
                    r += sum(sg[ib + 1:])
                    if ib + sa < n:
                        r -= sg[ib + sa]

    print(r)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    s = list(input())
    sr = [0] * n
    sg = [0] * n
    sb = [0] * n
    for i1 in range(n):
        ts = s[i1]
        if ts == 'R':
            sr[i1] = 1
        elif ts == 'G':
            sg[i1] = 1
        else:
            sb[i1] = 1
    if n <= 3:
        print(0)
        exit()
    r = 0
    for ia in range(0,n-3):
        ta = s[ia]
        if ta == 'R':
            r += sum(sg[ia+1:]) * sum(sb[ia+1:])
        elif ta == 'G':
            r += sum(sr[ia+1:]) * sum(sb[ia+1:])
        else:
            r += sum(sg[ia + 1:]) * sum(sr[ia + 1:])
        for ib in range((n - ia)//2+1):
            if ia + ib * 2 < n:
                if ta != s[ia + ib] and ta != s[ia + ib + ib] and s[ia+ib]!= s[ia + ib + ib]:
                    r -= 1
    print(r)

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

import sys
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]

N,Q=map(int,input().split())
graph=[[]for _ in range(N)]
point=[0]*N
for _ in range(N-1):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
for _ in range(Q):
    a,b=map(int,input().split())
    a=a-1
    point[a]=point[a]+b

def dfs(now,prev=-1):
    for i in graph[now]:
        if i==prev:
            continue
        point[i]=point[i]+point[now]
        dfs(i,now)
dfs(0)
print(*point)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]

N,Q=map(int,input().split())
graph=[[]for _ in range(N)]
point=[0]*N
for _ in range(N-1):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
for _ in range(Q):
    a,b=map(int,input().split())
    a=a-1
    point[a]=point[a]+b

def dfs(now,prev=-1):
    for next in graph[now]:
        if next==prev:
            continue
        point[next]=point[next]+point[now]
        dfs(next,now)
dfs(0)
print(*point)
### BUGGY CODE ###

Q = int(input())
prime = [2]

def setPrime(TOP):
    for x in range(3,TOP+1):
        for y in range(len(prime)):
            if x%prime[y] == 0:
                break
            if y == len(prime)-1:
                prime.append(x)
l = [0]*Q
r = [0]*Q
for i in range(Q):
    l[i],r[i] = list(map(int,input().split()))

setPrime(max(r))

for n in range(Q):
    result = 0
    for m in range(l[n],r[n]+1):
        if m in prime and int((m+1)/2) in prime:
            result += 1
    print(result)
            

### FIXED CODE ###

import math
Q=int(input())
querys = [list(map(int,input().split())) for x in range(Q)]
large = max(q[1] for q in querys)
like2017 = [0]*(large+1)

#siever
cands = [False if (5 < i and (i%2)*(i%3)*(i%5) == 0) or (i < 2) or (i == 4) else True for i in range(large+1)]
if 5 <= large:
  for i in range(6,int(math.sqrt(large)+1)):
    if cands[i]:
      for j in range(i*i,large+1,i):
        if cands[j]:
          cands[j] = False

#find 2017-like-number          
for x in range(large+1):
  if cands[x] and cands[(x+1)//2]:
    like2017[x] = 1
for y in range(1,large+1):
  like2017[y] += like2017[y-1]

for q in querys:
  print(like2017[q[1]]-like2017[q[0]-1])
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))
    Q = int(input())
    B = [0 for i in range(Q)]
    C = [0 for i in range(Q)]
    
    A_kind = []
    A_num = []
    ans = 0
    for a in A:
        ans += a
        if not a in A_kind:
            A_kind.append(a)
            A_num.append(1)
        else:
            A_num[A_kind.index(a)] += 1
    
    for q in range(Q):
        B[q],C[q] = map(int,input().split())
        
    for q in range(Q):
        b = B[q]
        c = C[q]
        if b in A_kind:
            n = A_kind.index(b)
            ans += (c - A_kind[n])*A_num[n]
            if c in A_kind:
                A_num[A_kind.index(c)] += A_num[n]
                del A_kind[n]
                del A_num[n]
            else:
                A_kind[n] = c
        print(ans)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))
    Q = int(input())
    B = [0 for i in range(Q)]
    C = [0 for i in range(Q)]
    
    A_num = [0 for i in range(10**5+1)]
    ans = 0
    for a in A:
        ans += a
        A_num[a] += 1
    
    for q in range(Q):
        b,c = map(int,input().split())
        if A_num[b] != 0:
            ans += (c-b)*A_num[b]
            A_num[c] += A_num[b]
            A_num[b] = 0
            
        print(ans)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, M = map(int, input().split())
A = [int(x) for x in input().split()]
sum = sum(A)

for i in range(M):
    sum -= A[A.index(max(A))] - (A[A.index(max(A))] // 2)
    A[A.index(max(A))] //= 2

print(sum)


### FIXED CODE ###

import heapq
from math import ceil

N, M = map(int, input().split())
A = [(-1)*int(x) for x in input().split()]

if len(A) == 1:
    for i in range(M):
        A[0] = ceil(A[0]/2)
    A[0] = -A[0]
    print(A[0])
else:
    count = 0
    heapq.heapify(A)
    a = heapq.heappop(A)
    b = heapq.heappop(A)
    while count < M:
        while a <= b:
            a = ceil(a/2)
            count += 1
            if count == M:
                break
        if count == M:
            break
        heapq.heappush(A,a)
        a = b
        b = heapq.heappop(A)
    heapq.heappush(A,a)
    heapq.heappush(A,b)
    ans = (-1)*sum(A)
    print(ans)
### BUGGY CODE ###

n = int(input())
a = 1
for i in range(1,n+1):
    a = a*i
print(a%(10**9+7))

### FIXED CODE ###

import math
n = int(input())
a = math.factorial(n)
print(a%(10**9+7))
### BUGGY CODE ###

n,m=input().split()
n=int(n)
m=int(m)
i=1
x=list()
y=list()
ans=0
g=0
i=i+1
l,r=input().split()
l=int(l)
r=int(r)
while l != r + 1:
     x.append(l)
     l = l + 1

i=1

while m!=i:
    i=i+1
    l,r=input().split()
    l=int(l)
    r=int(r)
    while l != r + 1:
        y.append(l)
        l = l + 1

    while g!=len(x):
        v=x[g] in y
        if v==False:
            x.remove(x[g])
        else:
            g=g+1
    g=0
    y=[]



print(len(x))

### FIXED CODE ###

n,m=input().split()
n=int(n)
m=int(m)
i=0
x=list()
y=list()
ans=0
g=0
ll=[]
rr=[]


while i!=m:
    i=i+1
    l,r=input().split()
    l=int(l)
    r=int(r)
    ll.append(l)
    rr.append(r)
l=max(ll)
r=min(rr)

ans=r-l+1
if l>r:
    ans=0
print(ans)
### BUGGY CODE ###

import heapq
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N, M, S = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    edge[u].append((v, a, b))
    edge[v].append((u, a, b))
CD = tuple(tuple(map(int, input().split())) for _ in range(N))

inf = 10**18
U = N*50
S = min(S, U)
dist = [[inf] * (U + 1) for _ in range(N)]
dist[0][S] = 0

que = [(0, -S, 0)]  # 時間、現在地、銀貨の数
while que:
    time, silver, now = heapq.heappop(que)
    silver = -silver
    if dist[now][silver] < time:
        continue
    # 両替する
    c, d = CD[now]
    n = 1
    while silver + c * n <= U:
        if dist[now][silver + c * n] > time + n * d:
            dist[now][silver + c * n] = time + n * d
            heapq.heappush(que, (time + n * d, -(silver + c * n), now))
            n += 1
    # 移動する
    for nxt, s, t in edge[now]:
        if silver < s:
            continue
        if dist[nxt][silver - s] > time + t:
            dist[nxt][silver - s] = time + t
            heapq.heappush(que, (time + t, -(silver - s), nxt))

for i in range(1, N):
    print(min(dist[i]))

### FIXED CODE ###

import heapq
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N, M, S = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    edge[u].append((v, a, b))
    edge[v].append((u, a, b))
CD = tuple(tuple(map(int, input().split())) for _ in range(N))

inf = 10**18
U = N*50
S = min(S, U)
dist = [[inf] * (U + 1) for _ in range(N)]
dist[0][S] = 0

que = [(0, -S, 0)]  # 時間、現在地、銀貨の数
while que:
    time, silver, now = heapq.heappop(que)
    silver = -silver
    if dist[now][silver] < time:
        continue
    # 両替する
    c, d = CD[now]
    n = 1
    while silver + c * n <= U:
        if dist[now][silver + c * n] > time + n * d:
            dist[now][silver + c * n] = time + n * d
            heapq.heappush(que, (time + n * d, -(silver + c * n), now))
            n += 1
        else:
            break
    # 移動する
    for nxt, s, t in edge[now]:
        if silver < s:
            continue
        if dist[nxt][silver - s] > time + t:
            dist[nxt][silver - s] = time + t
            heapq.heappush(que, (time + t, -(silver - s), nxt))

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

n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in range(len(a)):
    ans = ans * a[i]
if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
if 0 not in a:
    for i in range(len(a)):
        ans = ans * a[i]
        if ans > 10**18:
            print(-1)
            exit()
    print(ans)
else:
    print(0)
### BUGGY CODE ###

#C
def f(x):
    return int(x) - 1

n, q = map(int, input().split())
s = input()
l = [0] * q
r = [0] * q
for i in range(q):
    l[i], r[i] = map(f, input().split())
for i in range(q):
    count=0
    for j in range(l[i], r[i]):
        if r[i] == n:
            pass
        if s[j] == "A" and s[j + 1] == "C":
            count+=1
    print(count)

### FIXED CODE ###

#C
def f(x):
    return int(x) - 1

n, q = map(int, input().split())
s = input()
t = [0] * (n + 1)
for i in range(n):
    t[i + 1] = t[i] + (1 if s[i:i + 2] == "AC" else 0)
# print(t)
for i in range(q):
    l, r = map(int, input().split())
    print(t[r - 1] - t[l - 1])
### BUGGY CODE ###

# dp[i][j]=(区間[i,j]が残っているとき次の手番の得点-そうじゃない人の得点)
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
INF=-10**14
dp=[[0]*n for i in range(n)]
flag=[[0]*n for i in range(n)]
def memo(i,j):
    if flag[i][j]:
        return dp[i][j]
    flag[i][j]=1
    if i==j:
        dp[i][j]=a[i]
    else:
        dp[i][j]=max(a[i]-memo(i+1,j),a[j]-memo(i,j-1))
    return dp[i][j]
print(memo(0,n-1))

### FIXED CODE ###

# dp[j][i]=(区間[i,j]が残っているとき次の手番の得点-そうじゃない人の得点)
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
INF=-10**14
dp=[[0]*(i+1) for i in range(n)]
for i in range(n):
    dp[i][i]=a[i]
for i in range(1,n):
    for j in range(i-1,-1,-1):
        dp[i][j]=max(a[i]-dp[i-1][j],a[j]-dp[i][j+1])
print(dp[-1][0])
### BUGGY CODE ###

s = input()
q = int(input())
t  ={}
for i in range(q):
    t[i]=input().split()
for d in t.values():
    if d[0] == "1":
        s2 = s[::-1]
    elif d[0] == "2":
        if d[1] == "1":
            s2 = d[2]+s
        else:
            s2 = s+d[2]
    s = s2
print(s)

### FIXED CODE ###

s = input()
q = int(input())
t  ={}
for i in range(q):
    t[i]=input().split()
rv_count = 0
x = "X"
for d in t.values():
	if d[0] == "1":
		rv_count += 1
	else:
		if rv_count % 2 ==0:
			if d[1] == "1":
				x2 = d[2]+x
			else:
				x2 = x+d[2]
			x = x2
		else:
			red = d[2][::-1]
			if d[1] == "1":
				x2 = x + red
			else:
				x2 = red+x
			x = x2

if rv_count%2 == 0:
    xf = x.replace("X", s)
else:
	xf = x.replace("X", s)[::-1]
    
print(xf)
### BUGGY CODE ###

H,W,D=map(int,input().split())
A=[]

for h in range(H):
    A.append(list(map(int,input().split())))

pos= {}
for h in range(H):
    for w in range(W):
        pos[A[h][w]]=[h,w]



Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    nowh,noww=pos[L]
    now=L
    ans=0
    while now<R:
        newh,neww=pos[now+D]
        ans+=abs(nowh-newh)+abs(noww-neww)
        now+=D
        nowh=newh
        noww=neww
    print(ans)


### FIXED CODE ###

H,W,D=map(int,input().split())
A=[]

for h in range(H):
    A.append(list(map(int,input().split())))

pos= {}
for h in range(H):
    for w in range(W):
        pos[A[h][w]]=[h,w]

S=[0]*(H*W)
for d in range(D):
    tmp=0
    now=d+1
    while now+D<=H*W:
        nowh,noww=pos[now]
        newh,neww=pos[now+D]
        tmp+=abs(nowh-newh)+abs(noww-neww)
        S[now+D-1]=tmp
        now+=D

Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    ans=S[R-1]-S[L-1]
    print(ans)
### BUGGY CODE ###

a, b, k = map(int, input().split())

for i in range(a, b+1):
    if b - k < i or i < a + k:
        print(i)
    else:
        continue

### FIXED CODE ###

a, b, k = map(int, input().split())

for i in range(a, min(a+k, b+1)):
    print(i)
for i in range(max(a+k, b+1-k), b+1):
    print(i)
### BUGGY CODE ###

import copy

n = int(input())
h = [int(i) for i in input().split()]


def main():
    print("Yes" if detect() else "No")


def detect():
    for i in range(n):
        if (h[i] - min(h[i::])) > 1:
            return False
    return True


main()


### FIXED CODE ###

n = int(input())
h = [int(i) for i in input().split()]


def main():
    h[0] -= 1
    print("Yes" if detect() else "No")


def detect():
    for i in range(1, n):
        if h[i] > h[i-1]:
            h[i] -= 1
        elif h[i] < h[i-1]:
            return False

    return True


main()
### BUGGY CODE ###

"""
解説を参考に作成
"""

from collections import deque


def solve():
    H, W = map(int, input().split())
    mass = [[0] * W for _ in range(H)]
    # queue1 = deque([])
    # queue2 = deque([])
    queue1 = []
    queue2 = []
    for Hi in range(H):
        massHi = [True if s == '.' else False for s in list(input())]
        for Wi in range(W):
            mass[Hi][Wi] = massHi[Wi]
            if not massHi[Wi]:
                queue1.append([Hi, Wi])
    import datetime
    d = datetime.datetime.now()
    count = -1
    while True:
        # print('count: {}, queue:{}'.format(count, len(queue1)))
        if len(queue1) == 0:
            break
        for h, w in queue1:
            # left
            if w != 0 and mass[h][w - 1]:
                mass[h][w - 1] = False
                queue2.append([h, w - 1])
            # right
            if w < W - 1 and mass[h][w + 1]:
                mass[h][w + 1] = False
                queue2.append([h, w + 1])
            # top
            if h < H - 1 and mass[h + 1][w]:
                mass[h + 1][w] = False
                queue2.append([h + 1, w])
            # button
            if h != 0 and mass[h - 1][w]:
                mass[h - 1][w] = False
                queue2.append([h - 1, w])

        count += 1
        queue1 = queue2
        queue2 = []
    print(count)

    # print(datetime.datetime.now() - d)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

"""
解説と提出 #5747380を参考に作成
"""

from collections import deque


def solve():
    H, W = map(int, input().split())
    # mass = [[False] * W for _ in range(H)]
    # queue1 = deque([])
    # queue2 = deque([])
    queue1 = []
    queue2 = []
    mass = []
    mass.append([False] * (W + 2))  # 外枠
    for Hi in range(1, H + 1):
        mass.append([False] + [s == '.' for s in list(input())] + [False])
        for Wi in range(1, W + 1):
            if not mass[Hi][Wi]:
                queue1.append((Hi, Wi))
    mass.append([False] * (W + 2))  # 外枠
    import datetime
    d = datetime.datetime.now()
    count = -1
    while True:
        # print('count: {}, queue:{}'.format(count, len(queue1)))
        if len(queue1) == 0:
            break
        for h, w in queue1:
            # left
            if mass[h][w - 1]:
                mass[h][w - 1] = False
                queue2.append((h, w - 1))
            # right
            if mass[h][w + 1]:
                mass[h][w + 1] = False
                queue2.append((h, w + 1))
            # top
            if mass[h + 1][w]:
                mass[h + 1][w] = False
                queue2.append((h + 1, w))
            # button
            if mass[h - 1][w]:
                mass[h - 1][w] = False
                queue2.append((h - 1, w))

        count += 1
        queue1 = queue2
        queue2 = []
    print(count)

    # print(datetime.datetime.now() - d)


if __name__ == '__main__':
    solve()