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

import sys
from collections import defaultdict
from heapq import heappush, heappop, heapify
input = sys.stdin.readline

INF = 10**12
n, m, s = map(int, input().split())
edges = defaultdict(lambda: defaultdict(lambda: [INF, INF]))
cd = []
max_a = 0

for i in range(m):
    u, v, a, b = map(int, input().split())
    max_a = max(max_a, a)
    edges[u-1][v-1] = [a, b]
    edges[v-1][u-1] = [a, b]

for i in range(n):
    c, d = map(int, input().split())
    cd.append([c, d])

# 解答ACする
# Dijakstraの状態を(頂点、所持している銀貨の枚数, cost)で持つ
SIZE = max_a * n + 1
# SIZE = 2550
if s > SIZE:
    s = SIZE
nodes = [[INF for _ in range(SIZE+1)] for _ in range(n)]
nodes[0][s] = 0

def dijakstra():
    goals = set({0})
    que = [(0, 0, s)]
    heapify(que)
    while 10**6 > len(que) > 0:
        if len(goals) >= n:
            break
        cost, num, silver = heappop(que)
        if num not in goals:
            goals.add(num)
        c, d = cd[num]
        s_tmp = min(SIZE, silver+c)
        if silver < SIZE and s_tmp != silver:
            heappush(que, (cost + d, num, s_tmp))
            nodes[num][s_tmp] = min(nodes[num][s_tmp], cost + d)
        for v in edges[num].keys():
            a, b = edges[num][v]
            if silver >= a:
                if nodes[v][silver-a] > cost + b:
                    heappush(que, (cost + b, v, silver - a))
                    nodes[v][silver - a] = min(nodes[v][silver - a], cost + b)

dijakstra()
for i in range(1, n):
    print(min(nodes[i]))



### FIXED CODE ###

ic=lambda i,c:i+c*50
n,m,s=map(int,input().split())
edge=[[]for _ in range(125100)]
for _ in range(m):
  u,v,a,b=map(int,input().split())
  u-=1
  v-=1
  for i in range(a,2501):
    edge[ic(u,i)].append((ic(v,i-a),b))
    edge[ic(v,i)].append((ic(u,i-a),b))
for i in range(n):
  c,d=map(int,input().split())
  for j in range(c,2501):
    edge[ic(i,j-c)].append((ic(i,j),d))
from heapq import heappop,heappush
def dijkstra(s,n,edge):
  inf=10**20
  ans=[inf]*n
  ans[s]=0
  h=[[0,s]]
  while h:
    c,v=heappop(h)
    if ans[v]<c:continue
    for u,t in edge[v]:
      if c+t<ans[u]:
        ans[u]=c+t
        heappush(h,[c+t,u])
  return ans
d=dijkstra(ic(0,min(2500,s)),125100,edge)
ans=[0]+[10**20]*(n-1)
for i in range(1,n):
  for j in range(2501):ans[i]=min(ans[i],d[ic(i,j)])
print(*ans[1:])
### BUGGY CODE ###

def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    # https://tjkendev.github.io/procon-library/python/string/z-algorithm.html
    def z_algo(S):
        N = len(S)
        A = [0] * N
        i = 1; j = 0
        A[0] = l = len(S)
        while i < l:
            while i + j < l and S[j] == S[i + j]:
                j += 1
            if not j:
                i += 1
                continue
            A[i] = j
            k = 1
            while l - i > k < j - A[k]:
                A[i + k] = A[k]
                k += 1
            i += k; j -= k
        return A
    N = I()
    S = SI()
    ans = 0
    for i in range(N):
        Z = z_algo(S[i:])
        for k,n in enumerate(Z[1:]):
            cur = min(k+1,n)
            ans = max(ans,cur)
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

"""

"""

### FIXED CODE ###

def z_algo(s):
    N = len(s)
    A = [0]*N
    i = 1; j = 0
    l = len(s)
    A[0] = l
    B = [0]*N
    while i < l:
        while i+j < l and s[j] == s[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k

    # 自身は含まない
    for i in range(N):
        B[i] = i
    #
    for i in range(N):
        A[i] = min(A[i],i)
#    print(B)
#    A[0] = 0
    return A

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = []

N = I()
S = str(input())
cur = int(0)
ans = int(0)
lenC = []

for i in range(N):
#    print(z_algo(S[i:]))
    lenC.append(max(z_algo(S[i:])))

#print(lenC)
ans = min(max(lenC),N//2)
print(ans)
### BUGGY CODE ###

import math,collections

def f(c):
  sum=0
  for i in c.values():
    sum+=g(i,2)
  return sum

def g(n,r):
  if n==0 or n==1:return 0
  else:return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

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

for i in range(n):
  l=k[0:i]
  l.extend(k[i+1:])
  c=collections.Counter(l)
#  print('l:',l,'c:',c)
  print(f(c))

### FIXED CODE ###

import collections
n=int(input())
k=list(map(int,input().split()))
c=collections.Counter(k)
ans=0

for i in c.values():
  ans+=i*(i-1)//2

for i in range(n):
  print(ans-c[k[i]]+1)
### BUGGY CODE ###

(N,D,A) = map(int,input().split())
l = []
for i in range(N):
    l.append([int(x) for x in input().split()])
    l.sort()
k = [0 for i in range(N)]
for i in range(N):
    k[i] = -((-l[i][1])//A)

m = [0] * N
ub = 0
cnt = 1
for i in range(N):
    if ub < N-1:
        while l[ub + 1][0]-l[i][0] <= 2*D:
            cnt += 1
            ub += 1
            if ub == N - 1:
                break
        m[i] = cnt
    else:
        m[i] = cnt
    cnt -= 1

ans = 0
al = 0
s = [0 for i in range(N)]
j = 0
for i in range(N):
    s[i] = max(k[i]-al,0)
    ans += s[i]
    al += s[i]
    if i < N-1:
        while j+m[j]-1 < i+1:
            al -= s[j]
            if j < N-1:
                j += 1

print(ans)

### FIXED CODE ###

(N,D,A) = map(int,input().split())
l = []
for i in range(N):
    l.append([int(x) for x in input().split()])
l.sort()
k = [0 for i in range(N)]
for i in range(N):
    k[i] = -((-l[i][1])//A)

m = [0] * N
ub = 0
cnt = 1
for i in range(N):
    if ub < N-1:
        while l[ub + 1][0]-l[i][0] <= 2*D:
            cnt += 1
            ub += 1
            if ub == N - 1:
                break
        m[i] = cnt
    else:
        m[i] = cnt
    cnt -= 1

ans = 0
al = 0
s = [0 for i in range(N)]
j = 0
for i in range(N):
    s[i] = max(k[i]-al,0)
    ans += s[i]
    al += s[i]
    if i < N-1:
        while j+m[j]-1 < i+1:
            al -= s[j]
            if j < N-1:
                j += 1

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

k,s=map(int,input().split(" "))
c=0
for i in range(k+1):
  for j in range(k+1):
    if i+j>s:
      break
    for l in range(k+1):
      if i+j+l==s:
        c+=1
      if i+j+l>s:
        break
print(c)       

### FIXED CODE ###

k,s=map(int,input().split(" "))
c=0
for i in range(k+1):
  for j in range(k+1):
    if s-i-j<=k and s-i-j>=0:
      c+=1

print(c)
### BUGGY CODE ###

n1 = [0] * 100005
n2 = [0] * 100005
v1 = []
v2 = []
n = int(input())
v = list(map(int, input().split()))
for i in range(n):
    if(i % 2 == 0):
        n1[v[i]] += 1
        v1.append(v[i])
    else:
        n2[v[i]] += 1
        v2.append(v[i])
v1s = list(set(v1))
v2s = list(set(v2))
v1s.append(0)
v2s.append(0)
ans = 10000000
for num1 in v1s:
    for num2 in v2s:
        if(num2 == num1):
            continue
        ans = min(ans, n//2-n2[num2] + n//2-n1[num1])
print(ans)


### FIXED CODE ###

n1 = [[j, 0] for j in range(100005)]
n2 = [[j, 0] for j in range(100005)]
n = int(input())
v = list(map(int, input().split()))
for i in range(n):
    if(i % 2 == 0):
        n1[v[i]][1] += 1
    else:
        n2[v[i]][1] += 1
n1 = sorted(n1, key=lambda x:x[1], reverse=True)
n2 = sorted(n2, key=lambda x:x[1], reverse=True)

if(n1[0][0] == n2[0][0]):
    ans1 = n//2 - n1[0][1] + n//2 - n2[1][1]
    ans2 = n//2 - n1[1][1] + n//2 - n2[0][1]
    ans = min(ans1, ans2)
    print(ans)
else:
    ans = n//2 - n1[0][1] + n//2 - n2[0][1]
    print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
input=sys.stdin.readline
    
def g(to_li, from_li, dp, n):
    # nにつくパスの最大長
    if dp[n] != -1:
        return dp[n]
    if n == 0:
        return 0
    val = max([g(to_li, from_li, dp, t)+1 for t in to_li[n]])
    dp[n] = val
    return val
    

def main():
    N, M = [int(n) for n in input().split()]
    from_li = [[] for i in range(N+2)] # from[i]:=点iからつながった点
    to_li = [[] for i in range(N+2)] # to[i]:=点iにつながる点
    for i in range(M):
        x, y = [int(n) for n in input().split()]
        from_li[x].append(y)
        to_li[y].append(x)
    parents = []
    children = []
    dp = [-1]*(N+2)
    for index, to in enumerate(to_li):
        if len(to) == 0 and index != N+1 and index != 0:
            from_li[0].append(index)
            to_li[index].append(0)
    for index, fr in enumerate(from_li):
        if len(fr) == 0 and index != 0 and index != N+1:
            to_li[N+1].append(index)
            from_li[index].append(N+1)
    
    print(g(to_li, from_li, dp, N+1) - 2)




if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
def main():
    n, m = [int(n) for n in input().split()]
    paths = [[] for i in range(n+1)]
    for i in range(m):
        x, y = [int(r) for r in input().split()]
        paths[x].append(y)
    dp = [-1]*(n+1)

    ans = 0
    for i in range(n+1):
        ans = max(ans, dfs(paths, dp, i))
    print(ans-1)
def dfs(paths, dp, n):
    # nから下の最大長
    length = 0
    for p in paths[n]:
        val=0
        if dp[p] != -1:
            val = dp[p]
        else:
            val = dfs(paths, dp, p)
        length = max(length, val)
    length += 1 # pからnまでの一本もしくはnから終点までの一本
    dp[n] = length
    return length

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

import math

n = int(input()) 
total = 0
for a in range(1, n + 1):
    for b in range(1, n + 1):
        for c in range(1, n + 1):
            total += math.gcd(math.gcd(a, b), c)

print(total)    

### FIXED CODE ###

import math

n = int(input()) 
total = 0
for a in range(1, n + 1):
    for b in range(1, n + 1):
        g = math.gcd(a ,b)
        if g == 1:
            total += n
        else:
            for c in range(1, n + 1):
                total += math.gcd(g, c)

print(total)
### BUGGY CODE ###

import sys
from itertools import permutations, combinations, combinations_with_replacement, product

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, K, *A = map(int, read().split())
K_ = K
comb = list(combinations(A, 2))
comb = sorted(comb, key=lambda p: p[0] * p[1])

tmp = comb[K - 1]
print(tmp[0] * tmp[1])


### FIXED CODE ###

import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


def count(x):
    cnt = 0
    if x >= 0:
        cnt += N * len(zero)
    cnt += np.searchsorted(A, x // pos, side='right').sum()
    cnt += N * len(neg) - np.searchsorted(A, -(-x // neg), side='left').sum()
    cnt -= np.count_nonzero(A * A <= x)

    return cnt // 2


N, K, *A = map(int, read().split())
A = np.array(A)
A.sort()

neg = A[A < 0]
zero = A[A == 0]
pos = A[A > 0]

r = 10**18
l = -r

while r - l > 1:
    m = (r + l) // 2
    if count(m) >= K:
        r = m
    else:
        l = m

print(r)
### BUGGY CODE ###

N = int(input())
a = [int(i) for i in input().split()]
A = 1
for i in range(N):
    A = A * a[i]
if A > 1000000000000000000:
    print(-1)
else:
    print(A)

### FIXED CODE ###

N = int(input())
a = [int(i) for i in input().split()]
A = 1
if 0 in a:
  print(0)
  exit()
for i in range(N):
  A = A * a[i]
  if A > 1000000000000000000:
    print(-1)
    exit()
print(A)
### BUGGY CODE ###

import sys

n,m=map(int,input().split())
a = [[int(i) for i in input().split()] for i in range(m)] 
c=[]

#print(a[0][0],a[0][1])
for i in range(m):
    if a[i][1] == n:
        c.append(a[i][0])
for i in range(m):
    if a[i][0]==1:
        if a[i][1] in c:
            print("POSSIBLE")
            sys.exit()
        
print("IMPOSSIBLE")


### FIXED CODE ###

import sys
n,m=map(int,input().split())
a = [[int(i) for i in input().split()] for i in range(m)] 
c=[]
s=[]
a = sorted(a,key = lambda x:-x[1])

#print(a[0][0],a[0][1])
for i in range(m):
    if a[i][1] < n:
        break
    else:
        c.append(a[i][0])
c=set(c)
a = sorted(a,key = lambda x:x[0])
for i in range(m):
    if a[i][0] > 1:
        break
    else:
        s.append(a[i][1])

    #if a[i][1] in c:
s=set(s)

for i in s:
    if i in c:
        print("POSSIBLE")
        sys.exit()

print("IMPOSSIBLE")
### BUGGY CODE ###

s = input()
mod = 10 ** 9 + 7
dp = []
for i in range(13):
    temp = [0] * len(s)
    dp.append(temp)
# j桁目がxのとき13で割ったあまり
def amari(x, j):
    if x != "?":
        x = int(x)
        return [(10 ** j % 13) * x]
    else:
        return [(10 ** j % 13) * x for x in range(10)]
for i in amari(s[-1], 0):
    dp[i][0] = 1
for i in range(1, len(s)):
    for j in range(13):
        for k in amari(s[-i-1], i):
            dp[j][i] += dp[(j - k) % 13][i - 1]
            dp[j][i] %= mod
print(dp[5][len(s) - 1])

### FIXED CODE ###

s = input()
n = len(s)
mod = 10 ** 9 + 7
amari = [1]
for i in range(n - 1):
    amari.append(amari[-1] * 10 % 13)
amari.reverse()
dp = [[0 for i in range(13)] for j in range(n + 1)]
dp[0][0] = 1
for i in range(n):
    for j in range(13):
        if s[i] == "?":
            temp = 0
            for k in range(10):
                temp += dp[i][(j - amari[i] * k) % 13]
                temp %= mod
            dp[i + 1][j] = temp
        else:
            num = int(s[i])
            dp[i + 1][j] = dp[i][(j - amari[i] * num) % 13]
print(dp[n][5])
### BUGGY CODE ###

# https://atcoder.jp/contests/abc125/tasks/abc125_c

import itertools
from collections import Counter
from collections import defaultdict
import bisect

memo = {}


def gcd(a, b):
    if a in memo:
        if b in memo[a]:
            return memo[a][b]
    ans = gcd_core(a, b)
    if a in memo:
        memo[a][b] = ans
    else:
        memo[a] = {}
        memo[a][b] = ans
    return ans


def gcd_core(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


def main():
    N = int(input())
    A = list(map(int, input().split()))

    answers = []
    # half
    m = N // 2
    ans1 = 0
    for i in range(m):
        ans1 = gcd(A[i], ans1)

    ans2 = 0
    for i in range(m, N):
        ans2 = gcd(A[i], ans2)

    for i in range(m, N):
        ans = ans1
        for j in range(m, N):
            if i == j:
                continue
            ans = gcd(A[j], ans)
        answers.append(ans)

    for i in range(m):
        ans = ans2
        for j in range(m):
            if i == j:
                continue
            ans = gcd(A[j], ans)
        answers.append(ans)

    print(max(answers))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# https://atcoder.jp/contests/abc125/tasks/abc125_c

import itertools
from collections import Counter
from collections import defaultdict
import bisect

memo = {}


def gcd(a, b):
    if a in memo:
        if b in memo[a]:
            return memo[a][b]
    ans = gcd_core(a, b)
    if a in memo:
        memo[a][b] = ans
    else:
        memo[a] = {}
        memo[a][b] = ans
    return ans


def gcd_core(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


def main():
    N = int(input())
    A = list(map(int, input().split()))

    ming = 0

    cand = []

    for i in range(N):
        temp = gcd(A[i], ming)
        # print(temp)
        if temp != ming:
            cand.append(i)
        ming = temp

    # print(index)

    answers = []
    for c in cand:
        ans1 = 0
        for i in range(N):
            if i != c:
                ans1 = gcd(A[i], ans1)
        answers.append(ans1)

    print(max(answers))


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

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

pushed = [False] * N
pushed[0] = True
now = 0
cnt = 0
while True:
    next = A[now] - 1
    if pushed[next]:
        cnt = -1
        break

    if next != 1:
        now = next
        cnt += 1

    if next == 1:
        cnt += 1
        break

print(cnt)


### FIXED CODE ###

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

pushed = [False] * N
pushed[0] = True
now = 0
cnt = 0

while True:
    next = A[now] - 1

    if pushed[next]:
        cnt = -1
        break

    if next == 1:
        cnt += 1
        break

    if next != 1:
        now = next
        pushed[next] = True
        cnt += 1


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

import sys
input = sys.stdin.readline

N = int(input())
A = input().split()

ans = {}
ans_all = 0
for x in set(A):
    m = A.count(x)
    ans_all += m * (m - 1) // 2


for x in A:
    m = A.count(x) - 1
    print(ans_all - (m + 1) * m // 2 + m * (m - 1) // 2)


### FIXED CODE ###

import sys
from collections import Counter
input = sys.stdin.readline

N = int(input())
A = input().split()
a = Counter(A)

ans_all = 0
for x in a.keys():
    m = a[x]
    ans_all += m * (m - 1) // 2

for x in A:
    m = a[x] - 1
    print(ans_all - m)
### BUGGY CODE ###

n,x=map(int,input().split())
y=sorted([abs(x-int(i)) for i in input().split()])

def True_array(s,k):
    for i in s:
        if i%k!=0:
            return False
    return True

l=y[0]
for i in range(l):
    if True_array(y,l-i):
        print(l-i)
        break


### FIXED CODE ###

from fractions import gcd
n,X=map(int,input().split())
x=list(map(int,input().split()))

def hoge():
    global n,x,X
    ret=abs(X-x[0])
    for i in range(1,n):
        ret=gcd(abs(X-x[i]),ret)
    return ret

print(hoge())
### BUGGY CODE ###

# C
import sys

N = int(input())
left = 0
right = N-1
ans_left = ''
ans_right = ''

cnt = 0

print(0)
cnt += 1
s = input()
ans_left = s

if s != "Vacant":
    print(N-1)
    cnt += 1
    s = input()
    ans_right = s


    
while s != "Vacant" and cnt < 20:
    
    # find which is unusual
    mid = (left + right) // 2
    print(m)
    cnt += 1
    s = input()
    
    m = (mid - left) % 2
    if m == 0:
        if ans_left != s:
            right = mid
            ans_right = s
        else:
            left = mid
            ans_left = s
    else:
        if ans_left == s:
            right = mid
            ans_right = s
        else:
            left = mid
            ans_left = s
    

### FIXED CODE ###

# C
import sys

N = int(input())
left = 0
right = N-1
ans_left = ''
ans_right = ''

cnt = 0

print(0)
cnt += 1
s = input()
ans_left = s

if s != "Vacant":
    print(N-1)
    cnt += 1
    s = input()
    ans_right = s


    
while s != "Vacant" and cnt < 20:
    
    # find which is unusual
    mid = (left + right) // 2
    print(mid)
    cnt += 1
    s = input()
    
    m = (mid - left) % 2
    if m == 0:
        if ans_left != s:
            right = mid
            ans_right = s
        else:
            left = mid
            ans_left = s
    else:
        if ans_left == s:
            right = mid
            ans_right = s
        else:
            left = mid
            ans_left = s
### BUGGY CODE ###

S = input()
Q = int(input())
for i in range(Q):
    q = list(input().split())
    if int(q[0])==1:
        S = S[::-1]
    else:
        if int(q[1])==1:
            S = q[2]+S
        else:
            S += q[2]
print(S)

### FIXED CODE ###

S = input()
Q = int(input())
s = 0
s1 = []
s2 = []
for i in range(Q):
    q = list(input().split())
    s += int(q[0])
    if q[0]=='2':
        s_i = s + int(q[1]) 
        if s_i%2 == 0:
            s1.append(q[2])
        else:
            s2.append(q[2])
s1 = ''.join(s1)
s2 = ''.join(s2)
s2 = s2[::-1]
S = s2 + S + s1
if s%2 == 0:
    print(S)
else:
    print(S[::-1])
### BUGGY CODE ###

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

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H,W=MAP()

que = deque()
# 右左上下  
directions = [(0,1),(0,-1),(1,0),(-1,0)]
# 四方に一回り大きいグリッドを作る
grid = list2d(H+2, W+2, '*')
for i in range(1,H+1):
    row = list(input())
    for j in range(1, W+1):
        grid[i][j] = row[j-1]
        if grid[i][j] == '#':
            que.append((i, j, 0))

# 移動距離メモ
memo=[[-1]*(W+2) for i in range(H+2)]
while len(que):
    cur=que.popleft()
    if memo[cur[0]][cur[1]]!=-1:
        continue
    memo[cur[0]][cur[1]]=cur[2]
    # 4方向見る
    for direction in directions:
        x,y=map(lambda x,y: x+y, cur, direction)
        # 壁と黒はスキップ
        if grid[x][y]=='*' or grid[x][y]=='#':
            continue
        # 白を埋める
        if grid[x][y]=='.':
            grid[x][y]='#'
            que.append((x, y, cur[2]+1))
ans=0
for i in range(1, H+1):
        ans=max(ans, max(memo[i]))
print(ans)


### FIXED CODE ###

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

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H,W=MAP()

que = deque()
# 右左上下  
directions = [(0,1),(0,-1),(1,0),(-1,0)]
# 四方に一回り大きいグリッドを作る
grid = list2d(H+2, W+2, '*')
for i in range(1,H+1):
    row = list(input())
    for j in range(1, W+1):
        grid[i][j] = row[j-1]
        if grid[i][j] == '#':
            que.append((i, j, 0))

# 移動距離メモ
memo=[[-1]*(W+2) for i in range(H+2)]
while len(que):
    cur=que.popleft()
    if memo[cur[0]][cur[1]]!=-1:
        continue
    memo[cur[0]][cur[1]]=cur[2]
    # 4方向見る
    for direction in directions:
        x=cur[0]+direction[0]
        y=cur[1]+direction[1]
        # 壁と黒はスキップ
        if grid[x][y]=='*' or grid[x][y]=='#':
            continue
        # 白を埋める
        if grid[x][y]=='.':
            grid[x][y]='#'
            que.append((x, y, cur[2]+1))
ans=0
for i in range(1, H+1):
        ans=max(ans, max(memo[i]))
print(ans)