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

H,W = [int(i) for i in input().split()]

A = []
lst = []
P = []
for j in range(H):
    a = list(input())
    for i in range(W):
        if a[i] == '#':
            P.append([j,i])
            lst.append([j,i])
    A.append(a)

ans = [[0 for _ in range(W)] for _ in range(H)]
count = 0

while len(P) != 0:
    hNow,wNow = P.pop(0)
    if hNow-1 >= 0:
        if [hNow-1,wNow] not in lst:
            lst.append([hNow-1,wNow])
            P.append([hNow-1,wNow])
            ans[hNow-1][wNow] = ans[hNow][wNow]+1
    if hNow+1 < H:
        if [hNow+1,wNow] not in lst:
            lst.append([hNow+1,wNow])
            P.append([hNow+1,wNow])
            ans[hNow+1][wNow] = ans[hNow][wNow]+1
    if wNow-1 >= 0:
        if [hNow,wNow-1] not in lst:
            lst.append([hNow,wNow-1])
            P.append([hNow,wNow-1])
            ans[hNow][wNow-1] = ans[hNow][wNow]+1
    if wNow+1 < W:
        if [hNow,wNow+1] not in lst:
            lst.append([hNow,wNow+1])
            P.append([hNow,wNow+1])
            ans[hNow][wNow+1] = ans[hNow][wNow]+1

ans_t = 0
for i in ans:
    q = max(i)

    ans_t = max(ans_t,q)
print(ans_t)


### FIXED CODE ###

from collections import deque

H,W = [int(i) for i in input().split()]
l = [list(input()) for _ in range(H)]
ans = [[-1]*W for _ in range(H)]
q = deque()

for i in range(H):
    for j in range(W):
        if l[i][j] == '#':
            q.append([i,j])
            ans[i][j] = 0

t = 0
while q:
    i,j = q.popleft()
    for next_i, next_j in [[i+1,j], [i-1,j], [i,j+1], [i,j-1]]:
        if 0 <= next_i < H and 0 <= next_j < W:
            if ans[next_i][next_j] == -1 and l[next_i][next_j] == '.':
                ans[next_i][next_j] = ans[i][j] + 1
                t = max(t, ans[next_i][next_j])
                q.append([next_i,next_j])

print(t)
### BUGGY CODE ###

import time, sys
sys.setrecursionlimit(int(1e7))

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

friends = [[] for i in range(n)]
cands = [None for i in range(n)]
cycles = []
visited = [False for i in range(n)]
count = [0 for i in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    friends[a].append(b)
    friends[b].append(a)

def dfs(x):
    visited[x] = True
    cycle.append(x)
    for i in friends[x]:
        if not visited[i]:
            dfs(i)
    return


for i, v in enumerate(visited):
    if v:
        continue
    cycle = []
    dfs(i)
    l = len(cycle)
    ind = len(cycles)
    cycles.append(cycle)
    for fr in cycle:
        cands[fr] = ind
        count[fr] = l - 1 - len(friends[fr])


for _ in range(k):
    a, b = map(lambda x: int(x)-1, input().split())
    if a in cycles[cands[b]]:
        count[a] -= 1
        count[b] -= 1

for i in count:
    print(i, end=" ")

### FIXED CODE ###

import time, sys
sys.setrecursionlimit(int(1e7))

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

friends = [[] for i in range(n)]
cands = [None for i in range(n)]
cycles = []
visited = [False for i in range(n)]
count = [0 for i in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    friends[a].append(b)
    friends[b].append(a)

def dfs(x):
    visited[x] = True
    cycle.add(x)
    for i in friends[x]:
        if not visited[i]:
            dfs(i)
    return


for i, v in enumerate(visited):
    if v:
        continue
    cycle = set()
    dfs(i)
    l = len(cycle)
    ind = len(cycles)
    cycles.append(cycle)
    for fr in cycle:
        cands[fr] = ind
        count[fr] = l - 1 - len(friends[fr])


for _ in range(k):
    a, b = map(lambda x: int(x)-1, input().split())
    if a in cycles[cands[b]]:
        count[a] -= 1
        count[b] -= 1

for i in count:
    print(i, end=" ")
### BUGGY CODE ###

n = int(input())
a = input().split()
b = []
for i in range(n):
    n = a[i]
    b.append(n)
    b = b[::-1]

print(*b)

### FIXED CODE ###

n = int(input())
a = input().split()

a_odd = a[0::2]
a_even = a[1::2]

if n % 2 == 1:
    print(" ".join(a_odd[::-1] + a_even))
else:
    print(" ".join(a_even[::-1] + a_odd))
### BUGGY CODE ###


n, m = map(int, input().split())

dp = [[float("inf") for _ in range(2 ** n)] for i in range(m + 1)]
dp[0][0] = 0

pattern = {0}

for i in range(1, m+1):
  ai, bi = map(int, input().split()) 
  ci_bit = sum(2 ** (cij - 1) for cij in map(int, input().split()))
  new_pattern = set()
  for j in pattern:
    dp[i][j | ci_bit] = min(dp[i][j | ci_bit], dp[i-1][j] + ai)
    dp[i][j] = min(dp[i][j], dp[i-1][j])
    new_pattern.add(j | ci_bit)
  pattern |= new_pattern


print(-1 if dp[m][2**n - 1] == float("inf") else dp[m][2**n - 1])

### FIXED CODE ###

# 15:20-

n, m = map(int, input().split())

dp = [[float("inf") for _ in range(2 ** n)] for i in range(m + 1)]
dp[0][0] = 0

pattern = {0}

for i in range(1, m+1):
  ai, bi = map(int, input().split()) 
  ci_bit = sum(2 ** (cij - 1) for cij in map(int, input().split()))
  new_pattern = set()
  for j in pattern:
    dp[i][j | ci_bit] = min(dp[i][j | ci_bit], dp[i-1][j] + ai)
    dp[i][j] = min(dp[i][j], dp[i-1][j])
    new_pattern.add(j | ci_bit)
  pattern |= new_pattern


print(-1 if dp[m][2**n - 1] == float("inf") else dp[m][2**n - 1])
### BUGGY CODE ###

def main():
    from fractions import gcd

    MOD = 10 ** 9 + 7

    N = int(input())

    A = list(map(int, input().split()))

    B = [1] * (N + 1)

    for index, a in enumerate(A):
        tmp = gcd(B[index], a)
        B[index + 1] = B[index] * a // tmp

    C = [1] * (N + 1)
    for i in range(N - 1, -1, -1):
        tmp =gcd(C[i + 1], A[i])
        C[i] = C[i + 1] * A[i] // tmp

    # print (B)
    # print (C)

    ans = 0
    for i in range(N):
        tmp1 = gcd(B[i], C[i + 1])
        tmp2 = B[i] * C[i + 1] // tmp1

        tmp3 = gcd(tmp2, A[i])
        tmp4 = tmp2 * A[i] // tmp3

        ans += (tmp4 * pow(A[i], MOD - 2, MOD) % MOD)
        ans %= MOD

        # print (ans)

    print (ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from fractions import gcd

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

    MOD = 10 ** 9 + 7

    tmp = 1
    for a in A:
        tmp *= a // gcd(tmp, a)

    ans = 0
    for a in A:
        ans += tmp // a
    ans %= MOD

    print (ans)

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

def main():
    s = input()
    t = input()
    if not set(sorted(t)) <= set(sorted(s)):
        print(-1)
        return
    # print(set(sorted(t)) , set(sorted(s)))
    ret = 0
    ind = 0
    while not ind == len(t):
        if s[ret % len(s)] == t[ind]:
            ind += 1
        ret += 1
    print(ret)
    return


if __name__ == "__main__":
    main()

### FIXED CODE ###

import copy


def main():
    s = input()
    ss = s + s
    t = input()
    if not set(sorted(t)) <= set(sorted(s)):
        print(-1)
        return
    cnt_s = {}
    cnt_t = {}
    pos = {}  # [({}) for x in range(len(s))]
    for i in range(len(ss)):
        c = ss[i]
        if c not in cnt_s:
            cnt_s[c] = 0
            pos[c] = []
        cnt_s[c] += 1
        pos[c].append(i)
    # for k in pos.keys():
    #     pos[k].reverse()
    # org_pos = copy.deepcopy(pos)
    ret = 0
    tmp = -1
    for i in range(len(t)):
        c = t[i]
        if pos[c][0] > tmp:
            tmp = pos[c][0]
            continue
        l = 1
        r = len(pos[c]) - 1
        while not l == r:
            p = (l + r) // 2
            if pos[c][p] > tmp:
                r = p
            if pos[c][p] <= tmp:
                l = p + 1
        tmp = pos[c][l]
        if tmp >= len(s):
            ret += len(s)
            tmp -= len(s)
    ret += tmp + 1
    print(ret)
    return


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

s = input()
mod = [0] * 2019
mod[0] = 1
d = 1
n = 0
for i in reversed(s):
    n += int(i) * d
    n %= 2019
    d *= 10
    mod[n % 2019] += 1
print(sum(i*(i-1)//2 for i in mod))


### FIXED CODE ###

s = input()
mod = [0] * 2019
mod[0] = 1
d = 1
n = 0
for i in reversed(s):
    n += int(i) * d
    n %= 2019
    d *= 10
    d %= 2019
    mod[n % 2019] += 1
print(sum(i*(i-1)//2 for i in mod))
### BUGGY CODE ###

import math
import os
import sys
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

MOD = 10 ** 9 + 7
N, K = list(map(int, sys.stdin.readline().split()))


@lru_cache(maxsize=None)
def next_max(n):
    # ある数と隣り合わせになれる数
    return int(N // n)


NM = []
prev = 0
for i in range(1, int(math.sqrt(N)) + 2):
    NM.append(N - next_max(i) - prev)
    prev = (N - next_max(i))


# @lru_cache(maxsize=None)
# @debug
# def rec1(n, k):
#     if k <= 1:
#         return n
#
#     ret = 0
#     cnt = n
#     while cnt > 0:
#         i = next_max(cnt)
#         p = NM[i] if i < len(NM) else 1
#         ret = (ret + rec1(i, k - 1) * p) % MOD
#         cnt -= p
#     return ret
#
#
# #
# # ans = rec1(N, K)
# # print(ans % MOD)


@lru_cache(maxsize=None)
def rec(n, k):
    if n <= 0:
        return 0
    if k <= 1:
        return n

    i = next_max(n)
    p = NM[i] if i < len(NM) else 1
    ret = rec(i, k - 1)
    cum = rec(n - p, k)
    ret = ret * p % MOD
    return (cum + ret) % MOD


ans = rec(N, K)
print(ans % MOD)


### FIXED CODE ###

import math
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

MOD = 10 ** 9 + 7
N, K = list(map(int, sys.stdin.readline().split()))

NM = []
prev = 0
for i in range(1, int(math.sqrt(N)) + 2):
    m = int(N // i)
    NM.append(N - m - prev)
    prev = N - m

cnt = N
nums = []
while cnt >= 1:
    nums.append(cnt)
    i = int(N // cnt)
    p = NM[i] if i < len(NM) else 1
    cnt -= p
nums.reverse()

# dp[k][n]: rec(n, k)
dp = defaultdict(lambda: defaultdict(int))
for n in nums:
    dp[1][n] = n
for k in range(2, K + 1):
    for n in nums:
        i = int(N // n)
        p = NM[i] if i < len(NM) else 1
        ret = dp[k - 1][i] * p % MOD
        cum = dp[k][n - p]
        dp[k][n] = (cum + ret) % MOD

ans = dp[K][N]
print(ans % MOD)

# ans = rec(N, K)
# print(ans % MOD)
### BUGGY CODE ###

N,K = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
data = []
for j in range(N-K+1):
    data.append(sum([p[-i] for i in range(j,K+j)]))

print((max(data)+K)/2)

### FIXED CODE ###

N,K = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]

s = sum([p[i] for i in range(K)])
data = [s]
for i in range(N-K):
    s = s-p[i]+p[i+K]
    data.append(s)
print((max(data)+K)/2)
### BUGGY CODE ###

S=input()
N=len(S)
ans=0
for i in range(N):
    for j in range(i,N):
        tmp=S[i:j+1]
        if int(tmp)%2019==0:
            #print(tmp)
            ans+=1

print(ans)

### FIXED CODE ###

S=input()
N=len(S)
#「連続する区間」についての問題では、”累積和的なもの”をとるのが定石である。
#Sの連続する区間が、右からa文字分から、右からb文字分を取り除いたものであるとき
#その区間の整数が2019の倍数になるということは、s[a]とs[b]を2019で割ったあまりが等しい
#十分条件であることは分かったが、必要条件であるのか
#結論として必要条件でもある
#なぜなら2019と10は互いに素であるからである。

T=[]
T.append(0)
tmp=""
d=[0 for _ in range(2019)]
d[0]=1
r=0
t=1
for i in range(N):
    s=S[N-1-i]
    r+=int(s)*t
    r%=2019
    t*=10
    t%=2019 
    d[r]+=1

ans=0

print(sum(i*(i-1)//2 for i in d))
### BUGGY CODE ###

a,b,c = input().split()
n = int(a)
K = int(b)
Q = int(c)
CAList = []
AllP = []
for i in range(0,Q):
    CAList.append(int(input()))

for j in range(0,n):
    AllP.append(K)

for k in range(0,Q):
    box = AllP[CAList[k]-1]
    for l in range(0,n):
        AllP[l] = AllP[l] - 1
    AllP[CAList[k]-1] = box
    
for m in range(0,n):
    if AllP[m] >= 1:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

a,b,c = input().split()
n = int(a)
K = int(b)
Q = int(c)
CAList = []
AllP = []
for i in range(0,Q):
    CAList.append(int(input()))

for j in range(0,n):
    AllP.append(K-Q)

for k in range(0,Q):
    AllP[CAList[k]-1] += 1
    
for m in range(0,n):
    if AllP[m] >= 1:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n,*a=map(int,open(0).read().split())
ans=1
for i in a:
    ans*=i
if ans>10**18:
    ans=-1
print(ans) 

### FIXED CODE ###

n,*a=map(int,open(0).read().split())
if 0 in a:
    print(0)
    exit()
ans=1
for i in a:
    ans*=i
    if ans>10**18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

n,m,k = map(int,input().split())
a = [0]+list(map(int,input().split()))
b = [0]+list(map(int,input().split()))
s = [0]*(n+1)
t = [0]*(m+1)
p = m-1
q = n-1
x = 0
for i in range(n+1):
    s[i] += x + a[i]
    x = s[i]
x = 0
for i in range(m+1):
    t[i] += x + b[i]
    x = t[i]
#print(s,t)
x = 1
while(1):
#for i in range(30):
    f = 0
    #print(x)
    for j in range(x+1):
        if(m>=x-j):
            if(n >= j):
                if(s[j]+t[x-j] <= k):
                    #print(j,x-j)
                    f = 1
                    break
            else:
                break
    if(f == 0):
        break
    x += 1
print(x-1)

### FIXED CODE ###

n,m,k = map(int,input().split())
a = [0]+list(map(int,input().split()))
b = [0]+list(map(int,input().split()))
s = [0]*(n+1)
t = [0]*(m+1)
x = 0
for i in range(n+1):
    s[i] += x + a[i]
    x = s[i]
if(s[-1] <= k):
    p = n
else:
    for i in range(n+1):
        if(s[i] >= k):
            p = i
            break
x = 0
for i in range(m+1):
    t[i] += x + b[i]
    x = t[i]
if(t[-1] <= k):
    p = min(p,m)
else:
    for i in range(m+1):
        if(t[i] >= k):
            p = max(p,i)
            break
#print(s,t)
while(1):
    f = 0
    for j in range(p-min(p,m),min(p,n)+1):
        #print(j,p-j)
        if(s[j]+t[p-j] <= k):
            #print(j,x-j)
                f = 1
                break
    if(f == 0):
        break
    p += 1
print(p-1)
### BUGGY CODE ###

import heapq
import copy

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


def dfs(q, have, count, operate):
    if operate == 0:
        heapq.heappush(have, q[0])
        q = q[1:]
    elif operate == 1:
        heapq.heappush(have, q[-1])
        q = q[:-1]
    elif operate == 2:
        sub = heapq.heappop(have)
        q.insert(0, sub)
    elif operate == 3:
        sub = heapq.heappop(have)
        q.append(sub)

    count += 1
    if count >= k:
        return sum(have)

    a = -float('inf')
    b = -float('inf')
    c = -float('inf')
    d = -float('inf')
    e = dfs(q, have, count, -1)  # 何もしない

    if len(q) > 0:
        a = dfs(copy.deepcopy(q), copy.deepcopy(have), count, 0)
        b = dfs(copy.deepcopy(q), copy.deepcopy(have), count, 1)
    if len(have) > 0:
        c = dfs(copy.deepcopy(q), copy.deepcopy(have), count, 2)
        d = dfs(copy.deepcopy(q), copy.deepcopy(have), count, 3)

    return max(a, b, c, d, e)


print(dfs(v, [], -1, -1))


### FIXED CODE ###

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

ans = 0
for a in range(min(n, k) + 1):
    for b in range(min(n, k) - a + 1):
        li = v[:a]
        if b > 0:
            li += v[-b:]
        li.sort()
        count = 0
        while (a + b + count < k):
            if len(li) > 0 and li[0] < 0:
                count += 1
                li = li[1:]
            else:
                break
        ans = max(ans, sum(li))

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

# -*- coding: utf-8 -*-
N,X,Y = map(int,input().split())
ToltN=N*(N-1)/2
Dist=[[0 for i in range(N)] for i in range(N)]
for i in range(N):
    for j in range(i,N):
        Dist[i][j] = j-i
for i in range(N):
    for j in range(i,N):
        MyDist=abs(i-(X-1))+abs(j-(Y-1))+1

        if MyDist<Dist[i][j]:
            Dist[i][j]=MyDist
for j in range(N-1):
    ans=0
    for i in range(N):
        ans+=Dist[i].count(j+1)

    print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import collections
N,X,Y = map(int,input().split())
ToltN=N*(N-1)/2
Dist=[[0 for i in range(N)] for i in range(N)]
c=[0]*N
for i in range(N):
    for j in range(i+1,N):
        MyDist=abs(i-(X-1))+abs(j-(Y-1))+1
        if MyDist<j-i:
            Dist[i][j]=MyDist
            c[MyDist-1]+=1
        else:
            Dist[i][j] = j-i
            c[j-i-1]+=1
for i in range(N-1):
    print(c[i])
### BUGGY CODE ###

s = input()
t = input()

sum = 0
word = s
try:
    for char in t:
        index = word.index(char)+ 1
        sum+=index 
        word = word[index:] + s
except:
    print(-1)
else:     
    print(sum)

### FIXED CODE ###

import sys
s = input()
t = input()
tset = set(t)
slen = len(s)
if len(tset - set(s)) != 0:
    print(-1)
    sys.exit()
s2t = [i - ord('a') for i in (s + s).encode('ascii')]
lut = [[-1 for _ in range(slen)] for _ in range(26)]
for c in tset:
  b = ord(c) - ord('a')
  j = 0
  for i in range(slen * 2 - 1, -1, -1):
    if s2t[i] == b:
      j = 0
    else:
      j += 1
    if i < slen:
      lut[b][i] = j
p = 0
for c in t:
  b = ord(c) - ord('a')
  p += lut[b][p % slen] + 1
print(p)
### BUGGY CODE ###

from sys import stdin
f_i = stdin

mod = 10 ** 9 + 7

N, K = map(int, f_i.readline().split())
A = sorted(map(int, f_i.readline().split()))

comb = 1
ans = A[K-1] - A[N-K]
for i, j, A_s, A_t in zip(range(K, N), range(1, N), A[K:], A[N-K-1::-1]):
    comb = comb * i // j
    ans += (A_s - A_t) * comb

print(ans % mod)

### FIXED CODE ###

def solve():
    from sys import stdin
    f_i = stdin
    
    mod = 10 ** 9 + 7
    
    N, K = map(int, f_i.readline().split())
    A = sorted(map(int, f_i.readline().split()))
    
    comb = 1
    ans = A[K-1] - A[N-K]
    for i, j in zip(range(K, N), range(1, N)):
        comb = comb * i * pow(j, mod - 2, mod) % mod
        ans += (A[i] - A[N-i-1]) * comb
        ans %= mod
    
    print(ans)

solve()
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10000000)


N=input()
A=map(int, sys.stdin.readline().split())

dp=[ [ 0 for i in range(N) ]  for j in range(N) ]

def func(x,y,cnt):
	if dp[x][y]>0: return dp[x][y]
	ret=0
	if x==y:
		if cnt%2==0:
			ret=A[x]
			dp[x][y]=ret
			return ret
		else:
			ret=-1*A[x]
			dp[x][y]=ret
			return ret
	if cnt%2==0:
		cnt+=1
		ret=max( func(x,y-1,cnt)+A[y] , func(x+1,y,cnt)+A[x]  )
	else:
		cnt+=1
		ret=min( func(x,y-1,cnt)-A[y] ,func(x+1,y ,cnt)-A[x] )

	dp[x][y]=ret
	return ret

func(0,N-1,0)

print dp[0][N-1]


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

N=input()
A=map(int, sys.stdin.readline().split())

dp=[ [ None for i in range(N) ]  for j in range(N) ]


for i in range(N-1,-1,-1):
	if N%2==0:
		dp[i][i]=A[i]*-1
	else:
		dp[i][i]=A[i]


for i in range(N-2,-1,-1):
	for j in range(i+1,N):
		t=N-(j-i+1)	#残りの要素数
		if t%2==0:
			if dp[i][j] is None : dp[i][j]=float("-inf")
			dp[i][j]=max(dp[i][j] , dp[i][j-1]+A[j])
			dp[i][j]=max(dp[i][j] , dp[i+1][j]+A[i])
		else:
			if dp[i][j] is None : dp[i][j]=float("inf")
			dp[i][j]=min(dp[i][j] , dp[i][j-1]-A[j])
			dp[i][j]=min(dp[i][j] , dp[i+1][j]-A[i])

print dp[0][N-1]
### BUGGY CODE ###

# coding: utf-8

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

inf = pow(10, 10)

# current_shortests = [0] + [inf] * (n-1)

in_processing = [0]  # node-number
in_processing_len = [0]
shortest_fixed = []  # node-number
shortest_fixed_len = []


def argmin(l):
    output = 0
    for i in range(len(l)):
        if l[i] < l[output]:
            output = i

    return output


def search(l, v):
    for i in range(len(l)):
        if l[i] == v:
            return i


def fun():
    k = argmin(in_processing_len)
    node = in_processing[k]
    while node != n-1:

        # print("---------")
        # print(in_processing)
        # print(in_processing_len)
        # print(shortest_fixed)
        # print(shortest_fixed_len)
        # print(k)
        # print(node)
        # print("---------")

        # if node == n-1:
        #     return in_processing_len[k]

        shortest_fixed.append(node)
        shortest_fixed_len.append(in_processing_len[k])
        del in_processing[k]
        del in_processing_len[k]

        if node+1 < n and node+1 not in shortest_fixed:
            if node+1 not in in_processing:
                in_processing.append(node+1)
                in_processing_len.append(
                    shortest_fixed_len[-1] + abs(h[node+1] - h[node]))
            else:
                idx = search(in_processing, node+1)
                if in_processing_len[idx] > shortest_fixed_len[-1] + abs(h[node+1] - h[node]):
                    in_processing_len[idx] = shortest_fixed_len[-1] + abs(h[node+1] - h[node])
        if node+2 < n and node+2 not in shortest_fixed:
            if node+2 not in in_processing:
                in_processing.append(node+2)
                in_processing_len.append(
                    shortest_fixed_len[-1] + abs(h[node+2] - h[node]))
            else:
                idx = search(in_processing, node+2)
                if in_processing_len[idx] > shortest_fixed_len[-1] + abs(h[node+2] - h[node]):
                    in_processing_len[idx] = shortest_fixed_len[-1] + abs(h[node+2] - h[node])

        k = argmin(in_processing_len)
        node = in_processing[k]

    return in_processing_len[k]


print(fun())


### FIXED CODE ###

# coding: utf-8

"""
20191116
"""

N = int(input())
h = list(map(int, input().split()))

cost = [0, abs(h[1]-h[0])] + [None for _ in range(N-2)]

for i in range(2, N):
    cost[i] = min(cost[i-1] + abs(h[i]-h[i-1]), cost[i-2] + abs(h[i]-h[i-2]))

print(cost[N-1])
### BUGGY CODE ###

import numpy as np
N,M=map(int,input().split())
A=[]
for _ in range(M):
    A.append(int(input()))

mod=10**9+7

dp=np.zeros(N+1)
dp[0]=1
if 1 not in A:
    dp[1]=1
else:
    dp[1]=0

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

print(int(dp[N]))

### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
INF = 1000000007

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in a:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF

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

import sys
from operator import itemgetter
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
def main():
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while(e[0] > d):
			if cont == True:
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			else:
				mini = min(kouho)
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			cont = True
			if q < Q-1:
				q = q + 1
				d = int(inputs())
			else:
				flag = True
				q = q + 1
				break
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			cont = False
	for t in [None]*(Q-q):
		print(-1)
		
def sub():
	V = [list(map(int,inputs().split())) for p in [0]*N]
	M = [int(inputs()) for p in [0]*Q]
	V.sort(key = lambda x:(x[2],x[0],x[1]))
	for v in V:
		v[0] -= v[2]
		v[1] -= v[2] + 1
	for m in M:
		for n in range(N):
			if V[n][0] <=m and m <= V[n][1]:
				print(V[n][2])
				break
		else:
			print(-1)


if Q<1000:
	sub()
else:
	main()

### FIXED CODE ###

import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				print(mini-(mini//1000000001)*1000000002)
			else:
				mini = min(kouho)
				print(mini-(mini//1000000001)*1000000002)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			if mini == e[2]:
				cont = False
	for t in [None]*(Q-q):
		print(-1)
main()