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

import math
import sys
import queue
from collections import Counter
from itertools import accumulate
from fractions import gcd
from functools import reduce

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

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

mod = 1000000007

"""
# 標準入力取得
## 文字列
    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())

## 数値
    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

if __name__ == "__main__":
    N , M = map(int, sys.stdin.readline().split())
    A = [int(sys.stdin.readline()) for _ in range(M)]
    broken = [True if i in A else False for i in range(N + 1)]
    L = [0] * (N + 1)
    L[0] = 1
    if 1 not in A:
        L[1] = 1
    for i in range(2, N + 1):
        if not broken[i]:
            L[i] = L[i - 1] + L[i - 2]
    print(L[N] % mod)



### FIXED CODE ###

# n=int(input())
# a,b=map(int, input().split())
# c=list(map(int, input().split()))
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# a=100
# b=0.987654321
# print('{0:06d}-{1:6f}'.format(a,b))  # 0埋めのときの出力
# 000100-0.987654

import numpy as np
import math
import copy
import itertools

mod  = 1000000007

N, M=map(int, input().split())

broken = [0 for _ in range(N + 2)]

for i in range(M):
    n = int(input())
    broken[n] = True

dp = [0 for _ in range(N + 2)]
dp[N] = 1
for i in range(0, N)[::-1]:
    if broken[i]:
        dp[i] = 0
        continue
    dp[i] = (dp[i + 1] + dp[i + 2]) % mod

print(dp[0])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
n,m,k=map(int,input().split())
friend=[[]for i in range(n)]
block=[[]for i in range(n)]
G=[]

for i in range(m):
    a,b=map(int,input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
for i in range(k):
    c,d=map(int,input().split())
    block[c-1].append(d-1)
    block[d-1].append(c-1)

def dfs(now):
    global group
    for next in friend[now]:
        if visited[next]==False:
            visited[next]=True
            group.append(next)
            dfs(next)
            
    return group
group=[]
visited=[False]*n
for i in range(n):
        visited=[False]*(n)
        visited[i]=True
        G.append(dfs(i))
        group=[]
for i in range(n):
    ans=set(G[i])-set(friend[i])-set(block[i])
    print(len(ans))



### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ
 
    def find(self, x):  # x の根を返す
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])  # 経路圧縮
            return self.parent[x]
 
    def unite(self, x, y):  # x, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
 
    def is_same(self, x, y):  # x, y が同じ集合に属するか判定する
        return self.find(x) == self.find(y)
 
    def group_size(self, x):  # x が属する集合の大きさを返す
        return self.size[self.find(x)]
 

n,m,k=map(int,input().split())
friend=[[]for i in range(n)]
block=[[]for i in range(n)]
group=[[]for i in range(n)]
uf=UnionFind(n)

for i in range(m):
    a,b=map(int,input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
    uf.unite(a-1,b-1)

for i in range(k):
    c,d=map(int,input().split())
    if uf.is_same(c-1,d-1):
        block[c-1].append(d-1)
        block[d-1].append(c-1)

for i in range(n):
    ans=uf.group_size(i)-1-len(friend[i])-len(block[i])
    print(ans)
### BUGGY CODE ###

import sys
import math

def solve(a: list):
    length = len(a)
    if length <= 3:
        return min((p1[0]-p2[0])**2+(p1[1]-p2[1])**2 for p1, p2 in zip(a, a[1:]))

    med = length//2
    x_l, x_r = a[:med], a[med:]
    delta = min(solve(x_l), solve(x_r))
    median_x = a[med][0]
    m_a = []
        
    for p in x_l[::-1]:
        if p[0] < median_x-delta:
            break
        m_a.append(p)
    m_a.reverse()
    for p in x_r:
        if p[0] > median_x+delta:
            break
        m_a.append(p)

    for i, (x1, y1) in enumerate(m_a):
        to_y = y1 + delta
        for j, (x2, y2) in enumerate(m_a[i+1:]):
            if y2 > to_y:
                break
            delta = min(delta, (x1-x2)**2+(y1-y2)**2)

    return delta

if __name__ == "__main__":
    N = int(input())
    m = 1000000
    a = sorted([tuple(map(lambda s: int(float(s)*m), l.split())) for l in sys.stdin.readlines()])
    print("{:.10f}".format(math.sqrt(solve(a)/(m**2))))


### FIXED CODE ###

import sys
from operator import itemgetter
from itertools import combinations, takewhile
from math import sqrt

def solve(a: list, sorted_axis: int = -1):
    length = len(a)
    if length <= 3:
        return sqrt(min((x1-x2)**2+(y1-y2)**2 for (x1, y1), (x2, y2) in combinations(a, 2)))

    x_set_len = len(set(x for x, _ in a))
    axis1 = 0 if x_set_len > length/2 else 1

    if sorted_axis != axis1:
        a.sort(key=itemgetter(axis1))

    mid_index = length//2
    left, right = a[:mid_index], a[mid_index:]
    delta = min(solve(left, axis1), solve(right, axis1))

    axis2 = not axis1
    median = a[mid_index][axis1]
    mid_a = sorted([p for _iter in (
        (takewhile(lambda p: median-delta < p[axis1], left[::-1])),
        (takewhile(lambda p: p[axis1] < median+delta, right))
    ) for p in _iter], key=itemgetter(axis2))

    for i, (x1, y1) in enumerate(mid_a):
        ub = (x1 if axis1 else y1) + delta
        for x2, y2 in takewhile(lambda p: p[axis2] < ub, mid_a[i+1:]):
            delta = min(delta, sqrt((x1-x2)**2+(y1-y2)**2))

    return delta

if __name__ == "__main__":
    N = int(input())
    a = [tuple(map(float, l.split())) for l in sys.stdin.readlines()]
    print("{:.10f}".format(solve(a)))
### BUGGY CODE ###

import re


S = input()
L = len(S)

is_break = False

while len(S) > 1:
    S = re.sub('(01)+', '', S)
    S = re.sub('(10)+', '', S)
    try:
        S.find('01')
        S.find('10')
    except:
        is_break = True
    if is_break:
        break

print(L - len(S))


### FIXED CODE ###

S = input()

print(min(S.count('0'), S.count('1')) * 2)
### BUGGY CODE ###

N = int(input())
D = list(map(int, input().split()))
M = int(input())
T = list(map(int, input().split()))
s_T = set(T)
Flg = "YES"

for val in s_T:
    if(T.count(val) > D.count(val)):
        Flg = "NO"
        break
print(Flg)

### FIXED CODE ###

from collections import Counter
N = int(input())
D = list(map(int, input().split()))
M = int(input())
T = list(map(int, input().split()))
Flg = "YES"

c1 = Counter(D)
c2 = Counter(T)

for i, val in c2.items():
    if(c1[i] < val):
        Flg = "NO"
        break
print(Flg)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    s = input()
    q = int(input())
    K = list(map(int,input().split()))

    # print(s)

    for i in range(q):
        ans = 0
        k = K[i]
        D = [[0] * 3 for j in range(n)]
        for j in range(n):
            D[j][:] = D[j-1][:]

            if j-k >= 0:
                if s[j-k] == "D":
                    D[j][0] -= 1
                    D[j][2] -= D[j][1]
                elif s[j-k] == "M":
                    D[j][1] -= 1

            if s[j] == "D":
                D[j][0] += 1
            elif s[j] == "M":
                D[j][1] += 1
                D[j][2] += D[j][0]
            elif s[j] == "C":
                ans += D[j][2]
        print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    s = input()
    q = int(input())
    K = list(map(int,input().split()))
    # print(s)

    for i in range(q):
        ans = 0
        d = 0
        m = 0
        dm = 0
        k = K[i]
        for j in range(n):

            if j-k >= 0:
                if s[j-k] == "D":
                    d -= 1
                    dm -= m
                elif s[j-k] == "M":
                    m -= 1

            if s[j] == "D":
                d += 1
            elif s[j] == "M":
                m += 1
                dm += d
            elif s[j] == "C":
                ans += dm
        print(ans)

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

N = int(input())
p = [int(i) for i in input().split()]
ans = 1

if 0 in p:
  print(0)
  exit()
  
for i in p:
  ans = ans * i
  
if ans > 10 ** 18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

N = int(input())
p = [int(i) for i in input().split()]
ans = 1

if 0 in p:
  print(0)
  exit()
  
for i in range(N):
  ans*=p[i]
  if ans > 10 ** 18:
    print(-1)
    exit()
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

# from typing import Optional
from typing import List

# from typing import Dict
from typing import Tuple

# from typing import Sequence
import copy

Cod = Tuple[int, int]


def main():
    args = input().split()
    H = int(args[0])
    W = int(args[1])
    M = int(args[2])

    codList: List[Cod] = []
    for i in range(M):
        args = input().split()
        codList.append((int(args[0]), int(args[1])))

    maxRowCount = 0
    maxRowIndexList: List[int] = []
    tempCodList = copy.deepcopy(codList)
    for row in range(H):
        hitList = list(filter(lambda x: x[0] == row + 1, tempCodList))
        for hit in hitList:
            tempCodList.remove(hit)

        counter = len(hitList)
        if counter > maxRowCount:
            maxRowCount = counter
            maxRowIndexList = [row + 1]
        elif counter == maxRowCount:
            maxRowIndexList.append(row + 1)

    maxColumnCount = 0
    maxColumnIndexList: List[int] = []
    tempCodList = copy.deepcopy(codList)
    for column in range(W):
        hitList = list(filter(lambda x: x[1] == column + 1, tempCodList))
        for hit in hitList:
            tempCodList.remove(hit)
        counter = len(hitList)
        if counter > maxColumnCount:
            maxColumnCount = counter
            maxColumnIndexList = [column + 1]
        elif counter == maxColumnCount:
            maxColumnIndexList.append(column + 1)

    result = maxRowCount + maxColumnCount
    for row in maxRowIndexList:
        for column in maxColumnIndexList:
            if (row, column) in codList:
                continue
            else:
                print(result)
                return

    print(result - 1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

# from typing import Optional
from typing import List

# from typing import Dict
from typing import Tuple
from typing import Set

# from typing import Sequence

Cod = Tuple[int, int]


def main():
    args = input().split()
    H = int(args[0])
    W = int(args[1])
    M = int(args[2])

    codList = {}
    columnSumList: List[int] = [0] * W
    rowSumList: List[int] = [0] * H
    for i in range(M):
        h, w = map(lambda x: int(x), input().split())
        item = (h, w)
        codList.setdefault(h, {})
        codList[h][w] = item
        columnSumList[w - 1] += 1
        rowSumList[h - 1] += 1

    maxColumnSum = max(columnSumList)
    maxColumIndexList = [i for i, x in enumerate(columnSumList) if x == maxColumnSum]
    maxRowSum = max(rowSumList)
    maxRowIndexList = [i for i, x in enumerate(rowSumList) if x == maxRowSum]

    result = maxColumnSum + maxRowSum
    for row in maxRowIndexList:
        for column in maxColumIndexList:
            if row + 1 in codList and column + 1 in codList[row + 1]:
                continue
            else:
                print(result)
                return

    print(result - 1)


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

import collections
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.dist = [0] * n
 
    def root(self, i, d):
        if self.parent[i] == i:
            return i, d
        else:
            self.parent[i], d2 = self.root(self.parent[i], d + self.dist[i])
            return self.parent[i], d2
    
    def find(self, x, y):
        return self.root(x) == self.root(y)
 
    def union(self, i, j, d):
        i2, d1 = self.root(i, 0)
        j2, d2 = self.root(j, 0)
        if i2 < j2 :
            self.parent[j2] = i2
            self.dist[j] = d1 + d
        else:
            self.parent[i2] = j2
            self.dist[i] = d2 + d
            
N = int(input())
ps = [list(map(int, input().split())) for _ in range(N-1)]
ps = collections.deque(ps)
tree = UnionFind(N)
prv = set([1])
while ps:
    i, j, d = ps.popleft()
    if i in prv or j in prv:
        tree.union(i-1, j-1, d)
        prv.add(i)
        prv.add(j)
    else:
        ps.append([i, j, d])

for d in tree.dist:
    if d % 2 == 0:
        print(1)
    else:
        print(0)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
n=int(input())
G=[[]for i in range(n+1)]
for i in range(n-1):
    a, b, c = map(int,input().split())
    G[a] += (b,c),
    G[b] += (a,c),
    
d = [0]*(n+1) #1から各点への距離
def f(v,p,u): #v:今見ているとこ p:一つ前に見たとこ u:1からの距離
    d[v] = u
    for t, c in G[v]:
        if p != t:
            f(t,v,u+c)
f(1,0,0)
for i in range(n):
    if d[i+1] % 2 == 0:
        print(1)
    else:
        print(0)
### BUGGY CODE ###

l, r = map(int,input().split())
arr = []
if r-l <= 2019**2:
  for i in range(l,r):
    for j in range(i+1,r+1):
      a = (i*j)%2019
      arr.append(a)
  print(min(arr))
else:
  for i in range(l,2019**2+l):
    for j in range(i+1, 2019**2+l+1):
      a = (i*j)%2019
      arr.append(a)
    if 0 in arr:
      break
  print(min(arr))

### FIXED CODE ###

l, r = map(int,input().split())
arr = []
if r-l < 2019**2:
  for i in range(l,r):
    for j in range(i+1,r+1):
      a = (i*j)%2019
      arr.append(a)
    if 0 in arr:
      break
  print(min(arr))
else:
  print(0)
### BUGGY CODE ###

N = int(input())
X = []
for i in range(N):
    A = int(input())
    for j in range(len(X)):
        if A > X[j]:
            X[j] = A
            break
    else:
        X.append(A)
print(len(X))


### FIXED CODE ###

import bisect

N = int(input())
A = [-int(input()) for i in range(N)]
X = []
for i in range(N):
    a = A[i]
    idx = bisect.bisect_left(X, a+0.1)
    if idx == len(X):
        X.append(a)
    else:
        X[idx] = a
print(len(X))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)

# 1 ✕ 1 (int)
N = int(input().rstrip())

# N ✕ M (2D array)
A = list(map(int, input().rstrip().split()) for _ in range(N - 1))

items = [[-1] * (N) for _ in range(N)]
colors = [-1 for _ in range(N)]

for i in range(N - 1):
    a, b, w = A[i]
    items[a - 1][b - 1] = w
    items[b - 1][a - 1] = w


def dfs(v, c):
    colors[v] = c
    for i in range(N):
        w = items[v][i]
        if w == -1:
            continue

        cc = colors[i]
        nc = c if w % 2 == 0 else not c
        if cc != -1 and colors[i] != nc:
            return False
        if cc == -1 and not dfs(i, nc):
            return False

    return True


dfs(0, True)
for c in colors:
    print(int(not c))


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import collections

sys.setrecursionlimit(10 ** 7)

# 1 ✕ 1 (int)
N = int(input().rstrip())

# N ✕ M (2D array)
A = list(map(int, input().rstrip().split()) for _ in range(N - 1))

items = [[] for _ in range(N)]
colors = [-1 for _ in range(N)]

for i in range(N - 1):
    a, b, w = A[i]
    items[a - 1].append((b - 1, w))
    items[b - 1].append((a - 1, w))

queue = collections.deque()
queue.append(0)
colors[0] = 0
while queue:
    v = queue.popleft()
    c = colors[v]
    for k, w in items[v]:
        cc = colors[k]
        if cc == -1:
            nc = c if w % 2 == 0 else not c
            colors[k] = nc
            queue.append(k)

# def dfs(v, c):
#     colors[v] = c
#
#     cc = colors[k]
#
#     if cc == -1:
#         if not dfs(k, nc):
#             return False
#     else:
#         if colors[i] != nc:
#             return False
#
#
# return True
#
# dfs(0, True)
for c in colors:
    print(int(not c))
### BUGGY CODE ###

def main():
  import sys
  input = sys.stdin.readline
  
  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()))
  A.sort(reverse = True)
  B.sort(reverse = True)
  C.sort(reverse = True)
  res = []
  for i in range(X):
    for j in range(Y):
      for k in range(Z):
        if (i+1)*(j+1)*(k+1) <= K:
          res.append(A[i]+B[j]+C[k])
  res.sort(reverse = True)
  for r in res[:K]:
    print(r)

if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline

  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()))
  A.sort(reverse = True)
  B.sort(reverse = True)
  C.sort(reverse = True)
  AB = [a+b for a in A for b in B]
  AB.sort(reverse = True)
  res = [c+ab for ab in AB[:min(K, len(AB))] for c in C]
  res.sort(reverse = True)
  print("\n".join(list(map(str,res[:K]))))

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

n = int(input())
a = list(map(int,input().split()))
left = 0
num = 1
while True:
    Flag = True
    for i in range(len(a)):
        if a[i] == num:
            left += 1
            a = a[i:]
            Flag = False
            num += 1
            break
    if Flag:
        break
if left == 0:
    ans = -1
else:
    ans = n - left
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
left = 0
num = 1
start = 0
while True:
    Flag = True
    for i in range(start,n):
        if a[i] == num:
            left += 1
            start = i
            Flag = False
            num += 1
            break
    if Flag:
        break
if left == 0:
    ans = -1
else:
    ans = n - left
print(ans)
### BUGGY CODE ###

def delete(S):
    check=False
    for s in range(len(S)-1):
        if S[s]=="0" and S[s+1]=="1":
            del S[s]
            del S[s]
            check=True
            break
        if S[s]=="1" and S[s+1]=="0":
            del S[s]
            del S[s]
            check=True
            break
    return check,S
S= [i for i in input()]
ans= 0
check=True
while check == True:
    check,S = delete(S)
    if check == False:
        break
    else:
        ans+=2
print(ans)

### FIXED CODE ###

S = [i for i in input()]
zero = S.count("0")
iti = S.count("1")
print(min(zero,iti)*2)
### BUGGY CODE ###

"""
---アルゴリズム概要---
閉路のないグラフなので、シンプルにxからKまでまっすぐに進んでから、Kからyにまっすぐ進むことを考えればよい。
クエリの数Qが10**5個あるので、ノードaからノードbにまっすぐ進む場合のコストをメモしていくのがよさそう。

次に、どうやってノードaからノードbへの「まっすぐ進む道」＝「まっすぐ進むための次のノード」を判断するかだが、
これは、ノードaが直接つながっているノードのうち、
ノードbへのコストが最も少ないものがまっすぐ進むための次のノードとなる。
"""
import sys
sys.setrecursionlimit(2000000)
input = sys.stdin.readline
N = int(input())
edges = [{} for _ in range(N)]
#dpでiからjへの最短コストを管理する。
for _ in range(N-1):
    a,b,c = map(int,input().split())
    edges[a-1][b]=c
    edges[b-1][a]=c

Q,K = map(int,input().split())
dp = [float("INF")]*(N)

path = {}
def dfs(i,c):
    dp[i-1]=c
    path[i]=""
    for n,cost in edges[i-1].items():
        if n not in path:
            dfs(n, c + cost)

dfs(K,0)
for _ in range(Q):
    x,y = map(int,input().split())
    print(dp[x-1]+dp[y-1])

### FIXED CODE ###

"""
--- アルゴリズム概要 ---
前計算で頂点Kから各ノードへの最短路を記録しておき、
各クエリに対しては、dp[a]+dp[b]を返せばよい。

頂点Kから各ノードへの最短ルートはdfsとかで記録していけばよい。
"""
def main():
    from collections import deque
    import sys
    sys.setrecursionlimit(20000000)
    input = sys.stdin.readline
    N = int(input())
    AB = [[]for _ in range(N+1)]
    for i in range(N-1):
        a,b,c = map(int,input().split())
        AB[a].append((b,c))
        AB[b].append((a,c))

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

    path = {K:""}
    dp = [0]*(N+1)
    que = deque()
    for n,c in AB[K]:
        que.append((n,c))
    while que:
        now,cost = que.pop()
        path[now]=""
        dp[now]=cost
        for n,c in AB[now]:
            if n not in path:
                que.append((n,cost+c))
    for i in range(Q):
        x,y=map(int,input().split())
        print(dp[x]+dp[y])
main()
### BUGGY CODE ###

n,m = map(int,input().split())
numSet = set(range(1,n+1))
for i in range(m):
  l,r = map(int,input().split())
  numSet &= set(range(l,r+1))
print(len(numSet))


### FIXED CODE ###

n,m = map(int,input().split())
numSet = set(range(1,n+1))
L,R = [],[]
for i in range(m):
  l,r = map(int,input().split())
  L.append(l)
  R.append(r)
if min(R) >= max(L):
  print(min(R)-max(L)+1)
else:
  print(0)
### BUGGY CODE ###

n = int(input())
L = sorted(list(map(int, input().split())))
def isOK(target,a,b):
  return target > abs(a-b) and target < a+b

def bin_search(a,b):
  left = 1
  right = n
  while right-left>1:
    mid = (left+right)//2
    if isOK(L[mid],a,b):
      left = mid
    else:
      right = mid
  return left
ans = 0
for i in range(n):
  for j in range(i+1,n):
    a,b = L[i],L[j]
    ans += max(0, bin_search(a,b) - j)
      
print(ans)


### FIXED CODE ###

n = int(input())
L = sorted(list(map(int, input().split())))
def isOK(target,a,b):
  return target < a+b

def bin_search(a,b):
  left = 1
  right = n
  while abs(right-left)>1:
    mid = (left+right)//2
    if isOK(L[mid],a,b):
      left = mid
    else:
      right = mid
  return left
ans = 0
for i in range(n-2):
  for j in range(i+1,n):
    a,b = L[i],L[j]
    ans += max(0, bin_search(a,b) - j)
      
print(ans)
### BUGGY CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．

def main():
  H, W = list(map(int, input().split()))
  all_count = H * W
  L = [j == "#" for i in range(H) for j in input()]
  all_count = H * W
  blacks = [i for i in range(all_count) if L[i]]
  black_count = len(blacks)
 
  cands_H = [-W, W]
  cands_W = [-1, 1]
  result = 0
  while black_count < all_count:
    next_steps = [black+cand for black in blacks for cand in cands_H]
    next_steps.extend([black-1 for black in blacks if black%W != 0])
    next_steps.extend([black+1 for black in blacks if black%W != W-1])
    next_steps = set(next_steps)
    blacks = [i for i in next_steps if i >= 0 and i < all_count and not L[i]]
    for i in blacks:
      L[i] = True
    black_count += len(blacks)
    result += 1

  print(result)

if __name__ == "__main__":
  main()


### FIXED CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．
from collections import deque
import copy

def main():
  H, W = list(map(int, input().split()))
  L = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if L[i][j]])
  cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  result = 0
  while True:
    nq = deque()
    while q:
      i, j = q.popleft()
      if i > 0 and not L[i-1][j]:
        L[i-1][j] = True
        nq.append((i-1, j))
      if j > 0 and not L[i][j-1]:
        L[i][j-1] = True
        nq.append((i, j-1))
      if i < H-1 and not L[i+1][j]:
        L[i+1][j] = True
        nq.append((i+1, j))
      if j < W-1 and not L[i][j+1]:
        L[i][j+1] = True
        nq.append((i, j+1))
    if nq:
      q = copy.copy(nq)
    else:
      break    
    result += 1
  print(result)

if __name__ == "__main__":
  main()