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

N,K = map(int,input().split())
A = [int(input()) for _ in range(N)]
dp2 = [0] * N
for i in range(N):
    tmax = 0
    for j in range(i+1):
        if abs(A[i]-A[j]) <= K:
            tmax = max(tmax,dp2[j]+1)
    dp2[i] = tmax  

print(max(dp2))

### FIXED CODE ###

# Input Part
N,K = map(int,input().split())
A = [int(input()) for _ in range(N)]

Amax = 3*10**5

# N: 処理する区間の長さ
N0 = 2**(Amax-1).bit_length()
INF = 0
data = [INF]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])

        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

def main():
    for i in range(N):
        tmin = max(0,A[i]-K)
        tmax = min(Amax,A[i]+K)+1
        update(A[i],query(tmin,tmax)+1)
        #print(data)
    print(data[0])
main()
### BUGGY CODE ###

from itertools import permutations 
inf=10**10
n, m, r = map(int, input().split())
r=list(map(int, input().split()))
abc=[list(map(int, input().split())) for _ in range(m)]
d=[[inf]*n for i in range(n)]
for i in range(n):
    d[i][i]=0
for ai, bi, ci in abc:
    d[ai-1][bi-1]=ci
    d[bi-1][ai-1]=ci
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])
p=list(permutations(r))
print(min(sum(d[pi[i]-1][pi[i+1]-1] for i in range(len(r)-1)) for pi in p))

### FIXED CODE ###

from itertools import permutations
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
E = [list(map(int, input().split())) for _ in range(M)]
INF = 10 ** 9
d = [[INF for j in range(N)] for i in range(N)]
for i, j, c in E:
    d[i - 1][j - 1] = c
    d[j - 1][i - 1] = c
for k in range(N):
    for i in range(N - 1):
        for j in range(i, N):
            dk = d[i][k] + d[k][j]
            if d[i][j] > dk:
                d[i][j] = dk
                d[j][i] = dk
ans = 10 ** 9
for ri in permutations(r):
    x = 0
    for i in range(R - 1):
        x += d[ri[i] - 1][ri[i + 1] - 1]
    if ans > x:
        ans = x
print(ans)
### BUGGY CODE ###

n=int(input())
data_set=[0 for i in range(n)]
for i in range(n):
    a=list(map(int,input().split()))
    a.append(-1)
    data_set[i]=a
index=[0 for i in range(n)]
ans=-1
flag=True
now=[data_set[i][index[i]] for i in range(n)]
finished=[False for i in range(n)]
while flag:
    visited=[False for i in range(n)]
    sub=False
    for i in range(n):
        #nowリストのうち日ありからi+1番目のものについての一致条件の確認
        K=now[i]
        if now[K-1]==i+1:
            #交代できる時
            if not (visited[i] or visited[K-1]):
                if not (finished[i] or finished[K-1]):
                    visited[i]=True
                    visited[K-1]=True
                    index[i]+=1
                    index[K-1]+=1
                    sub=True
                    if index[i]==n-1:
                        finished[i]=True
                    else:
                      	now[i]=data_set[i][index[i]]
                    if index[K-1]==n-1:
                        finished[K-1]=True
                    else:
                        now[K-1]=data_set[K-1][index[K-1]]
    if not sub:
        flag=False
    ans+=1

judge=True
for i in range(n):
  if finished[i]==False:
    judge=False
    break
if judge:
  print(ans)
else:
  print(-1)


### FIXED CODE ###

n=int(input())
import time
T=time.time()
data_set=[0 for i in range(n)]
for i in range(n):
    a=list(map(int,input().split()))
    a.append(-1)
    data_set[i]=a
index=[0 for i in range(n)]
ans=-1
flag=True
semi=False
now=[data_set[i][index[i]] for i in range(n)]
finished=[False for i in range(n)]
while flag:
    visited=[False for i in range(n)]
    sub=False
    for i in range(n):
        #nowリストのうち日ありからi+1番目のものについての一致条件の確認
        K=now[i]
        if now[K-1]==i+1 and not(visited[i] or visited[K-1]) and not(finished[i] or finished[K-1]):
                    visited[i]=True
                    visited[K-1]=True
                    index[i]+=1
                    index[K-1]+=1
                    sub=True
                    if index[i]==n-1:
                        finished[i]=True             
                    now[i]=data_set[i][index[i]]
                    if index[K-1]==n-1:
                        finished[K-1]=True                   
                    now[K-1]=data_set[K-1][index[K-1]]
    if not sub:
        flag=False
    if time.time()-T>1.5:
        flag=False
        semi=True
    ans+=1
judge=True
for i in range(n):
  if finished[i]==False:
    judge=False
    break
if judge:
  print(ans)
else:
  if not semi:
    print(-1)
  if semi:
    print(499500)
### BUGGY CODE ###

N = int(input())
S = list(input())

accLeft = [0]
accRight = [0]

tmp = 0
for c in S:
  tmp += int(c == 'W')
  accLeft.append(tmp)
accLeft.append(0)

tmp = 0
for c in S[::-1]:
  tmp += int(c == 'E')
  accRight = [tmp] + accRight
accRight = [0] + accRight

print(min([accLeft[i-1] + accRight[i+1] for i in range(1, N+1)]))

### FIXED CODE ###

N = int(input())
S = list(input())

accLeft = [0]
accRight = [0]

tmp = 0
for c in S:
  tmp += int(c == 'W')
  accLeft.append(tmp)
accLeft.append(0)

tmp = 0
for c in S[::-1]:
  tmp += int(c == 'E')
  accRight.append(tmp)
accRight.append(0)
accRight = accRight[::-1]

print(min([accLeft[i-1] + accRight[i+1] for i in range(1, N+1)]))
### BUGGY CODE ###

a,b,k = map(int,input().split())
List = [x for x in range(a,b+1) if x <= a+k-1 or x >= b-k+1]
for x in List: print(x)

### FIXED CODE ###

a,b,k = map(int,input().split())
X = [i for i in range(a,a+k) if i <= b]
Y = [i for i in range(b-k+1,b+1) if a <= i]
Z = sorted(list(set(X+Y)))
for z in Z: print(z)
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]

cnt = 0

for i in range(n):
    i_ = (n+i)%n
    for k in range(n):
        for l in range(n):
            if s[(i_+k)%n][l] != s[(i_+l)%n][k]:
                break
        else:
            continue
        break
    else:
        cnt += 1

print(cnt*n)

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]

cnt = 0

def is_symmetry(s_):
    for k in range(n):
        for l in range(k+1, n):
            if s_[k][l] != s_[l][k]:
                return False
    return True

for i in range(n):
    i_ = (n+i)%n
    s_ = s[i_:] + s[:i_]
    if is_symmetry(s_):
        cnt += 1

print(cnt*n)
### BUGGY CODE ###

n = int(input())
a_list = list(map(int, input().split()))
# print(a_list)
a_set = set(a_list)
length_dict = {}
total_num = 0
for elm in a_set:
    cur_list = [ind for ind in range(n) if a_list[ind] == elm]
    length_dict[elm] = len(cur_list)
    total_num += int(length_dict[elm]*(length_dict[elm]-1)/2)
difference = {}
for elm in a_set:
    difference[elm] = int(length_dict[elm]*(length_dict[elm]-1)/2) - int((length_dict[elm]-1)*(length_dict[elm]-2)/2)


# print(num_dict0, num_dict1)
for ind in range(n):
    elm = a_list[ind]
    print(total_num-difference[elm])

### FIXED CODE ###

n = int(input())
a_list = list(map(int, input().split()))
# print(a_list)
a_set = set(a_list)
length_dict = {}
for elm in a_set:
    length_dict[elm] = 0    

for ind in range(n):
    elm = a_list[ind]
    length_dict[elm] += 1

total_num = 0
for elm in a_set:
    total_num += int(length_dict[elm]*(length_dict[elm]-1)/2)
difference = {}
for elm in a_set:
    difference[elm] = int(length_dict[elm]*(length_dict[elm]-1)/2) - int((length_dict[elm]-1)*(length_dict[elm]-2)/2)


# print(num_dict0, num_dict1)
for ind in range(n):
    elm = a_list[ind]
    print(total_num-difference[elm])
### BUGGY CODE ###

n = int(input())
a_list = list(map(int, input().split()))
count = 0
Jlist = []
for j in range(2, n+1):
    if j > a_list[j-1]:
        for i in range(1, j):
            if j -a_list[j-1] == a_list[i-1] + i:
                count += 1

print(count)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
count = 0
d={}
for i in range(n):
    if i - a[i] in d:
        count+=d[i - a[i]]
    if i + a[i] in d:
        d[i+a[i]] += 1
    else:
        d[i+a[i]] = 1

print(count)
### BUGGY CODE ###

import sys


def prepare(n):
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i % MOD
    inv = [1] * (n + 1)
    inv[n] = pow(fact[n], MOD - 2, MOD)
    for i in range(n - 1, 0, -1):
        inv[i] = inv[i + 1] * (i + 1) % MOD
    return fact, inv


MOD = 10 ** 9 + 7
h, w, n = map(int, input().split())
walls = [tuple(map(int, line.split())) for line in sys.stdin.readlines()]
walls.append((1, 1))
walls.append((h, w))
walls.sort()
fact, inv = prepare(h + w)
dp = [1]
for i, (cy, cx) in enumerate(walls[1:], start=1):
    res = 0
    for j, (py, px) in enumerate(walls[:i]):
        if cx < px:
            continue
        dy, dx = cy - py, cx - px
        res -= dp[j] * fact[dy + dx] % MOD * inv[dy] % MOD * inv[dx] % MOD
        res %= MOD
    dp.append(res)
print(-dp[-1] % MOD)


### FIXED CODE ###

import sys


def prepare(n):
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i % MOD
    inv = [1] * (n + 1)
    inv[n] = pow(fact[n], MOD - 2, MOD)
    for i in range(n - 1, 0, -1):
        inv[i] = inv[i + 1] * (i + 1) % MOD
    return fact, inv


MOD = 10 ** 9 + 7
h, w, n = map(int, input().split())
walls = [tuple(map(int, line.split())) for line in sys.stdin.readlines()]
walls.append((1, 1))
walls.append((h, w))
walls.sort()
fact, inv = prepare(h + w)
dp = [1]
for i, (cy, cx) in enumerate(walls[1:], start=1):
    res = 0
    for j, (py, px) in enumerate(walls[:i]):
        if cx < px:
            continue
        dy, dx = cy - py, cx - px
        res -= dp[j] * fact[dy + dx] % MOD * inv[dy] % MOD * inv[dx] % MOD
        res %= MOD
    dp.append(res)
print(-dp[-1] % MOD)
### BUGGY CODE ###


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

for i in range(N):
    tmp = A[0:i] + A[i + 1:len(A)]
    print(max(tmp))


### FIXED CODE ###


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

srtd = sorted(A)
for i in range(N):
    # print(str(i) + '番目')
    if srtd[-1] != A[i]:
        print(srtd[-1])
    else:
        print(srtd[-2])
### BUGGY CODE ###

from math import factorial
n,m = map(int,input().split())
if abs(n-m) > 1:
  print(0)
elif n == m:
  ans = 2*factorial(n)**2
  print(ans)
else:
  ans = factorial(n)*factorial(m)
  print(ans)

### FIXED CODE ###

from math import factorial
n,m = map(int,input().split())
if abs(n-m) > 1:
  print(0)
elif n == m:
  ans = 2*(factorial(n)%(10**9+7))**2%(10**9+7)
  print(ans)
else:
  ans = (factorial(n)%(10**9+7))*(factorial(m)%(10**9+7))%(10**9+7)
  print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
minus = [-x for x in a if x < 0]
plus = [x for x in a if x >= 0]

minus.sort()
plus.sort()

def cnt(x):
    ans = 0
    if x < 0:
        x = -x
        r = 0
        for num in minus[::-1]:
            while r < len(plus) and plus[r] * num < x:
                r += 1
            ans += len(plus) -  r
        return ans

    r = 0
    for num in minus[::-1]:
        if num * num <= x: ans -= 1
        while r < len(minus) and minus[r] * num <= x:
            r += 1
        ans += r
    r = 0
    for num in plus[::-1]:
        if num * num <= x: ans -= 1
        while r < len(plus) and plus[r] * num <= x:
            r += 1
        ans += r
    ans //= 2
    ans += len(minus) * len(plus)
    return ans

bottom = 0
top = 2*(10**18) + 2


while top - bottom > 1:
    mid = (top + bottom) // 2
    if cnt(mid - 10**18-1) < k:
        bottom = mid
    else:
        top = mid

print(int(top - 10**18-1))


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
minus = [-x for x in a if x < 0]
plus = [x for x in a if x >= 0]

minus.sort()
plus.sort()

def cnt(x):
    ans = 0
    if x < 0:
        x = -x
        r = 0
        for num in minus[::-1]:
            while r < len(plus) and plus[r] * num < x:
                r += 1
            ans += len(plus) -  r
        return ans

    r = 0
    for num in minus[::-1]:
        if num * num <= x: ans -= 1
        while r < len(minus) and minus[r] * num <= x:
            r += 1
        ans += r
    r = 0
    for num in plus[::-1]:
        if num * num <= x: ans -= 1
        while r < len(plus) and plus[r] * num <= x:
            r += 1
        ans += r
    ans //= 2
    ans += len(minus) * len(plus)
    return ans

bottom = 0
top = 2*(10**18) + 2


while top - bottom > 1:
    mid = (top + bottom) // 2
    if cnt(mid - 10**18-1) < k:
        bottom = mid
    else:
        top = mid

print(int(top - 10**18-1))
### BUGGY CODE ###

MOD = 10 ** 9 + 7
S = input()

dp = [0] * 13
dp[0] = 1

for s in S:
    prev = dp
    dp = [0] * 13
    if s == '?':
        add = range(10)
    else:
        add = [int(s)]
    for i in range(13):
        for a in add:
            dp[(i*10+a)%13] += prev[i]
    dp = [x % MOD for x in dp]
print(dp[5])

### FIXED CODE ###

MOD = 10 ** 9 + 7
S = input()

dp = [0] * 13
dp[0] = 1

for s in S:
  prev = [x for x in dp]
  dp = [0] * 13
  if s == '?':
    add = range(10)
  else:
    add = [int(s)]
  for i in range(13):
    for x in add:
      dp[(10*i+x)%13] += prev[i]
  dp = [x % MOD for x in dp]
  
print(dp[5])
### BUGGY CODE ###

def remain(pos,length):
  p=pos
  if p<0 or p>=length:
    return False
  for c,d in moves:
    if s[p]==c:
      if d=='L':
        p-=1
      if d=='R':
        p+=1
    if p<0 or p>=length:
      return False
  return True

n,q=map(int,input().split())
s=input()
moves=[list(map(str,input().split())) for _ in range(q)]
l=-1
r=n
while r-l!=1:
  mid=(l+r)//2
  if remain(mid,n)==True:
    r=mid
  else:
    l=mid
remain_left=r
l=remain_left
r=n
while r-l!=1:
  mid=(l+r)//2
  if remain(mid,n)==True:
    l=mid
  else:
    r=mid
remain_right=l
print(remain_right-remain_left+1)

### FIXED CODE ###

def remain(pos,length):
  p=pos
  for c,d in moves:
    if s[p]==c:
      if d=='L':
        p-=1
      if d=='R':
        p+=1
    if p<0 or p>=length:
      return False
  return True

n,q=map(int,input().split())
s=input()
moves=[list(map(str,input().split())) for _ in range(q)]
l=-1
r=n
while r-l!=1:
  mid=(l+r)//2
  if remain(mid,n)==True:
    r=mid
  else:
    l=mid
remain_left=r
if remain_left==n:
  print(0)
  exit()
l=remain_left
r=n
while r-l!=1:
  mid=(l+r)//2
  if remain(mid,n)==True:
    l=mid
  else:
    r=mid
remain_right=l
print(remain_right-remain_left+1)
### BUGGY CODE ###

H, W = map(int, input().split())
S = []
for i in range(H):
  cha = str(input())
  s = [i for i in cha]
  S.append(s)
  
def side(li, h, w):
  left = w
  right = w
  i = 0
  if w == 0:
    left = 0
  else:
    while S[h][w-i] == '.':
      if i == w:
        left = 0
        break
      i += 1
    else:
      left = w-i+1
  i = 0
  if w == len(S[h])-1:
    right = len(S[h])-1
  else:
    while S[h][w+i] == '.':
      if w+i == len(S[h])-1:
        right = len(S[h])-1
        break
      i += 1
    else:
      right = w+i-1
  return right-left+1

def front(S, h, w):
  up = h
  down = h
  i = 0
  if h == 0:
    up = 0
  else:
    while S[h-i][w] == '.':
      if i == h:
        up = 0
        break
      i += 1
    else:
      up = h-i+1
  i = 0
  if h == len(S)-1:
    down = len(S)-1
  else:
    while S[h+i][w] == '.':
      if h+i == len(S)-1:
        down = len(S)-1
        break
      i += 1
    else:
      down = h+i-1
  return down-up+1

ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == '.':
      ans =  max(ans, side(S, i, j) + front(S, i, j) - 1)
print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
S = []
l1 = []
for i in range(H):
  s = str(input())
  S.append(s)
  tmp = []
  cnt = 0
  flag = False
  for j in s:
    if flag:
      if j == '.':
        cnt += 1
      else:
        for k in range(cnt):
          tmp.append(cnt)
        cnt = 0
        tmp.append(0)
        flag = False
    else:
      if j == '.':
        flag = True
        cnt += 1
      else:
        tmp.append(0)
  if cnt > 0:
    for k in range(cnt):
      tmp.append(cnt)
  l1.append(tmp)

l2 = []
for i in range(W):
  tmp = []
  cnt = 0
  flag = False
  for j in range(H):
    x = S[j][i]
    if flag:
      if x == '.':
        cnt += 1
      else:
        for k in range(cnt):
          tmp.append(cnt)
        cnt = 0
        tmp.append(0)
        flag = False
    else:
      if x == '.':
        flag = True
        cnt += 1
      else:
        tmp.append(0)
  if cnt > 0:
    for k in range(cnt):
      tmp.append(cnt)
  l2.append(tmp)

ans = [[0]*W for i in range(H)]
m = 0
for i in range(H):
  for j in range(W):
    if (l1[i][j]>0) and (l2[j][i]>0):
      ans[i][j] = l1[i][j] + l2[j][i] - 1
    else:
      ans[i][j] = l1[i][j] + l2[j][i]
    m = max(m, ans[i][j])
print(m)
### BUGGY CODE ###

import math

big = 10**9 + 7

N = int(input())
A = list(map(int, input().split()))
num = A[0]
for i in range(1, N):
    num = num * A[i] // math.gcd(num, A[i])

res = 0
for a in A:
    res += num//a % big

print(res%big)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import math

def main():
    big = 10 ** 9 + 7

    N = int(input())
    A = list(map(int, input().split()))
    num = A[0]
    for i in range(1, N):
        num = num * A[i] // math.gcd(num, A[i])

    res = 0
    for a in A:
        res += num // a

    print(res % big)

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

a,b = map(int,input().split())
ans = 0
for i in range(a,b+1):
    ans = ans ^ i
    # print(bin(ans))
print(ans)




### FIXED CODE ###

a,b = map(int,input().split())
if a==0:
    print(b)
    exit()
ab = bin(a-1)[2:]
bb = bin(b)[2:]
# print(ab)
# print(bb)
sa = []
sb = []
if int(bb[-1]):
    sb = [1]
else:
    for i in bb:
        sb += [int(i)]
if a>0:
    if int(ab[-1]):
        sa = [1]
    else:
        for i in ab:
            # print(2)
            sa += [int(i)]
sa[-1] = (a//2)%2
sb[-1] = ((b+1)//2)%2
# print(sa)
# print(sb)
# print(ab)
ta = "".join([str(i) for i in sa])
tb = "".join([str(i) for i in sb])
ta = int(ta,2)
tb = int(tb,2)
# print(ta)
# print(tb)
ans = ta^tb
# print(ta)
# print(tb)
print(ans)
### BUGGY CODE ###

n=int(input())
l=[int(i) for i in input().split()]
l.extend(l)
from fractions import gcd
from functools import reduce
ans=1
def gcd_list(numbers):
    return reduce(gcd, numbers)
for i in range(n):
  ans=max(ans,gcd_list(l[i:i+n-1]))
print(ans)
  

### FIXED CODE ###

n=int(input())
l=[int(i) for i in input().split()]
l.extend(l)
from fractions import gcd
lst1=[l[0]]
lst2=[l[-1]]
for i in range(1,n):
    lst1.append(gcd(lst1[-1],l[i]))
for i in range(n-1,-1,-1):
    lst2.append(gcd(lst2[-1],l[i]))
lst2=lst2[::-1]
lst=[]
for i in range(n):
    if i==0:
        lst.append(lst2[1])
    if i==n-1:
        lst.append(lst1[-2])
    else:
        lst.append(gcd(lst1[i-1],lst2[i+1]))
print(max(lst))
### BUGGY CODE ###

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

count = 0

x = 0
while (x <= K):
    y = 0
    while (y <= K):
        if S - (x + y) <= K and 0 <= S - (x + y):
            count += 1
        y += 1
    x += 1



print(count)

### FIXED CODE ###

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

count = 0

x = 0
while (x <= K):
    y = 0
    while (y <= K):
        if 0 <= S - (x + y) <= K:
            count += 1
        y += 1
    x += 1



print(count)
### BUGGY CODE ###

import sys
from math import ceil, log2

input = sys.stdin.readline

def main():
    MOD = 10**9 + 7
    
    N = int(input())
    A = list(map(int, input().split()))
    K = ceil(log2(max(max(A), 1)))
    nums = [[0,0] for i in range(K)]
    ks = [(i, 2**i) for i in range(K)]
    
    for i, a in enumerate(A):
        for j, k in ks:
            n = a & k > 0
            nums[j][n] += 1
    ans = 0
    
    for a in A:
        for j, k in ks:
            n = a & k > 0
            nums[j][n] -= 1
            ans += k * nums[j][not n] % MOD
            
    print(ans%MOD)

if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np

def main():
    N = int(input())
    A = np.array(list(map(int, input().split())))
    ans = 0
    MOD = 10**9+7
    k = 1
    x = np.max(A)
    n = 1 if x == 0 else int(np.log2(x))+1

    for i in range(n):
        c = np.count_nonzero(A%2)
        A >>= 1
        ans = (ans + c * (N-c) * k) % MOD
        k = (2*k) % MOD

    print(ans)

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

# coding:utf-8

Black = "#"
White = "."

dir_x = [1, 0, -1, 0]
dir_y = [0, 1, 0, -1]


def main():
    H, W = map(int, input().split())
    masu = []
    for i in range(H):
        masu.append(input().rstrip())
    step = 0
    count = W*H
    memo = [[-1]*W for i in range(H)]

    for y in range(H):
        for x in range(W):
            if masu[y][x] == Black:
                memo[y][x] = 0
                count -= 1

    while count > 0:
        temp_step = step
        step += 1
        for y in range(H):
            for x in range(W):
                if memo[y][x] == temp_step:
                    for i in range(4):
                        temp_x = x + dir_x[i]
                        temp_y = y + dir_y[i]
                        if temp_x >= 0 and temp_x < W and temp_y >= 0 and temp_y < H and memo[temp_y][temp_x] < 0:
                            memo[temp_y][temp_x] = step
                            count -= 1
    # print(memo)
    print(step)


if __name__ == "__main__":
    main()


### FIXED CODE ###

# coding:utf-8

Black = "#"
White = "."

dir_x = [1, 0, -1, 0]
dir_y = [0, 1, 0, -1]


def main():
    H, W = map(int, input().split())
    step = 0
    count = W*H
    memo = [[-1]*W for i in range(H)]
    steplist = []

    for y in range(H):
        temp_in = input()
        for x in range(W):
            if temp_in[x] == Black:
                memo[y][x] = 0
                count -= 1
                steplist.append([y, x])

    while count > 0:
        step += 1
        next_list = []
        for l_yx in steplist:
            for i in range(4):
                temp_x = l_yx[1] + dir_x[i]
                temp_y = l_yx[0] + dir_y[i]
                if temp_x >= 0 and temp_x < W and temp_y >= 0 and temp_y < H:
                    if memo[temp_y][temp_x] < 0:
                        memo[temp_y][temp_x] = step
                        count -= 1
                        next_list.append([temp_y, temp_x])
        steplist = next_list
    print(step)


if __name__ == "__main__":
    main()