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

a,b=map(int,input().split())
h=[int(i) for i in input().split()]
ansl=[]
for i in range(b):
    c,d=map(int,input().split())
    ch=h[c-1]
    dh=h[d-1]
    if ch==dh:
        ansl.append(c-1)
        ansl.append(d-1)
        ansl=list(set(ansl))
    else:
        if ch<dh:
            ansl.append(c-1)
        else:
            ansl.append(d-1)
        ansl=list(set(ansl))
print(a-len(ansl))

### FIXED CODE ###

a,b=map(int,input().split())
h=[int(i) for i in input().split()]
ansl=[]
dic={i:0 for i in range(a)}
aans=[]
for i in range(b):
    c,d=map(int,input().split())
    if True:
        ch=h[c-1]
        dh=h[d-1]
        if ch==dh:
            if dic[c-1]==0:
                ansl.append(c-1)
                dic[c-1]+=1
            if dic[d-1]==0:
                ansl.append(d-1)
                dic[d-1]+=1
        else:
            if ch<dh:
                if dic[c-1]==0:
                    ansl.append(c-1)
                    dic[c-1]+=1
            else:
                if dic[d-1]==0:
                    ansl.append(d-1)
                    dic[d-1]+=1
        aans.append([c,d])
print(a-len(ansl))
### BUGGY CODE ###

X = str(input())

for i in range (0, int(len(X)/2)+1):
	X = X.replace("ST", '')
	if X == X.replace("ST", ''):
		print(len(X))
		exit() 

print(len(X))

### FIXED CODE ###

X = str(input())

Tn = 0
Sn = 0
Nagasa = len(X)

for i in range (0, Nagasa):
	if X[i] == 'T':
		if Sn == 0:
			Tn+=1
		else:
			Sn-=1
	else:
		Sn+=1

print(2*Tn)
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, k  = MAP()
p = LIST()

def kitai(a):
    tmp = 0
    # for a in A:
    tmp = 1/a * (1/2 * a * (a+1))
    return tmp
    

ans = 0
# A = []
c = 0
B = []
for i in range(n-k+1):
    A = p[i:i+k]
    if c != max(c, sum(A)):
        c = sum(A)
        C = deepcopy(A)
    B.append(A)

# print(C)

for a in C:
    # print(a)
    ans += kitai(a)
# ans = max(ans, k)
print(ans)

# for A in B:
#     k = 0
#     for a in A:
#         # print(a)
#         k += kitai(a)
#     ans = max(ans, k)
# print(ans)







### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, k  = MAP()
p = LIST()

def kitai(a):
    tmp = 0
    # for a in A:
    tmp = 1/a * (1/2 * a * (a+1))
    return tmp
    
ans = 0
max_index = 0
# left = 0
# right = k
max_ruiseki = sum(p[0:k])
now_ruiseki = 0
ruiseki = [max_ruiseki]
for left in range(n-k+1):
    if left != 0:
        right = k + left 
        # print(left-1, p[left-1])
        
        # print(right-1 ,p[right-1])
        new_ruiseki = ruiseki[left-1] + p[right-1] - p[left-1]
        ruiseki.append(new_ruiseki)

# print(ruiseki)
m = 0
max_index = 0
for i in range(len(ruiseki)):
    if m != max(m, ruiseki[i]):
        m = ruiseki[i]
        index = i

# print(index)

A = p[index:index+k]
    # now_ruiseki = max_ruiseki
for a in A:
    ans += kitai(a)
print(ans)

    



# next_ruiseki = 0
# for i in range(n-k+1):
#     next_ruiseki = ruiseki    
#     ruiseki = max(ruiseki)


    # A
    # A = p[i:i+k]
    # if c != max(c, sum(A)):
    #     c = sum(A)
    #     C = deepcopy(A)
# for a in C:
#     ans += kitai(a)
# print(ans)
### BUGGY CODE ###

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]

def f(i, w, v):
  if i == n:
    return v
  if d[i][0] <= w:
    return max(f(i + 1, w - d[i][0], v + d[i][1]), f(i + 1, w, v))
  else:
    return f(i + 1, w, v)  
print(f(0, w, 0))


### FIXED CODE ###

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys()))
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        t[nw] = nv
    else:
      t[nw] = nv
print(max(t.values()))
### BUGGY CODE ###

n,d,a = map(int,input().split())
raw = []
event = []
for i in range(n):
  x,h = map(int,input().split())
  event.append([x,0,i,h])
for i in range(n):
  tmp = event[i][0] + 2 * d
  event.append([tmp,1,i])
event.sort()
#print(event)
use = [0 for _ in range(n)]
now = 0
ans = 0
for j in range(2*n):
  x,d,i = event[j][:3]
  if d == 0:
    h = event[j][3]
    if h <= now * a:
      pass
    else:
      h -= now * a
      tmp = (h-1)//a+1
      now += tmp
      use[i] = tmp
      ans += tmp
  else:
    now -= use[i]
  #print(x,d,i,ans,now)
print(ans)

### FIXED CODE ###

n,d,a = map(int,input().split())
raw = []
event = []
for i in range(n):
  x,h = map(int,input().split())
  event.append([x,0,i,h])
for i in range(n):
  tmp = event[i][0] + 2 * d
  event.append([tmp,1,i])
event.sort()
#print(event)
use = [0 for _ in range(n)]
now = 0
ans = 0
for j in range(2*n):
  x,d,i = event[j][:3]
  if d == 0:
    h = event[j][3]
    if h <= now * a:
      pass
    else:
      h -= now * a
      tmp = (h-1)//a+1
      now += tmp
      use[i] = tmp
      ans += tmp
  else:
    now -= use[i]
  #print(x,d,i,ans,now)
print(ans)
### BUGGY CODE ###

n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 13

if n > 15:
    print(re)
    
costs = [INF] * n
for i, (x, y, c) in enumerate(info):
    costs[i] = c * min(abs(x), abs(y))


x_dir = [[INF] * (1 << n) for i in range(n)]
y_dir = [[INF] * (1 << n) for i in range(n)]

for bit_state in range(1 << n):
    for i, (xi, yi, c) in enumerate(info):
        x_dir[i][bit_state] = min(costs[i], x_dir[i][bit_state])
        y_dir[i][bit_state] = min(costs[i], y_dir[i][bit_state])
        if not((bit_state >> i) & 1):
            continue
        for j, (xj, yj, c) in enumerate(info):
            x_dir[j][bit_state] = min(x_dir[j][bit_state], c * abs(yi - yj))
            y_dir[j][bit_state] = min(y_dir[j][bit_state], c * abs(xi - xj))


ans = [INF] * (n + 1)
for bit_state in range((1 << n) - 1):
    x_bit = bit_state
    cnt = bin(bit_state).count("1")
    while x_bit >= 0:
        x_bit &= bit_state
        # bit_stateの下位集合sub_stateの列挙
        # 処理はじめ
        y_bit = bit_state - x_bit
        tmp = 0
        for i in range(n):
            tmp += min(x_dir[i][x_bit], y_dir[i][y_bit])
        ans[cnt] = min(ans[cnt], tmp)
        # 処理おわり
        x_bit -= 1

ans[-1] = 0
for res in ans:
    print(res)

### FIXED CODE ###

#import random


n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 13

#n = 15
#info = []
#for i in range(n):
#    info.append([random.randint(-10000, 10000), random.randint(-10000, 10000), random.randint(1, 1000000)])


costs = [INF] * n
for i, (x, y, c) in enumerate(info):
    costs[i] = c * min(abs(x), abs(y))

OFFSET = n
x_dir = [INF] * ((1 << n) * OFFSET)
y_dir = [INF] * ((1 << n) * OFFSET)


for bit_state in range(1 << n):
    for i, (xi, yi, c) in enumerate(info):
        x_dir[bit_state * OFFSET + i] = min(costs[i], x_dir[bit_state * OFFSET + i])
        y_dir[bit_state * OFFSET + i] = min(costs[i], y_dir[bit_state * OFFSET + i])
        if not((bit_state >> i) & 1):
            continue
        for j, (xj, yj, c) in enumerate(info):
            x_dir[bit_state * OFFSET + j] = min(x_dir[bit_state * OFFSET + j], c * abs(yi - yj))
            y_dir[bit_state * OFFSET + j] = min(y_dir[bit_state * OFFSET + j], c * abs(xi - xj))


ans = [INF] * (n + 1)
for bit_state in range((1 << n) - 1):
    x_bit = bit_state
    cnt = bin(bit_state).count("1")
    while x_bit >= 0:
        x_bit &= bit_state
        # bit_stateの下位集合sub_stateの列挙
        # 処理はじめ
        y_bit = bit_state - x_bit
        tmp = 0
        for i in range(n):
            tmp += min(x_dir[x_bit * OFFSET + i], y_dir[y_bit * OFFSET + i])
        ans[cnt] = min(ans[cnt], tmp)
        # 処理おわり
        x_bit -= 1

ans[-1] = 0
for res in ans:
    print(res)
### BUGGY CODE ###

import sys
from collections import deque
import copy
import heapq
INF = 10 ** 16


def dijkstra(n, town, k, start):
    d = []
    used = []
    for i in range(n):
        d.append(INF)
        used.append(False)
    d[start] = 0
    # 都市kで交換した時の円またはスヌークのの最小値
    while True:
        v = -1
        for u in range(n):
            if not used[u] and (v == -1 or d[u] < d[v]):
                v = u
        if v == -1:
            break
        used[v] = True
        for u in range(len(town[v])):
            if d[v] + town[v][u][k] < d[town[v][u][0]]:
                d[town[v][u][0]] = d[v] + town[v][u][k]
    return d


def main():
    n, m, s, t = map(int, input().split())
    s -= 1
    t -= 1
    money = 10 ** 15
    town = []

    for i in range(n):
        town.append([])
    for i in range(m):
        fro, to, a, b = map(int, input().split())
        fro -= 1
        to -= 1
        town[fro].append((to, a, b))
        town[to].append((fro, a, b))
    
    a = dijkstra(n, town, 1, s)
    b = dijkstra(n, town, 2, t)

    total = []
    for i in range(n):
        heapq.heappush(total, (a[i] + b[i], i + 1))
    count = 0
    while count < n:
        mon, year = heapq.heappop(total)
        if year > count:
            heapq.heappush(total, (mon, year))
            print(money - mon)
            count += 1
        else:
            continue
    

if __name__ == '__main__':
    main()


### FIXED CODE ###

from heapq import heapify, heappop, heappush


def dijkstra(n, train, start):
    d = []
    queue = []
    INF = 10 ** 16
    for i in range(n):
        d.append(INF)
    d[start] = 0
    heapify(queue)
    heappush(queue, (0, start))
    # 都市kに行く時の円またはスヌークのの最小値
    while len(queue) != 0:
        distance, v = heappop(queue)
        if d[v] < distance:
            continue
        for u in range(len(train[v])):
            if d[train[v][u][0]] > d[v] + train[v][u][1]:
                d[train[v][u][0]] = d[v] + train[v][u][1]
                heappush(queue, (d[train[v][u][0]], train[v][u][0]))
    return d


def main():
    n, m, s, t = map(int, input().split())
    s -= 1
    t -= 1
    money = 10 ** 15
    train_en = []
    train_snuuk = []

    for i in range(n):
        train_en.append([])
        train_snuuk.append([])
    for i in range(m):
        fro, to, a, b = map(int, input().split())
        fro -= 1
        to -= 1
        train_en[fro].append((to, a))
        train_en[to].append((fro, a))
        train_snuuk[fro].append((to, b))
        train_snuuk[to].append((fro, b))

    a = dijkstra(n, train_en, s)
    b = dijkstra(n, train_snuuk, t)

    cost_sum = []
    for i in range(n):
        cost_sum.append((a[i] + b[i], i + 1))
    heapify(cost_sum)
    m, y = heappop(cost_sum)
    for i in range(n):
        while y <= i:
            m, y = heappop(cost_sum)
        print(money - m)


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

n, q = map(int, input().split())
graph = {i + 1:[] for i in range(n)}
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
checked = set()
check_list = [1]
new_graph = {i + 1:[] for i in range(n)}
while check_list:
    check = check_list.pop(0)
    for i in graph[check]:
        if i not in checked:
            new_graph[check].append(i)
            check_list.append(i)
    checked |= {check}
count = {i + 1:0 for i in range(n)}
for i in range(q):
    p, x = map(int, input().split())
    count[p] += x
add_list = [1]
while add_list:
    add = add_list.pop(0)
    for i in new_graph[add]:
        add_list.append(i)
        count[i] += count[add]
for i in range(n):
    print(count[i + 1], end = " ")
print()

### FIXED CODE ###

import sys, collections
input = sys.stdin.readline

n, q = map(int, input().split())
graph = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
add = [0 for i in range(n + 1)]
for i in range(q):
    p, x = map(int, input().split())
    add[p] += x
flag = [False for i in range(n + 1)]
check = collections.deque([1])
while check:
    test = check.popleft()
    flag[test] = True
    num_list = graph[test]
    for i in num_list:
        if flag[i] == True:
            pass
        else:
            add[i] += add[test]
            check.append(i)
for i in range(n):
    print(add[i + 1], end = " ")
print()
### BUGGY CODE ###

from collections import deque
N, M = map(int, input().split())
G = {k: [] for k in range(N+1)}
for _ in range(M):
    u, v = map(int, input().split())
    G[u].append(v)
S, T = map(int, input().split())

visited = [[10**9] * (N+1) for _ in range(4)]


que = deque([(S, 0, 0)])

ans = -1
c = 0
while que:
    ci, t, c = que.popleft()
    if t != 0:
        visited[t][ci] = c
    if t == 3:
        t = 0
        if ci == T:
            ans = c//3
            break

    for ni in G[ci]:
        if visited[t+1][ni] > c:
            que.append((ni, t+1, c+1))

print(ans)


### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
G = [[[] for j in range(3)] for i in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    for i in range(3):
        G[u][i].append((v, (i+1) % 3))
S, T = map(int, input().split())


visited = [[-1] * 3 for _ in range(N+1)]

que = deque([(S, 0, 0)])
visited[S][0] = 0

while que:
    ci, l, d = que.popleft()

    for ni, nl in G[ci][l]:
        if visited[ni][nl] == -1:
            que.append((ni, nl, d+1))
            visited[ni][nl] = d+1

print(visited[T][0]//3)
### BUGGY CODE ###

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

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse = True)
x = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0 for i in range(N+1)]
for i in range(2, N+1):
    for a in A:
        if i >= x[a] and dp[i-x[a]] + 1 > dp[i]:
            dp[i] = dp[i-x[a]] + 1
K = N
ans = ''
while K > 0:
    for a in A:
        if K >= x[a] and dp[K] == dp[K-x[a]] + 1:
            if dp[K] == 1 and K != x[a]:
                continue
            ans += str(a)
            K -= x[a]
            break
print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse = True)
x = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0 for i in range(N+1)]
INF = float('inf')
for i in range(1, N+1):
    t = -INF
    for a in A:
        if i >= x[a]:
            t = max(dp[i-x[a]] + 1, t)
    dp[i] = t

K = N
k = dp[N]
ans = ""
while k > 0:
    for a in A:
        xa = x[a]
        if K >= xa and k == dp[K-xa] + 1:
            ans += str(a)
            K -= xa
            k -= 1
            break
print(ans)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
ans = []
for i in range(N):
	if sum(x % (N - i) for x in ans) != a[N - 1 - i]:
		ans.append(N - i)
print(len(ans))
Ans = [str(x) for x in ans]
print(' '.join(Ans))

### FIXED CODE ###

N = int(input())
a = [0] + list(map(int, input().split()))
ans = [0] * (N + 1)
an = []
for i in range(N, 0, -1):
	if sum(ans[i * 2 :: i]) % 2 != a[i]:
		ans[i] = 1
		an.append(i)
print(len(an))
Ans = [str(x) for x in an]
print(' '.join(Ans))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import bisect

line=[i*(i+1)//2 for i in range(10**7+1)]

N=int(input())

if N==1:
    print(0)
    exit()

do=[0 for i in range(10**6+1)]

for i in range(2,int(N**0.5)+1):
    while N%i==0:
        N/=i
        do[i]+=1

ans=0
judge=True

for _,item in enumerate(do):
    index=(bisect.bisect_right(line,item))-1
    ans+=index
    if index!=0:
        judge=False

print(ans+1 if judge else ans)




### FIXED CODE ###

# coding: utf-8
# Your code here!
import bisect

line=[i*(i+1)//2 for i in range(10**6+1)]

N=int(input())


do=[0 for i in range(10**6+1)]

for i in range(2,int(N**0.5)+1):
    while N%i==0:
        N/=i
        do[i]+=1

ans=0 if N==1 else 1

for _,item in enumerate(do):
    index=(bisect.bisect_right(line,item))-1
    ans+=index

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

def doubling(n,k,a):
    logk = 1
    while pow(2,logk) < k:
        logk += 1
    dp = [[0 for _ in range(n)] for _ in range(logk)]
    for i in range(n):
        dp[0][i] = a[i]
    for i in range(logk-1):
        for j in range(n):
            dp[i+1][j] = dp[i][dp[i][j]]
    now = 0
    index = 0
    while k > 0:
        if k&1:
            now = dp[index][now]
        k = k >> 1
        index += 1
    return now+1


def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    for i in range(n):
        a[i] -= 1
    print(doubling(n,k,a))    

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n,k = inpm()
    a = inpl()
    past = [0 for _ in range(n)]
    past[0] = 1
    root = [0]
    pre = 0
    while True:
        Next = a[pre]-1
        if past[Next]:
            break
        root.append(Next)
        pre = Next
        past[Next] = 1
    rev = []
    i = 0
    while root[len(root)-1-i] != Next:
        rev.append(root[len(root)-1-i])
        i += 1
    rev.reverse()
    rever = [Next]
    for i in range(len(rev)):
        rever.append(rev[i])
    n1 = len(root)
    n2 = len(rever)
    if n1-1 >= k:
        print(root[k]+1)
        return
    if rever[0] != 0:
        k -= n1-n2
    print(rever[(k)%n2]+1)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

def m():
    h, w, d = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    pre = [0] * ((h+1)*(w+1))
    for i in range(h):
        for j in range(w):
            pre[a[i][j]] = (i+1, j+1)
    q = int(input())

    for _ in range(q):
        power = 0
        l, r = map(int, input().split())
        for p in range(l+d, r+1, d):
            power += abs(pre[p][0]-pre[p-d][0])
            power += abs(pre[p][1]-pre[p-d][1])
        print(power)

m()

### FIXED CODE ###

def m():
    h, w, d = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    pre = [0] * ((h*w)+1)
    for i in range(h):
        for j in range(w):
            pre[a[i][j]] = (i+1, j+1)
    accum = [0] * len(pre)
    for i in range(d+1, len(pre)):
        accum[i] = accum[i - d] \
                   + abs(pre[i][0] - pre[i - d][0])\
                   + abs(pre[i][1] - pre[i - d][1])

    q = int(input())
    for _ in range(q):
        l, r = map(int, input().split())
        power = accum[r] - accum[l]
        print(power)

m()
### BUGGY CODE ###

n = int(input())
li = [int(input()) for _ in range(n)]

cnt = 0
liuse = [1]
place = 1
for i in range(n):
  place = li[place-1]
  liuse.append(place)
  cnt += 1
  if place == 2:
    print(cnt)
    exit()
  if len(liuse) > len(set(liuse)):
    print(-1)
    exit()

### FIXED CODE ###

n = int(input())
li = [int(input()) for _ in range(n)]

liuse = [0]*n
liuse[0] = 1
for i in range(1,n):
  liuse[i] = li[liuse[i-1]-1]
if 2 in liuse:
  print(liuse.index(2))
else:
  print(-1)
### BUGGY CODE ###

from collections import deque
INF = int(1e9) + 7
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
def bfs(x, y):
    d = [[INF] * w for i in range(h)]
    dx = [1,0]
    dy = [0,1]
    if s[0][0] == '#':
        d[0][0] = 1
    else:
        d[0][0] = 0
    que = deque([(0, 0)])

    while len(que) != 0:
        val = que.popleft()

        for i in range(2):
            nx = val[0] + dx[i]
            ny = (val[1] + dy[i])
            if nx < h and ny < w:

                que.append((nx, ny))
                if (s[nx][ny] == '#') and (d[nx][ny] > d[val[0]][val[1]]):
                    d[nx][ny] = d[val[0]][val[1]] + 1
                elif s[nx][ny] != '#' and d[nx][ny] < d[val[0]][val[1]]:
                    d[nx][ny] = d[nx][ny]

                else:
                    d[nx][ny] = d[val[0]][val[1]]
    return d[h-1][w-1]
print(bfs(h, w))

### FIXED CODE ###

INF = int(1e9) + 7
h, w = map(int, input().split())
s = []
for i in range(h):
    s.append(list(input()))

dp = [[INF] * w for i in range(h)]
if s[0][0] == '#':
    dp[0][0] = 1
else:
    dp[0][0] = 0
#print(dp)

for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            continue
        val1 = dp[i-1][j]
        if s[i][j] == '#' and s[i-1][j] == '.':
            val1 += 1
        val2 = dp[i][j-1]
        if s[i][j] == '#' and s[i][j-1] == '.':
            val2 += 1
        dp[i][j] = min(val1, val2)
        #print(i, j,val1, val2)
print(dp[h-1][w-1])
#print(dp)
### BUGGY CODE ###

H,W=map(int,input().split())
A=[input() for _ in range(H)]
visited_area=[[-1]*W for _ in range(H)]
stack=[]
for h,c_h in enumerate(A):
    for w,c_w in enumerate(c_h):
        if c_w=='#':
            stack.append([h,w])
def bfs(A,visited_area,stack):
    kotae = 0
    for a in range(H):
        kotae += A[a].count('#')
    while kotae<H*W:
        h, w = stack.pop()
        for x, y in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h = h + x
            new_w = w + y
            if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                continue
            if A[new_h][new_w] == '.' and visited_area[new_h][new_w] == - 1:
                visited_area[new_h][new_w] = visited_area[h][w]+1
                stack.insert(0, [new_h, new_w])
                kotae+=1
bfs(A,visited_area,stack)
answers=[]
for a in visited_area:
    answers.append(max(a))
print(max(answers)+1)


### FIXED CODE ###

from collections import deque
H,W=map(int,input().split())
A=[input() for _ in range(H)]
visited_area=[[-1]*W for _ in range(H)]
stack=deque([])
for h,c_h in enumerate(A):
    for w,c_w in enumerate(c_h):
        if c_w=='#':
            stack.append([h,w])
def bfs(A,visited_area,stack):
    kotae = 0
    for a in range(H):
        kotae += A[a].count('#')
    while kotae<H*W:
        h, w = stack.pop()
        for x, y in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h = h + x
            new_w = w + y
            if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                continue
            if A[new_h][new_w] == '.' and visited_area[new_h][new_w] == - 1:
                visited_area[new_h][new_w] = visited_area[h][w]+1
                stack.appendleft([new_h, new_w])
                kotae+=1
bfs(A,visited_area,stack)
answers=[]
for a in visited_area:
    answers.append(max(a))
print(max(answers)+1)