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

#A
from collections import deque
H,W = map(int,input().split())
G = [list(str(input())) for _ in range(H)]
inf = float("inf")

dist = [[inf for w in range(W)] for h in range(H)]
now = [[0,0]]

if G[0][0] == "#":
    dist[0][0] = 1
else:
    dist[0][0] = 0
    
D = deque([[0,0]])
while D:
    d = D.popleft()
    h,w = d
    if h < H-1:
        D.append([h+1,w])
        if G[h+1][w] == "#":
            dist[h+1][w] = min(dist[h+1][w],dist[h][w]+1)
        else:
            dist[h+1][w] = min(dist[h+1][w],dist[h][w])
    if w < W-1:
        D.append([h,w+1])
        if G[h][w+1] == "#":
            dist[h][w+1] = min(dist[h][w+1],dist[h][w]+1)
        else:
            dist[h][w+1] = min(dist[h][w+1],dist[h][w])

print(dist[H-1][W-1])



### FIXED CODE ###

#A
H,W = map(int,input().split())
G = [list(str(input())) for _ in range(H)]
inf = float("inf")

dist = [[inf for w in range(W)] for h in range(H)]

if G[0][0] == "#":
    dist[0][0] = 1
else:
    dist[0][0] = 0

for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            pass
        elif j == 0:
            dist[i][j] = dist[i-1][j]
            if G[i][j] == "#" and G[i-1][j] != "#":
                dist[i][j]+=1
        elif i == 0:
            dist[i][j] = dist[i][j-1]
            if G[i][j] == "#" and G[i][j-1] != "#":
                dist[i][j]+=1
        else:
            d1 = dist[i-1][j]
            d2 = dist[i][j-1]
            if G[i][j] == "#" and G[i-1][j] != "#":
                d1+=1
            if G[i][j] == "#" and G[i][j-1] != "#":
                d2+=1
            dist[i][j] = min(d1,d2)
        

print(dist[H-1][W-1])
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split())
A = list(map(int, input().split()))
sumlist = np.sort(np.array([sum(A[j:j+N-i]) for i in range(N) for j in range(i+1)]))[::-1]
ans = sumlist[0]
for i in range(40, -1, -1):
    tmp = (ans & (2 ** i)) // (2 ** i)
    if tmp:
        start = i
        break
f = lambda x: (x & onehot) // onehot
ans_list = [0]
ans = 0
for i in range(start, -1, -1):
    onehot = 2 ** i + ans
    tmp = list(map(f, sumlist))
    if sum(tmp) >= K:
        ans = onehot
print(ans)


### FIXED CODE ###

from collections import Counter
N, K = map(int, input().split())
A = list(map(int, input().split()))
cusum = [A[0]]
for i in range(1, N):
    cusum += [cusum[-1]+A[i]]
B = []
for i in range(N):
    B += [cusum[i]]
    for j in range(i+1, N):
        B += [cusum[j] - cusum[i]]
max_bit = 43
ans = 0
while max_bit > 0:
    counter = Counter()
    for b in B:
        for i in range(44):
            if b & 1 == 1:
                counter[i] += 1
            b = b >> 1
    for i in range(max_bit, -1, -1):
        if counter[i] >= K:
            filter_bit = 2 ** i
            B = [b for b in B if b & filter_bit == filter_bit]
            max_bit = i-1
            ans += filter_bit
            break
        max_bit = i
print(ans)
### BUGGY CODE ###

k, s = map(int, input().split())

sum_set = []
for i in range(k + 1):
    for j in range(k + 1):
        m = s - i - j
        if 0 <= m <= k:
            comb = [i, j, m]
            sum_set.append(comb)
        else:
            continue
print(len(sum_set))


### FIXED CODE ###

k, s = map(int, input().split())

count = 0
for i in range(k + 1):
    for j in range(k + 1):
        m = s - i - j
        if 0 <= m <= k:
            count += 1
print(count)
### BUGGY CODE ###

from collections import defaultdict, Counter
from itertools import combinations
INF = float("inf")


def main():
    N, K = map(int, input().split())
    points = []
    for i in range(N):
        x, y = map(int, input().split())
        points.append((y, x))

    ans = INF
    for i in range(N):
        for j in range(N):
            for k in range(N):
                for l in range(N):
                    y1, y2, x1, x2 = points[i][0], points[j][0], points[k][1], points[l][1]

                    n = 0
                    for p in points:
                        n += y1 <= p[0] <= y2 and x1 <= p[1] <= x2
                    if n >= K:
                        ans = min(ans, abs(y1 - y2) * abs(x1 - x2))
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict, Counter
from itertools import combinations
INF = float("inf")


memo1 = {}
memo2 = {}

def ok(y1, y2, x1, x2, yd, yd2, xd, xd2, K):
    if (y1, y2) in memo1:
        y = memo1[(y1, y2)]
    else:
        a = yd2[y1]
        b = yd[y2]
        y = b.difference(a)
        memo1[(y1, y2)] = y

    if (x1, x2) in memo2:
        x = memo2[(x1, x2)]
    else:
        c = xd2[x1]
        d = xd[x2]
        x = d.difference(c)
        memo2[(x1, x2)] = x

    # print(a, b, c, d)
    # print(y, x)

    n = len(y & x)

    return n >= K


def main():
    import time
    N, K = map(int, raw_input().split())
    ys, xs = [], []
    for i in range(N):
        x, y = map(int, raw_input().split())
        ys.append((y, i))
        xs.append((x, i))

    ys.sort()
    yd = defaultdict(set)
    yd2 = defaultdict(set)
    old = set()
    for y, i in ys:
        yd2[y] = old.copy()
        old.add(i)
        yd[y] = old.copy()

    xs.sort()
    xd = defaultdict(set)
    xd2 = defaultdict(set)
    old = set()
    for x, i in xs:
        xd2[x] = old.copy()
        old.add(i)
        xd[x] = old.copy()

    ans = INF

    # print(yd)
    # print(xd)
    #
    # print(ok(1, 4, 1, 8, yd, yd2, xd, xd2, K))
    for i, j in combinations(range(N), 2):
        for k, l in combinations(range(N), 2):
            a, b, c, d = ys[i], ys[j], xs[k], xs[l]
            y1 = min(a[0], b[0])
            y2 = max(a[0], b[0])

            x1 = min(c[0], d[0])
            x2 = max(c[0], d[0])

            kkk = abs(x1 - x2) * abs(y1 - y2)
            if kkk < ans:
                # print(i, j)
                # print(x1, x2, abs(x1 - x2))
                # print(y1, y2, abs(y1 - y2))
                # print(ok(y1, y2, x1, x2, yd, yd2, xd, xd2, K))
                if ok(y1, y2, x1, x2, yd, yd2, xd, xd2, K):
                    ans = kkk

    print(ans)

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

import math

N,M = map(int,input().split())
A = [0]*N
A = list(map(int,input().split()))
if (N == 1):
    print(A[0]//(2**M))
else:
    while (M != 0):
        A.sort(reverse=True)
        y = min(math.floor(math.log2(A[0]/A[1])+1),M)
        A[0] //= 2**y
        M -= y

    print(sum(A))


### FIXED CODE ###

import math
import heapq

N,M = map(int,input().split())
A = [0]*N
A = list(map(lambda x: int(x)*(-1),input().split()))
if (N == 1):
    print((-1 * A[0])//(2**M))
else:
    """
    while (M != 0):
        A.sort(reverse=True)
        y = min(math.floor(log2(A[0]/A[1])+1),M)
        A[0] //= 2**y
        M -= y
    """
    """
    A.sort(reverse=True)
    for i in range(N):
        y = min(A[i] // 2,M)
        A[i] //= 2**y
        M -= y
        if (M <= 0):
            break
    """
    heapq.heapify(A)

    for i in range(M):
        m = heapq.heappop(A) * -1
        heapq.heappush(A,(m//2 * -1))

    print(-sum(A))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

def main():
    N, X, Y = map(int,input().split())

    node = [[[] for _ in range(N)] for _ in range(N)]
    used = [[False] * N for _ in range(N)]

    for i in range(N):
        node[i][0].append(i)
        used[i][i] = True


    for k in range(1,N):
        ans = 0
        for i in range(N):
            for x in node[i][k-1]:
                if x == X-1 and (not used[i][Y -1]):
                    node[i][k].append(Y-1)
                    used[i][Y-1] = True
                    ans += 1

                if x == Y-1 and (not used[i][X -1]):
                    node[i][k].append(X-1)
                    used[i][X-1] = True
                    ans += 1

                if (x - 1 >= 0 )and (not used[i][x - 1]):
                    node[i][k].append(x - 1)
                    used[i][x - 1] = True
                    ans += 1

                if (x + 1 < N) and (not used[i][x + 1]):
                    node[i][k].append(x + 1)
                    used[i][x + 1] = True
                    ans += 1
        print(ans//2)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

def main():
    N, X, Y = map(int,input().split())
    X, Y = X - 1, Y - 1

    # iからjまでの距離
    # 到達の仕方は以下の３パターンなので、このうち最小が最短の距離になる
    # 直線のパターン
    # |j - i|
    # まずiからXまでいって、その後XからYまでジャンプ、Yからjまでのパターン
    # |X - i| + 1 + |j - Y|
    # まずiからYまでいって、その後YからXまでジャンプ、Xからjまでのパターン
    # |Y - i| + 1 + |j - X|

    ans = [0] * N

    for i in range(N - 1):
        for j in range(i + 1, N):
            ij = abs(j - i)
            ixyj = abs(X - i) + 1 + abs(j - Y)
            iyxj = abs(Y - i) + 1 + abs(j - X)

            dist = min(ij, ixyj, iyxj)

            ans[dist] += 1

    for a in ans[1:]:
        print(a)


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

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split( )))
ans = 0
mod = 10**9+7
Bit = [0 for j in range(60)]# for i in range(n+1)

for i in range(1,n):##1から
    for j in range(60):
        if not ((a[i-1]>>j)&1):#a[i-1]のjビット目0
            Bit[j] += 1
        if ((a[i]>>j)&1):#aiのjビット目1
            ans += Bit[j]<<j
            ans %=mod
        else:
            ans += (i-Bit[j])<<j
            ans %= mod
    
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split( )))
ans = 0
mod = 10**9+7
Bit = [0 for j in range(60)]# for i in range(n+1)
for j in range(60):#ループ交換
    for i in range(1,n):##1から
        if not ((a[i-1]>>j)&1):#a[i-1]のjビット目0
            Bit[j] += 1
        if ((a[i]>>j)&1):#aiのjビット目1
            ans += Bit[j]<<j
            ans %=mod
        else:
            ans += (i-Bit[j])<<j
            ans %= mod
    
print(ans)
### BUGGY CODE ###

import numpy as np

n = int(input())
listN = np.array([i+1 for i in range(n)])
listM = np.array([j+2 for j in range(n-1)]+[1])
print(np.sum(listN%listM))


### FIXED CODE ###

n = int(input())
print(((n-1)*n)//2)
### BUGGY CODE ###

import sys

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = rl()
MOD = 10 ** 9 + 7
#2番目以降(N-1個の数)のbitの格桁の合計
l = [0] * 60
for i in range(N):
    s = list(str(bin(A[i]))[2:].rjust(60, '0'))
    #print(s)
    for j in range(60):
        if s[j] == '1':
            l[j] += 1
answer = 0
#print(l)
for i in range(N-1):
    s = list(str(bin(A[i]))[2:].rjust(60, '0'))
    for j in range(60):
        if s[j] == '1':
            l[j] -= 1
            answer += 2 ** (59-j) * (N - 1 - i - l[j])
        else:
            answer += 2 ** (59-j) * l[j]
    answer %= MOD
#print(l)
print(answer)



### FIXED CODE ###

import sys
import numpy as np

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = np.array(rl())
answer = 0
MOD = 10 ** 9 + 7

for n in range(63):
    B = (A >> n) & 1
    x = np.count_nonzero(B)
    y = N - x
    x *= y
    for _ in range(n):
        x *= 2
        x %= MOD
    answer += x

print(answer%MOD)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)

def rec(n):
    if n == 1:
        return 1
    return rec(n-1) + 1


print(rec(600000))


### FIXED CODE ###

A, B = map(int, input().split())
print(max(A*2-1,A+B,B*2-1))
### BUGGY CODE ###

nk = input().split()
seisuuretu = input().split()

for i in range(len(seisuuretu)):
    seisuuretu[i] = int(seisuuretu[i])

all_seisuuretu = []

for start in range(len(seisuuretu) + 1):
    for end in range(len(seisuuretu) + 1):
        if start < end:
            all_seisuuretu.append(seisuuretu[start:end])

list_max = []
beautiful_list = []
for pattern in all_seisuuretu:
    temp_pattern = bin(sum(pattern))[2:]
    beautiful_list.append(temp_pattern)
    list_max.append(len(temp_pattern))

list_max = -max(list_max)

status = True
while status == True:
    temp = []
    count = 0
    for i in beautiful_list:
        try:
            if int(i[list_max]) == 1:
                count += 1
                temp.append(i)
        except:
            continue
    if count > int(nk[1]):
        list_max += 1
        beautiful_list = temp
    elif count == int(nk[1]):
        beautiful_list = temp
        num_count = True
        for num in beautiful_list:
            if num_count == True:
                ronriseki = int(num, 2)
            else:
                ronriseki = ronriseki & int(num, 2)
            num_count = False
        print(ronriseki)
        status = False
    elif list_max == -1:
        num_count = True
        for num in beautiful_list:
            if num_count == True:
                ronriseki = int(num, 2)
            else:
                ronriseki = ronriseki & int(num, 2)
            num_count = False
        print(ronriseki)
        status = False
    else:
        list_max += 1


### FIXED CODE ###

nk = input().split()
seisuuretu_2 = input().split()
nk1 = int(nk[1])

#seisuuretu = [int(i) for i in seisuuretu_2]
seisuuretu = list(map(int, seisuuretu_2))

list_max = set()
beautiful_list = []
for start in range(len(seisuuretu) + 1):
    for end in range(len(seisuuretu) + 1):
        if start < end:
            temp_pattern = bin(sum(seisuuretu[start:end]))[2:]
            beautiful_list.append(temp_pattern)
            list_max |= {len(temp_pattern),}

list_max = -max(list_max)

status = True
while status == True:
    temp = []
    count = 0
    for i in beautiful_list:
        try:
            if i[list_max] == "1":
                count += 1
                temp.append(i)
        except:
            continue
    if count > nk1:
        list_max += 1
        beautiful_list = temp
    elif count == nk1:
        num_count = True
        for num in temp:
            if num_count == True:
                ronriseki = int(num, 2)
            else:
                ronriseki = ronriseki & int(num, 2)
            num_count = False
        print(ronriseki)
        exit()
        status = False
    elif list_max == -1:
        num_count = True
        for num in beautiful_list:
            if num_count == True:
                ronriseki = int(num, 2)
            else:
                ronriseki = ronriseki & int(num, 2)
            num_count = False
        print(ronriseki)
        exit()
        status = False
    else:
        list_max += 1
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
ne = n%2
B = []
for i in range(n):
    if (i+1)%2 == ne:
        B = [A[i]]+B
    else:
        B = B + [A[i]]
print(*B)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
if n%2==0:
    B = A[1::2][::-1] + A[::2]
    print(*B)
else:
    B = A[::2][::-1] + A[1::2]
    print(*B)
### BUGGY CODE ###

#!/usr/bin/python

import sys

p=[0]*10000;mp=[];inf=65536;v=[0]*10000;t=[0]*10000
 
 
ans=100000
 
n,m,r=map(int,raw_input().split(' '))
 
p=map(int,raw_input().split(' '))
 
def dsss(x,now):
	global ans
	if x==r+1:
		ans=min(ans,now)
		return 
	else :
		for i in range(r):
			if v[p[i]]==0 :
				v[p[i]]=1
				t[x]=p[i]
				if x==1:
					dsss(x+1,now)
				else :
					dsss(x+1,now+mp[p[i]-1][t[x-1]-1])
				v[p[i]]=0
	return 
 
 
for i in range(n+5):
	mp.append(range(n+5))
 
 
for i in range(n+5):
    for j in range(n+5):
        mp[i][j]=inf
 
for i in range(m):
	a,b,c=map(lambda x: int(x),sys.stdin.readline().split(" ",3))
	a-=1;b-=1;
	mp[a][b]=min(mp[a][b],c)
	mp[b][a]=min(mp[b][a],c)
 
for i in range(n):
	for j in range(n):
		for k in range(n):
			mp[j][k]=min(mp[j][k],mp[j][i]+mp[i][k])
 
dsss(1,0)
 
print ans


### FIXED CODE ###

#!/usr/bin/python

import sys

p=[0]*10000;mp=[];inf=65530060;v=[0]*1000;t=[0]*1000
 
 
ans=100000000

 
n,m,r=map(int,sys.stdin.readline().split(" "))



s=sys.stdin.readline().replace("\n","")

p=map(int,s.split(" "))


def dsss(x,now):
	global ans,v,p,t,mp
	if x==r+1:
		ans=min(ans,now)
		return 
	else :
		for i in range(r):
			if v[p[i]]==0 :
				v[p[i]]=1
				t[x]=p[i]
				if x==1:
					dsss(x+1,now)
				else :
					dsss(x+1,now+mp[p[i]-1][t[x-1]-1])
				v[p[i]]=0
	return 
 
 
for i in range(n+5):
	mp.append(range(n+5))
 
 
for i in range(n+5):
    for j in range(n+5):
            mp[i][j]=inf


for i in range(m):
	a,b,c=map(lambda x: int(x),sys.stdin.readline().split(" ",3))
	a-=1;b-=1;
	mp[a][b]=min(mp[a][b],c)
	mp[b][a]=min(mp[b][a],c)


for i in xrange(n):
	for j in xrange(n):
		for k in xrange(n):
			if mp[j][i]+mp[i][k]<mp[j][k]:
			    mp[j][k]=mp[j][i]+mp[i][k]

dsss(1,0)
 
print ans
### BUGGY CODE ###

N,W=map(int,input().split())
Wlist=[]
Vlist=[]
for i in range(N):
  w,v=map(int,input().split())
  Wlist+=[w]
  Vlist+=[v]
dp=[[0 for p in range(W+1)] for i in range(N)]
for i in range(W+1):
  if i>=Wlist[0]:
    dp[0][i]=Vlist[0]
for i in range(1,N):
  wi=Wlist[i]
  for j in range(W+1):
    if j-wi>=0:
      dp[i][j]=max(dp[i-1][j-wi]+Vlist[i],dp[i-1][j])
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j])
print(max(dp[N-1]))

### FIXED CODE ###

def main():
  N,W=map(int,input().split())
  Wlist=[]
  Vlist=[]
  for i in range(N):
    w,v=map(int,input().split())
    Wlist+=[w]
    Vlist+=[v]
  Vmax=max(Vlist)
  V=Vmax*N
  dp=[[float('inf') for p in range(V+1)] for i in range(N)]
  for i in range(V+1):
    if i<=Vlist[0]:
      dp[0][i]=Wlist[0]
  dp[0][0]=0
  for i in range(1,N):
    vi=Vlist[i]
    wi=Wlist[i]
    for j in range(V+1):
      if j-vi>=0:
        dp[i][j]=min(dp[i-1][j-vi]+wi,dp[i-1][j])
      else:
        dp[i][j]=min(dp[i-1][j],dp[i][j])
  dpn=dp[N-1]
  ans=0
  for i in range(V+1):
    if dpn[i]<=W:
      ans=i
  print(ans)
if __name__ == '__main__':
  main()
### BUGGY CODE ###

n,ad=map(int,input().split())
b=[int(i)for i in input().split()]
def combs(a):
    if len(a) == 0:
        return [[]]
    cs =[]
    for c in combs(a[1:]):
        cs += [c, c+[a[0]]]
    return cs
cou=0
for i in combs(b):
  if len(i)==0:
    continue
  elif sum(i)/len(i)==ad:
    cou+=1
print(cou)   

### FIXED CODE ###

n,a=map(int,input().split())
nums=[int(i)-a for i in input().split()]
d={0:1}
for i in nums:
  s = [[j, d[j]] for j in d]
  for j in s:
    if j[0] + i in d:
      d[j[0]+i] += j[1]
    else:
      d[j[0]+i] = j[1]
print(d[0]-1)
### BUGGY CODE ###

N,M=map(int, input().split() )
A=list(map(int, input().split() ))
B=[0]*M
C=[0]*M
for i in range(M):
  B[i],C[i]=map(int, input().split() )
A.sort()
summ=sum(A)

for i in range(M):
  cnt=0
  for j,num in enumerate(A):
    if num<=C[i]:
      A[j]=C[i]
      cnt += 1
      if cnt==B[i]:
        break
  A.sort()
  
print(sum(A))
  
  

### FIXED CODE ###

from collections import Counter

N,M = map(int, input().split() )
A   = list(map(int, input().split() ))
B   = [0]*M
C   = [0]*M
Cou = Counter(A)

for i in range(M):
  B[i],C[i]  = map(int, input().split() )
  Cou[C[i]] += B[i]
  
#print(Cou)  
ans=0
cnt=0
S=sorted(Cou,reverse=True)
#print(S)
for num in S:
  kosuu = min(Cou[num],N-cnt)
  cnt += kosuu
  ans += num*kosuu
  
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)


def solve():
    N, K = map(int, input().split())
    AB = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        AB[a].append(b)
        AB[b].append(a)

    # AB = [sorted([int(i) for i in input().split()]) for _ in range(N - 1)]
    # AB.sort()
    p = 1
    pattern = 1
    print(dfs(AB, 1, 0, 0, 1, K, 0) % (10 ** 9 + 7))


def dfs(hen, cho, kai, ko, tag, K, oya):
    tag *= K - (ko - 1 if ko > 0 else 0) - (2 if kai >= 2 else kai)
    next_ko = hen[cho].copy()
    if oya != 0:
        next_ko.remove(oya)
    # for h in hen:
    #     if cho in h and not (oya in h):
    #         x = h[0] if h[1] == cho else h[1]
    #         next_ko.append(x)
    # print(cho, ko, kai, next_ko, tag)
    # print(K - (ko - 1 if ko > 0 else 0))
    # print((2 if kai >= 2 else kai))
    # input()
    # print(cho, next_ko)
    # input()
    for i in range(len(next_ko)):
        tag = dfs(hen, next_ko[i], kai + 1, i + 1, tag, K, cho)
    return tag


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)


def solve():
    N, K = map(int, input().split())
    AB = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        AB[a].append(b)
        AB[b].append(a)

    # AB = [sorted([int(i) for i in input().split()]) for _ in range(N - 1)]
    # AB.sort()
    print(dfs(AB, 1, 0, 0, 1, K, 0) % (10 ** 9 + 7))


def dfs(hen, cho, kai, ko, tag, K, oya):
    tag *= K - (ko - 1 if ko > 0 else 0) - (2 if kai >= 2 else kai)
    next_ko = hen[cho].copy()
    if oya != 0:
        next_ko.remove(oya)
    for i in range(len(next_ko)):
        tag = dfs(hen, next_ko[i], kai + 1, i + 1, tag, K, cho)
    return tag % (10 ** 9 + 7)


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

import bisect

def solve():
    N, Q = [int(_) for _ in input().split()]
    STX = []
    for i in range(N):
        Si, Ti, Xi = [int(_) for _ in input().split()]
        STX.append((Si - Xi, Ti - Xi, Xi))
    D = []
    for i in range(Q):
        D.append((int(input()), i))
    STX.sort(key = lambda x:x[2])
    # D have already been sorted based on settings on problem
    ans = [-1] * Q
    for i in range(N):
        Li, Ri, Xi = STX[i]
        if len(D) == 0:
            break
        it = bisect.bisect_left(D, (Li, -1))
        while it < len(D):
            if D[it][0] >= Ri:
                break
            ans[D[it][1]] = Xi
            D.pop(it)
    for i in range(Q):
        print (ans[i])

if __name__ == '__main__':
    solve()


### FIXED CODE ###

import bisect

def solve():
    N, Q = [int(_) for _ in raw_input().split()]
    STX = []
    for i in range(N):
        Si, Ti, Xi = [int(_) for _ in raw_input().split()]
        STX.append((Si - Xi, Ti - Xi, Xi))
    D = []
    for i in range(Q):
        D.append((int(raw_input()), i))
    STX.sort(key = lambda x:x[2])
    # D have already been sorted based on settings on problem
    ans = [-1] * Q
    l = [None] * Q
    for i in range(N):
        Li, Ri, Xi = STX[i]
        lit = bisect.bisect_left(D, (Li, -1))
        rit = bisect.bisect_left(D, (Ri, -1))
        while lit < rit:
            if l[lit] is not None:
                lit = l[lit]
            else:
                ans[D[lit][1]] = Xi
                l[lit] = rit
                lit += 1
    for i in range(Q):
        print ans[i]

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

import sys
from collections import deque
H,W = map(int,sys.stdin.readline().rstrip().split())
map = [[i for i in map(str,sys.stdin.readline().rstrip())] for _ in range(H)]
dist = [[-1]*W for _ in range(H)]
q = deque()
for i in range(H):
  for j in range(W):
    if map[i][j] == '#':
      q.append((i,j))
      dist[i][j] = 0

def bfs():
  while q:
    x,y = q.popleft()
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0<= nx < H and 0 <= ny < W and map[nx][ny] == '.' and dist[nx][ny] == -1:
        dist[nx][ny] = dist[x][y] + 1
        q.append((nx,ny))
bfs()
ans = 0
for i in range(H):
  ans = max(max(dist[i][:]),ans)
print(ans)

### FIXED CODE ###

import sys
from collections import deque
H,W = map(int,sys.stdin.readline().rstrip().split())
map = [[i for i in map(str,sys.stdin.readline().rstrip())] for _ in range(H)]
dist = [[-1]*W for _ in range(H)]
q = deque()
for i in range(H):
  for j in range(W):
    if map[i][j] == '#':
      q.append((i,j))
      dist[i][j] = 0

def bfs():
  while q:
    x,y = q.popleft()
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0<= nx < H and 0 <= ny < W and map[nx][ny] == '.' and dist[nx][ny] == -1:
        dist[nx][ny] = dist[x][y] + 1
        q.append((nx,ny))
bfs()
ans = 0
for i in range(H):
  ans = max(max(dist[i][:]),ans)
print(ans)