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

from collections import deque


H, W = map(int, input().split())
A = [input() for _ in range(H)]
m = [[3000] * W for _ in range(H)]
for i, s in enumerate(A):
    for j, c in enumerate(s):
        if c == '#':
            m[i][j] = 0


def bfs(i, j):
    queue = deque()
    queue.append((i, j))
    while queue:
        p, q = queue.popleft()
        if 0 < p and m[p - 1][q] > m[p][q] + 1:
            m[p - 1][q] = m[p][q] + 1
            queue.append((p - 1, q))
        if 0 < q and m[p][q - 1] > m[p][q] + 1:
            m[p][q - 1] = m[p][q] + 1
            queue.append((p, q - 1))
        if p < H - 1 and m[p + 1][q] > m[p][q] + 1:
            m[p + 1][q] = m[p][q] + 1
            queue.append((p + 1, q))
        if q < W - 1 and m[p][q + 1] > m[p][q] + 1:
            m[p][q + 1] = m[p][q] + 1
            queue.append((p, q + 1))


for i, r in enumerate(m):
    for j, n in enumerate(r):
        if n == 0:
            bfs(i, j)
_max = 0
for r in m:
    _max = max(_max, max(r))
print(_max)


### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
m = [[0 if c == '#' else 3000 for c in input()] for _ in range(H)]
queue = deque()
for i, r in enumerate(m):
    for j, n in enumerate(r):
        if n == 0:
            queue.append((i, j))
while queue:
    p, q = queue.popleft()
    if 0 < p and m[p - 1][q] > m[p][q] + 1:
        m[p - 1][q] = m[p][q] + 1
        queue.append((p - 1, q))
    if 0 < q and m[p][q - 1] > m[p][q] + 1:
        m[p][q - 1] = m[p][q] + 1
        queue.append((p, q - 1))
    if p < H - 1 and m[p + 1][q] > m[p][q] + 1:
        m[p + 1][q] = m[p][q] + 1
        queue.append((p + 1, q))
    if q < W - 1 and m[p][q + 1] > m[p][q] + 1:
        m[p][q + 1] = m[p][q] + 1
        queue.append((p, q + 1))
_max = 0
for r in m:
    _max = max(_max, max(r))
print(_max)
### BUGGY CODE ###

from collections import deque
 
n = int(input())
lst = [deque(map(int, input().split())) for _ in range(n)]
 
current = []
for i in range(n):
    current.append(lst[i].popleft())

count = 0
players = set(range(1, n+1))
while True:
    index_lst = []
    for i in players:
        candidate = current[i-1]
        if candidate == 0:
            continue
        if current[candidate-1] == i:
            index_lst += [i, candidate]   
    if len(index_lst) == 0:
        if sum(current) == 0:
            print(count)
            break
        else:
            print(-1)
            break
    for i in set(index_lst):
        if len(lst[i-1]) == 0:
            current[i-1] = 0
        else:
            current[i-1] = lst[i-1].popleft()
    players = index_lst
    count += 1

### FIXED CODE ###

from collections import deque
 
n = int(input())
lst = [deque(map(int, input().split())) for _ in range(n)]
 
current = []
for i in range(n):
    current.append(lst[i].popleft())

count = 0
players = set(range(1, n+1))
while True:
    index_lst = []
    for i in players:
        candidate = current[i-1]
        if candidate in index_lst:
            continue
        if current[candidate-1] == i:
            index_lst += [i, candidate]   
    if len(index_lst) == 0:
        if sum(current) == 0:
            print(count)
            break
        else:
            print(-1)
            break
    for i in index_lst:
        if len(lst[i-1]) == 0:
            current[i-1] = 0
        else:
            current[i-1] = lst[i-1].popleft()
    players = set(index_lst)
    count += 1
### BUGGY CODE ###

def is_prime(n):
    """
    nが素数かどうか判定する
    """
    if n < 2:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    else:
        i = 3
        while i ** 2 <= n:
            if n % i == 0:
                return False
            i += 2
        return True


Q = int(input())
for _ in range(Q):
    left, right = map(int, input().split(' '))
    if left % 2 == 0:
        left += 1
    print(len([n for n in range(left, right + 1, 2) if is_prime(n) and is_prime((n + 1) // 2)]))


### FIXED CODE ###

from functools import lru_cache


@lru_cache(maxsize=None)
def is_prime(n):
    """
    nが素数かどうか判定する
    """
    if n < 2:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    else:
        i = 3
        while i ** 2 <= n:
            if n % i == 0:
                return False
            i += 2
        return True


size = 10 ** 5 + 1
memo = [0] * size
for n in range(3, size):
    memo[n] = memo[n - 1]
    if n % 2 == 1 and is_prime(n) and is_prime((n + 1) // 2):
        memo[n] += 1

Q = int(input())
for _ in range(Q):
    left, right = map(int, input().split(' '))
    print(memo[right] - memo[left - 1])
### BUGGY CODE ###

n = int(input())
s = input()
memo_ls = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
    for j in range(min(i+1,n-1), n):
        if s[i] == s[j]:
            memo_ls[i][j] = memo_ls[i-1][j-1] + 1
for i in range(n):
    for j in range(min(i+1,n-1), n):
        if memo_ls[i][j] > 0:
            if j - i < memo_ls[i][j]:
                memo_ls[i][j] = j - i
print(max([max(i) for i in memo_ls]))

### FIXED CODE ###

n = int(input())
s = input()
_max = 0
memo_ls = [[0 for i in range(n)] for j in range(n)]
memo_dict = {i : [0 for j in range(n)] for i in range(-1,n)}
for i in range(n):
    for j in range(min(i+1,n-1), n):
        if s[i] != s[j]:
            continue
        candidate = memo_dict[i-1][j-1] + 1
        if candidate > j - i:
            candidate = j - i
        memo_dict[i][j] = candidate
        if candidate > _max:
            _max = candidate
print(_max)
### BUGGY CODE ###

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

ls = [0] * (n+1)
for i in range(n-1):
    if s[i] == 'A' and s[i+1] == 'C':
        ls[i]= 1

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

### FIXED CODE ###

n,q = map(int, input().split())
s =input()
A = [[int(j) for j in input().split()] for i in range(q)]
ls = [0] * (n+1)
for i in range(n-1):
    if s[i] == 'A' and s[i+1] == 'C':
        ls[i+1]= ls[i]+1
    else:
        ls[i+1]= ls[i]

for k in range(q):
    print(ls[A[k][1]-1]-ls[A[k][0]-1])
### BUGGY CODE ###

def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)
def lcm(a,b):
    return a//gcd(a,b)*b

n=int(input())
a=[int(i) for i in input().split()]
L=a[0]
for i in a:
    if L%i!=0:
        L=lcm(L,i)
ans=0
for i in a:
    ans=(ans+L//i)%(10**9+7)
print(ans)

### FIXED CODE ###

from fractions import gcd
def lcm(a,b):
    return a//gcd(a,b)*b

n=int(input())
a=[int(i) for i in input().split()]
L=a[0]
for i in a:
    L=lcm(L,i)
ans=0
for i in a:
    ans+=L//i
print(ans%(10**9+7))
### BUGGY CODE ###

import numpy as np
INF=10**18
N,M,L=map(int,input().split())
d=np.zeros((N,N))
d[:,:]=INF
for i in range(N):
    d[i,i]=0
for m in range(M):
    A,B,C=map(int,input().split())
    d[A-1,B-1]=C
    d[B-1,A-1]=C

for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i,j]=min(d[i,j],d[i,k]+d[k,j])
for i in range(N):
        for j in range(N):
            if d[i,j]<=L:
                d[i,j]=1
for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i,j]=min(d[i,j],d[i,k]+d[k,j])
ans=[]
Q=int(input())
for i in range(Q):
    s,t=map(int,input().split())
    dis=d[s-1,t-1]
    if dis==INF:
        ans.append(-1)
    else:
        ans.append(dis-1)

for a in ans:
    print(int(a))


### FIXED CODE ###

INF=10**15
N,M,L=map(int,input().split())
d=[[INF for i in range(N)] for j in range(N)]
d1=[[INF for i in range(N)] for j in range(N)]
for i in range(N):
    d[i][i]=0
for m in range(M):
    A,B,C=map(int,input().split())
    d[A-1][B-1]=C
    d[B-1][A-1]=C

for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
for i in range(N):
        for j in range(N):
            if i!=j and d[i][j]<=L:
                d1[i][j]=1
                d1[j][i]=1
for k in range(N):
    for i in range(N):
        for j in range(N):
            d1[i][j]=min(d1[i][j],d1[i][k]+d1[k][j])

Q=int(input())
for _ in range(Q):
    s,t=map(int,input().split())
    dis=d1[s-1][t-1]
    if dis==INF:
        print(-1)
    else:
        print(dis-1)
### BUGGY CODE ###

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

tree = {i:[] for i in range(1, n + 1)}
for _ in range(1, n):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

tmp = [1]
while len(tmp) != 0:
    tmp2 = tmp
    tmp = []
    for oya in tmp2:
        tmp.extend(tree[oya])
        for ko in tree[oya]:
            tree[ko].remove(oya)


cnt = [list(map(int, input().split())) for _ in range(q)]

ans = [0]*n
for p, x in cnt:
    tmp = [p]
    while len(tmp) != 0:
        for i in tmp:
            ans[i-1] += x
        tmp2 = tmp
        tmp = []
        for aaa in tmp2:
            tmp.extend(tree[aaa])


print(" ".join(map(str, ans)))

### FIXED CODE ###

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

tree = {i:[] for i in range(1, n + 1)}
for _ in range(1, n):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

cnt = [0]*n
for _ in range(q):
    p, x = map(int, input().split())
    cnt[p-1] += x

check = [0]*n

tmp = [1]
while len(tmp) != 0:
    tmp2 = tmp
    tmp = []
    for oya in tmp2:
        check[int(oya)-1] = 1
        for ko in tree[oya]:
            if check[ko-1] == 0:
                cnt[ko-1] += cnt[oya-1]
                tmp.append(ko)


print(" ".join(map(str, cnt)))
### BUGGY CODE ###

S = input()
l = len(S)
T = [0]
for i in range(1, l+1):
    T.append((T[-1]+int(S[-i])*10**(i-1)) % 2019)
C = {}
for t in T:
    try:
        C[t] += 1
    except:
        C[t] = 1
ans = 0
for c in C.values():
    ans += c*(c-1)//2
print(ans)


### FIXED CODE ###

S = [int(i) for i in list(input())]
S.reverse()
l = len(S)
T = [0]
for i in range(l):
    T.append((T[-1]+S[i]*(pow(10, i, 2019))) % 2019)
C = {}
for t in T:
    try:
        C[t] += 1
    except:
        C[t] = 1
ans = 0
for c in C.values():
    ans += c*(c-1)//2
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
n=int(input())
a=[int(x) for x in input().split()]
mod=10**9+7
lcm=1
from fractions import gcd
for ai in a:
    lcm=ai*lcm//gcd(ai,lcm)
ans=0
for ai in a:
    ans+=lcm//ai
print(ans%mod)

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
n=int(input())
a=[int(x) for x in input().split()]
mod=10**9+7
lcm=1
from fractions import gcd
for ai in a:
    lcm=ai*lcm//gcd(ai,lcm)
ans=0
for ai in a:
    ans+=lcm//ai
print(ans%mod)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

sys.setrecursionlimit(10**6)
N, Q = map(int, input().split())
tree = [[] for _ in range(N+1)]
ans = [0 for _ in range(N+1)]

def dfs(v, p = -1):
    for u in tree[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)

def main():

    AB = [list(map(int,input().split())) for _ in range(N-1)]
    AB.sort()

    for a,b in AB:
        tree[a].append(b)
        tree[b].append(a)
    # print(tree)

    for _ in range(Q):
        p,x = map(int, input().split())
        ans[p] += x
    # print(ans)

    dfs(1)
    print(*ans[1:])

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**6)
N, Q = map(int, input().split())
tree = [[] for _ in range(N)]
ans = [0] * N

def dfs(v, p):
    for u in tree[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)

def main():

    for _ in range(N-1):
        a, b = map(int,input().split())
        a -= 1
        b -= 1
        tree[a].append(b)
        tree[b].append(a)

    for _ in range(Q):
        p,x = map(int, input().split())
        ans[p-1] += x
    # print(ans)

    dfs(0, -1)
    print(*ans)

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

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

mod=998244353
if D[0]!=0:
  print(0)
else:
  ans=1
  cnt=[0]*n
  for i in range(1,n):
    cnt[i]=D.count(i)
  for i in range(2,n):
    if cnt[i]>0:
      ans*=cnt[i-1]**cnt[i]
      
  print(ans%mod)

### FIXED CODE ###

import collections
n=int(input())
D=list(map(int,input().split()))

mod=998244353
c=collections.Counter(D)

if D[0]!=0 or c[0]!=1:
  print(0)
else:
  ans=c[0]
  node=c[0]
  for i in range(1,n):
    ans*=(c[i-1]**c[i])%mod
    node+=c[i]
    if node==n:
      break
  print(ans%mod)
### BUGGY CODE ###


import itertools

def main():
    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()))

    p = itertools.product(A, B, C)
    data = [i + j + k for i, j, k in p]
    data.sort(reverse=True)

    for i in range(K):
        print(data[i])

if __name__ == '__main__':
    main()


### FIXED CODE ###



def main():
    X, Y, Z, K = list(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)


    data = []
    for i in range(X):
        for j in range(Y):
            if i * j > K:
                break
            for k in range(Z):
                if i * j * k > K:
                    break
                data.append(A[i] + B[j] + C[k])

    data.sort(reverse=True)

    for i in range(K):
        print(data[i])

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

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

for i in range(N):
  for j in range(i+1,N):
    p = A[i]*A[j]% (10**9+7)
    P += p
    
sum = P%(10**9+7)
print(sum)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
P = 0
S = sum(A)
m = 10**9+7

for i in range(N):
  S -= A[i]
  P += A[i]*S
  
ans = P%m
print(ans)
### BUGGY CODE ###

N,M,Q = map(int, input().split())
train = []
quest = []
ans = []
for i in range(M):
    train.append([int(x) for x in input().split()])
for j in range(Q):
    quest.append([int(x) for x in input().split()])
for k in range(Q):
    c = 0
    for l in range(M):
        if quest[k][0] <= train[l][0] and train[l][1] <= quest[k][1]:
            c += 1
    ans.append(c)
for m in range(Q):
    print(ans[m])

### FIXED CODE ###

N,M,Q = map(int, input().split())
train = []
quest = []
for i in range(M):
    train.append([int(x) for x in input().split()])
for j in range(Q):
    quest.append([int(x) for x in input().split()])

List = []
for s in range(N):
    List.append([])

for k in range(N):
    for l in range(k+1):
        List[k].append(0)

for i in range(M):
    List[N-(train[i][1]-train[i][0]+1)][train[i][0]-1] += 1

num = N-1

while num >= 1:
    for j in range(len(List[num-1])):
        List[num-1][j] += List[num][j] + List[num][j+1]
        if num-1 < N-2:
            List[num-1][j] -= List[num+1][j+1]
    num -= 1
for k in range(Q):
    print( List[N-(quest[k][1]-quest[k][0]+1)][quest[k][0]-1])
### BUGGY CODE ###

input()
ls = list(map(int,input().split()))
n = 0
for i in set(ls):
    if ls.count(i) == 0 or ls.count(i) == i:
        pass
    elif ls.count(i) > i:
        n += ls.count(i) - i
    else:
        n += ls.count(i)
print(n)

### FIXED CODE ###

from collections import Counter
input()
a = map(int,input().split())

result = 0
for k, v in Counter(a).items():
    if k > v:
        result += v
    elif k < v:
        result += v-k
print(result)
### BUGGY CODE ###

N = int(input())
X = list(input())
es = [0,N,0]

def p(X):
    print(X)

def list_change(X):
    for i in range(N):
        if X[i] == 'W':
            es[0] = i
            for j in reversed(range(es[1])):
                if X[j] == 'R':
                    es[1] = j
                    if i<j :
                        X[i] = 'R'
                        X[j] = 'W'
                        es[2] +=1
                        break
                   


list_change(X)
p(es[2])


### FIXED CODE ###

N = int(input())
X = list(input())
es = [0,N,0]

def p(X):
    print(X)

def list_change(X):
    for i in range(N):
        if X[i] == 'W':
            es[0] = i
            for j in reversed(range(es[1])):
                if X[j] == 'R':
                    es[1] = j
                    if i<j :
                        X[i] = 'R'
                        X[j] = 'W'
                        es[2] +=1
                        break
                elif j == 0:
                    es[1] = 1
                


list_change(X)
p(es[2])
### BUGGY CODE ###

N = int(input())
S = str(input())
R = []
G = []
B = []
answer = 0
for i in range(N):
    if S[i] == 'R':
        R.append(i)
    if S[i] == 'G':
        G.append(i)
    if S[i] == 'B':
        B.append(i)
for r in R:
    for g in G:
        for b in B:
            if abs(min(r, g)-b) != abs(max(r, g)-b) and abs(min(r, b)-g) != abs(max(r, b)-g) and abs(min(b,g)-r) != abs(max(g, b)-r):
                answer += 1
print(answer)

### FIXED CODE ###

N = int(input())
S = str(input())
R = 0
G = 0
B = 0
Z = 0
for i in range(N):
    if S[i] == 'R':
        R += 1
    if S[i] == 'G':
        G += 1
    if S[i] == 'B':
        B += 1

for i in range(N-1):
    for j in range(i+1, N):
        k = 2 * j - i
        if k > N-1:
            continue
        if S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
            Z += 1
print(R*G*B-Z)
### BUGGY CODE ###

from operator import add
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


# 解説見た

H, W, K = map(int, input().split())
MEIJI = []
for _ in range(H):
    MEIJI.append(list(map(int, list(input()))))

# 全部のカットを試す
ans = 10 ** 5
for h in range(2 ** (H - 1)):
    # 分割できるか
    ok = False

    # 先に横の分割の数
    row = 1
    for i in range(H - 1):
        row += (h >> i) & 1

    num_cut = row - 1
    cnt = [0] * row

    #print("cut == ", h, "row == ", row)

    # 列は貪欲にカット
    for c in range(W):
        idx = 0
        tmp_cnt = [0] * row
        for r in range(H):

            if r != 0 and (h >> r - 1) & 1:
                idx += 1

            tmp_cnt[idx] += MEIJI[r][c]

        # チェック
        new_cnt = list(map(add, cnt, tmp_cnt))

        if any([K < x for x in new_cnt]):
            cnt = tmp_cnt
            num_cut += 1
        else:
            ok = True
            cnt = new_cnt

        #print("column:", c, tmp_cnt)

    if ok:
        ans = min(num_cut, ans)

print(ans)


### FIXED CODE ###

from operator import add
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


# 解説見た

H, W, K = map(int, input().split())
MEIJI = []
for _ in range(H):
    MEIJI.append(list(map(int, list(input()))))

# 全部のカットを試す
ans = 10 ** 5
for h in range(2 ** (H - 1)):
    # 分割できるか
    ok = False

    # 先に横の分割の数
    row = 1
    for i in range(H - 1):
        row += (h >> i) & 1

    num_cut = row - 1
    cnt = [0] * row

    #print("cut == ", h, "row == ", row)

    # 列は貪欲にカット
    for c in range(W):
        idx = 0
        tmp_cnt = [0] * row
        for r in range(H):

            if r != 0 and (h >> r - 1) & 1:
                idx += 1

            tmp_cnt[idx] += MEIJI[r][c]

        # チェック
        new_cnt = list(map(add, cnt, tmp_cnt))

        if any([K < x for x in new_cnt]):
            cnt = tmp_cnt
            num_cut += 1
        else:
            ok = True
            cnt = new_cnt

        #print("column:", c, tmp_cnt)

    if ok:
        ans = min(num_cut, ans)

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

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


### FIXED CODE ###

import numpy as np
N = int(input())
A = [int(a) for a in input().split()]
ans = A[0]

if 0 in A:
    print(0)
    exit()

for i in range(1, len(A)):
    if A[i] != 1:
        ans *= A[i]
    if ans > 10**18:
        print(-1)
        exit()

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

import sys
input = sys.stdin.readline

def main():
    s = input().rstrip()
    n = int(input())
    li = [input().split() for i in range(n)]
    a = 0 #先頭がどっちかという情報

    for x in li:
        if x[0] == "1":
            if a == 0:
                a = 1
            else:
                a = 0
        else:
            if (x[1] == "1" and a == 0) or (x[1] == "2" and a == 1):
                s = x[2] + s
            else:
                s = s + x[2]

    if a == 0: #先頭が前なら
        print(s)
    else: #先頭が後なら
        print(s[::-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

ans = input()
q = int(input())
top = 0
first = str()
last = str()

for i in range(q):
    li =input().split()
    if li[0] =="1":
        top = (top+1)%2
    else:
        if li[1] == "1":
            if top ==0:
                first += li[2]
            else:
                last += li[2]
        else:
            if top ==1:
                first += li[2]
            else:
                last += li[2]

if top == 0:
    ans = first[::-1] + ans + last
else:
    ans = last[::-1] + ans[::-1] + first

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

H, W = map(int, input().rstrip().split())
checked = [[True]*(W+2)]
checked += [[True] + [ch == "#" for ch in input().rstrip()] + [True]
            for i in range(H)]
checked += [[True]*(W+2)]

black_list = []
# 初期化
# 0 => 黒、 -1 => 白
for i in range(1, H+1):
    for j in range(1, W+1):
        if checked[i][j]:
            black_list.append((i, j))

# 黒の周辺4方向のうち、白だったら黒にする
ans = -1
while black_list:
    ans += 1
    tmp = []
    for x, y in black_list:
        # 上
        if not checked[x-1][y]:
            checked[x-1][y] = True
            tmp.append((x-1, y))
        # 下
        if not checked[x+1][y]:
            checked[x+1][y] = True
            tmp.append((x+1, y))
        # 左
        if not checked[x][y-1]:
            checked[x][y-1] = True
            tmp.append((x, y-1))

        # 右
        if not checked[x][y+1]:
            checked[x][y+1] = True
            tmp.append((x, y+1))

    black_list = tmp

print(ans)


### FIXED CODE ###

H, W = map(int, input().rstrip().split())
checked = [[True]*(W+2)]
checked += [[True] + [ch == "#" for ch in input().rstrip()] + [True]
            for i in range(H)]
checked.append([True]*(W+2))

black_list = []
# 初期化
# 0 => 黒、 -1 => 白
for i in range(1, H+1):
    for j in range(1, W+1):
        if checked[i][j]:
            black_list.append((i, j))

# 黒の周辺4方向のうち、白だったら黒にする
ans = -1
while black_list:
    ans += 1
    tmp = []
    for x, y in black_list:
        # 上
        if not checked[x-1][y]:
            checked[x-1][y] = True
            tmp.append((x-1, y))
        # 下
        if not checked[x+1][y]:
            checked[x+1][y] = True
            tmp.append((x+1, y))
        # 左
        if not checked[x][y-1]:
            checked[x][y-1] = True
            tmp.append((x, y-1))

        # 右
        if not checked[x][y+1]:
            checked[x][y+1] = True
            tmp.append((x, y+1))

    black_list = tmp

print(ans)