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

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))

    dp = [0] * (n)
    dp[1] = abs(h[0] - h[1])
    for i in range(2, n):
        J = min(k, i)
        dp2 = [0] * J
        for j in range(1, J + 1):
            dp2[j - 1] = dp[i - j] + abs(h[i - j] - h[i])
        dp[i] = min(dp2)
    print(dp[-1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

import numpy as np


def main():
    n, k = map(int, input().split())
    height = np.fromstring(input(), 'int32', sep=' ')
    height = np.append(height, [0] * (k - 1))

    dp = np.full((n + k - 1), 10 ** 9, dtype='int')
    dp[0] = 0

    for i in range(n - 1):
        default_val = dp[i + 1:i + 1 + k]
        new_val = dp[i] + np.abs(height[i + 1:i + 1 + k] - height[i])
        dp[i + 1:i + 1 + k] = np.minimum(default_val, new_val)
    print(dp[n - 1])


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

k,s = map(int,input().split())
cnt = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z ==s:
                cnt += 1
print(cnt)

### FIXED CODE ###

k,s = map(int,input().split())
cnt = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if z >= 0 and z <= k:
            cnt += 1

print(cnt)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import math
h,n = map(int, input().split())
aa = [None for _ in range(n+1)]
bb = [None for _ in range(n+1)]
mp = [[None for _ in range(n+1)] for _ in range(h+1)]
# 体力i 技の種類j
for j in range(1, n+1):
  aa[j], bb[j] = map(int, input().split())
for i in range(1, h+1):
    mp[i][0] = float("inf")
for j in range(1, n+1):
    for i in range(1, h+1):
        if i - aa[j] >= 1:
          # print(i, j, i - aa[j])
          mp[i][j] = min(mp[i][j-1], mp[i - aa[j]][j] + bb[j])
        else:
          mp[i][j] = min(mp[i][j-1], bb[j])
print(mp[h][n])

### FIXED CODE ###

# coding: utf-8
# Your code here!
def main():
    import math
    h,n = map(int, input().split())
    aa = [0]*(n+1)
    bb = [0]*(n+1)
    mp = [[None for _ in range(n+1)] for _ in range(h+1)]
    # 体力i 技の種類j
    for j in range(1, n+1):
      mp[0][j] = 0
      aa[j], bb[j] = map(int, input().split())
    for i in range(1, h+1):
        mp[i][0] = float("inf")
    for j in range(1, n+1):
        for i in range(1, h+1):
        	mp[i][j] = min(mp[i][j-1], mp[max(0, i - aa[j])][j] + bb[j])
    print(mp[h][n])

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

X,Y,A,B,C = map(int, input().split())
p=list(map(int, input().split()))
q=list(map(int, input().split()))
r=list(map(int, input().split()))

P=sorted(p, reverse=True)
Q=sorted(q, reverse=True)
R=sorted(r, reverse=True)

a=[0]
b=[0]
c=[0]

for i in P[:X]:
    a.append(a[-1]+i)
    
for i in Q[:Y]:
    b.append(b[-1]+i)
      
for i in R:
    c.append(c[-1]+i)
    
ans={0}

for i in range(len(c)):
    for j in range(len(b)):
        for k in range(len(a)):
            if i+j+k==X+Y:
                tmp=c[i]+b[j]+a[k]
                #print(tmp)
                ans.add(tmp)
            else:
                pass
            
print(max(ans))

### FIXED CODE ###

X,Y,A,B,C = map(int, input().split())
P=sorted(list(map(int,input().split())), reverse=True)
Q=sorted(list(map(int,input().split())), reverse=True)
R=sorted(list(map(int,input().split())), reverse=True)

C = P[:X] + Q[:Y] + R
C.sort(reverse=True)

print(sum(C[:X+Y]))
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]
buf = 1
for i in range(N) :
    buf = buf * A[i]
if buf > 10**(18) :
    print("-1")
else :
    print(buf)

### FIXED CODE ###

import numpy as np
N = int(input())
buf = list(map(int,input().split()))
cnt = 1
flag = True
for i in range(N) :
    if buf[i] == 0 :
        print(0)
        exit()
for i in range(N) :
    cnt = cnt * buf[i]
    if cnt > 10 ** 18 :
        flag = False
        break

if flag == True :
    print(cnt)
else :
    print("-1")
### BUGGY CODE ###

s=input().strip()
K=int(input())
sorteds=sorted(set(s))
ct=0
subsset=set()
for c in sorteds:
    ct+=1
    ixs=[]
    ss=s
    ix=0
    while len(ss):
        ii=ss.find(c)
        if ii==-1:break
        ixs.append(ix+ii)
        ix=ix+ii
        ss=ss[ii:]
        for i in range(len(ss)):
            subsset.add(ss[:1+i])
        ss=ss[1:]
    if len(subsset)>=K:
        break
print(sorted(list(subsset))[K-1])

### FIXED CODE ###

s=input().strip()
K=int(input())
sorteds=sorted(set(s))
ct=0
subsset=set()
for c in sorteds:
    ct+=1
    ixs=[]
    ss=s
    ix=0
    while len(ss):
        ii=ss.find(c)
        if ii==-1:break
        ixs.append(ix+ii)
        ix=ix+ii
        ss=ss[ii:]
        for i in range(min(len(ss),K)):
            subsset.add(ss[:1+i])
        ss=ss[1:]
    if len(subsset)>=K:
        break
print(sorted(list(subsset))[K-1])
### BUGGY CODE ###

N,K = map(int,input().split())
X = list(map(int,input().split()))
ANS = []
for i in range(N-K+1) :
    L = X[i:K+i]
    if min(L)*max(L) >= 0 :
        ANS.append(max(abs(min(L)),max(L)))
    else :
        ANS.append(min(abs(min(L))*2+abs(max(L)),abs(max(L))*2+abs(min(L))))
print(min(ANS))
#print(ANS)



### FIXED CODE ###

N,K = map(int,input().split())
L = list(map(int,input().split()))
ANS = []
for i in range(len(L)-K+1) :
    p = L[i]
    q = L[i+K-1]
    if p*q == 0 :
        r = abs(p-q)
    elif p*q < 0 :
        r = 2*min(abs(p),q) + max(abs(p),q)
    else :
        if p > 0 :
            r = q
        else :
            r = abs(p)
    ANS.append(r)
ans = min(ANS)
print(ans)
### BUGGY CODE ###

def main():
  N=int(input())
  A=list(set(list(map(int,input().split()))))

  if min(A)==1:
    print(1)
    exit()

  while len(A)>1:
    monster_min = A.pop(A.index(min(A)))
    for i in range(len(A)):
      A[i] %= monster_min
    A.sort()
    for i in A[:]:  
      if i == 0: A.remove(i)
      else: continue
    A.append(monster_min)

  print(A[0])

if __name__ == "__main__":
  main()

### FIXED CODE ###

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

if min(A)==1:
  print(1)
  exit()

while len(A)>1:
  monster_min = A.pop(A.index(min(A)))
  for i in range(len(A)):
    A[i] %= monster_min
  A.sort()
  for i in A[:]:  
    if i == 0: A.remove(i)
    else: continue
  A.append(monster_min)

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

from functools import lru_cache

import sys
sys.setrecursionlimit(10**5+10)

mod = 10**9+7

S = input()
S = S[::-1]
#print(S)

# 0~i桁目までの部分文字列において
# (mod 13)がbとなるパターン数を返す
@lru_cache(maxsize=None)
def search(i,rem):
	if i==len(S):
		return 1 if rem==5 else 0
	
	ch = int(S[i]) if S[i]!='?' else -1

	res = 0
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		num = d*(10**i)%13
		res += search(i+1,(rem+num)%13)
	return res%mod

print(search(0,0))


### FIXED CODE ###

S = input()
S = S[::-1]
#print(S)

mod = 10**9+7

tblpow = [1]
for i in range(1,len(S)+1):
	tblpow.append(10*tblpow[i-1]%13)

dp = [0]*13
dp[0] = 1
for i in range(len(S)-1,-1,-1):
	ch = int(S[i]) if S[i]!='?' else -1
	temp = [0]*13
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		for m in range(13):
			temp[(d*tblpow[i]+m)%13] += dp[m]
	for m in range(13):
		temp[m] %= mod
	dp = temp
print(dp[5])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

commands = {"insert": lambda x, l: insert(x, l),
            "delete": lambda x, l: delete(x, l),
            "deleteFirst": lambda x, l: deleteFirst(x, l),
            "deleteLast": lambda x, l: deleteLast(x, l)}


# ??£??????????????????????????????x?????????????´?????¶?????¶????
def insert(x, l):
    l = [x] + l
    return l


# ??????x??????????????????????´??????£??????????????????????????????
def delete(x, l):
    for i in xrange(len(l)):
        if l[i] == x:
            l.pop(i)
            break
    return l


# ?????????????????????????´????????????????
def deleteFirst(x, l):
    l.pop(0)
    return l


# ????????????????°????????´????????????????
def deleteLast(x, l):
    l.pop()
    return l


if __name__ == '__main__':
    N = input()
    functions, args = [], []
    for i in xrange(N):
        command = raw_input().split()
        functions.append(command[0])
        if command[0] == "deleteFirst" or command[0] == "deleteLast":
            args.append(0)
        else:
            args.append(int(command[1]))

    result = []
    for i in xrange(len(functions)):
        result = commands[functions[i]](args[i], result)
    print ' '.join(map(str, result))

### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-

''' ???????????£???????????? '''

from collections import deque

functions = {"insert": lambda obj, x: obj.insert(x),
             "delete": lambda obj, x: obj.delete(x),
             "deleteFirst": lambda obj: obj.deleteFirst(),
             "deleteLast": lambda obj: obj.deleteLast()}


class DoublyLinkedList(object):
    """ Doubly Linked List """

    def __init__(self):
        # self.list = []
        self.list = deque()

    def insert(self, x):
        """ ???????????????x?????????????´?????????\ """
        # self.list = [x] + self.list
        self.list.appendleft(x)

    def delete(self, x):
        """ ??????x??????????????????????´?????????? """
        # for i in range(len(self.list)):
        #     if self.list[i] == x:
        #         self.list.pop(i)
        #         break
        if x in self.list:
            self.list.remove(x)

    def deleteFirst(self):
        """ ?????????????????????????´?????????? """
        # self.list.pop(0)
        self.list.popleft()

    def deleteLast(self):
        """ ????????????????°????????´?????????? """
        self.list.pop()


if __name__ == '__main__':
    N = int(input())

    q = deque()
    for i in range(N):
        command = input().split()
        if command[0] == 'insert':
            q.appendleft(command[1])
        elif command[0] == 'delete':
            if command[1] in q:
                q.remove(command[1])
        elif command[0] == 'deleteFirst':
            q.popleft()
        elif command[0] == 'deleteLast':
            q.pop()

    print(' '.join(map(str, q)))

    # dll = DoublyLinkedList()
    # for i in range(N):
    #     command = input().split()
    #     if len(command) == 1:
    #         functions[command[0]](dll)
    #     elif len(command) == 2:
    #         functions[command[0]](dll, int(command[1]))
    # print(' '.join(map(str, dll.list)))
### BUGGY CODE ###


def gcd(a, b) :
  if a % b == 0 :
    return b
  
  return gcd(b, a%b)

K = int(input())
ans = 0

for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      ans += gcd(gcd(a,b) , c)

print(ans)

### FIXED CODE ###


def gcd(a, b) :
  if a % b == 0 :
    return b
  
  return gcd(b, a%b)

K = int(input())
ans = 0

for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      ans += gcd(gcd(a,b) , c)

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

n = int(input())
arr = list()
for i in range(n):
    arr.append(input())

maxi = 0
res = list()
flag = True
while True:
    if arr:
        x = max(set(arr), key = arr.count)
        if flag:
            maxi = arr.count(x)
            flag = False
            res.append(x)
            while x in arr:
                arr.remove(x)
        else:
            if arr.count(x) == maxi:
                res.append(x)
                while x in arr:
                    arr.remove(x)
            else:
                break
    else:
        break
for i in sorted(res):
    print(i)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
ans = dict()
for _ in range(N):
    k = str(input())
    if k in ans:
        ans[k]+=1
    else:
        ans.update({k:1})
groupedByValue = defaultdict(list)
for key, value in sorted(ans.items()):
    groupedByValue[value].append(key)
l = groupedByValue[max(groupedByValue)]
for i in l:
    print(i)
### BUGGY CODE ###

## bfs ##
N = int(input())
G = [[] for _ in range(N)]
dis = [-1]*N
que = []
for _ in range(N-1):
    a, b, c = map(int, input( ).split( ))
    a -= 1
    b -= 1
    G[a].append([b,c])
    G[b].append([a,c])
Q, K = map(int, input().split())
K -= 1
dis[K] = 0
que.append(K) 
while que:
    p = que.pop(0)
    for i in range(len(G[p])):
        n_p, d = G[p][i]
        if dis[n_p] != -1:
            continue
        que.append(n_p)
        dis[n_p] = dis[p] + d

for i in range(Q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    ans = dis[x]+dis[y]
    print(ans)
   
    

### FIXED CODE ###

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

N = int(input())
tree = [[] for _ in range(N)]
cost_from_k = [0]*N

def calcurate_cost(fr, to, cost):
  cost_from_k[to] += cost_from_k[fr]+cost
  for n_to, n_cost in tree[to]:
    if n_to == fr:
      continue
    if K != n_to:
      calcurate_cost(to, n_to, n_cost)
      
for i in range(N-1):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  tree[a].append((b,c))
  tree[b].append((a,c))

  
Q, K = map(int, input().split())
K -= 1
calcurate_cost(K, K, 0)

for j in range(Q):
  x, y = map(int, input().split())
  print(cost_from_k[x-1]+cost_from_k[y-1])
### BUGGY CODE ###

s = input()
k = int(input())
days = int(5e15)
for i in range(days):
    for j in range(2,10):
         s = s.replace(str(j), str(j)*j)

print(s[k-1])


### FIXED CODE ###

s,k = [input() for i in range(2)]
for i in range(int(k)):
    if int(s[i]) > 1:
        print(s[i])
        exit()
print(1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
import copy

N,M,P=map(int, sys.stdin.readline().split())

al=[ [] for i in range(N+1) ]		#隣接リスト
rev_al=[ [] for i in range(N+1) ]	#reverse隣接リスト
#辺のリスト
edge=[]

for i in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	al[a].append(b)
	rev_al[b].append(a)
	edge.append((a,b,c-P))


#ゴールからBFS
q=deque()
q.append(N)
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
while q:
	fro=q.popleft()
	Visit[fro]=1
	for to in rev_al[fro]:
		if Visit[to]==0:
			q.append(to)
			
Visit1=Visit

#スタートからBFS
q=deque()
q.append(1)
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
while q:
	fro=q.popleft()
	Visit[fro]=1
	for to in al[fro]:
		if Visit[to]==0:
			q.append(to)

Visit2=Visit

#1からもNからも到達可能な頂点の集合
V=[]
for v1,v2 in zip(Visit1,Visit2):
	V.append(v1&v2)

new_N=sum(V)

D=[ float("-inf") for _ in range(N+1) ]	#頂点１からの距離 1-indexed
D[1]=0

fedge=[]	#必要な要素だけをフィルターした辺集合
for a,b,c in edge:
	if V[a]==1 and V[b]==1:
		fedge.append((a,b,c))

#ベルマンフォード N-1回
for _ in range(new_N-1):
	for a,b,c in fedge:
		D[b]=max( D[b],D[a]+c )

D1=copy.deepcopy(D)

#ベルマンフォード 追加1回で差分が出たら閉路検出
for a,b,c in fedge:
	if D[b]!=max( D[b],D[a]+c ):
		print -1
		quit()
else:
	print max(D[N],0)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque

N,M,P=map(int, sys.stdin.readline().split())

al=[ [] for i in range(N+1) ]		#隣接リスト
rev_al=[ [] for i in range(N+1) ]	#reverse隣接リスト
#辺のリスト
edge=[]

for i in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	al[a].append(b)
	rev_al[b].append(a)
	edge.append((a,b,c-P))


#ゴールからBFS
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(N)
Visit[N]=1
while q:
	fro=q.popleft()
	for to in rev_al[fro]:
		if Visit[to]==0:
			Visit[to]=1
			q.append(to)
			
Visit1=Visit

#スタートからBFS
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(1)
Visit[1]=1
while q:
	fro=q.popleft()
	for to in al[fro]:
		if Visit[to]==0:
			Visit[to]=1
			q.append(to)

Visit2=Visit

#1からもNからも到達可能な頂点の集合
V=[]
for v1,v2 in zip(Visit1,Visit2):
	V.append(v1&v2)

new_N=sum(V)

fedge=[]	#必要な要素だけをフィルターした辺集合
for a,b,c in edge:
	if V[a]==1 and V[b]==1:
		fedge.append((a,b,c))


D=[ float("-inf") ]*(N+1)	#頂点１からの距離 1-indexed
D[1]=0

#ベルマンフォード
for i in range(new_N):
	for a,b,c in fedge:
		if D[a]==float("-inf"): continue
		alt=D[a]+c
		if D[b]<alt:
			D[b]=alt
			if i==new_N-1:
				print -1
				quit()

print max(0,D[N])
### BUGGY CODE ###

k = int(input())

if k%2 == 0 or k%5 ==0:
    print(-1)
else:
    a = 7
    while a%k != 0:
        a = int(str(a)+'7')
    print(len(str(a)))
    


### FIXED CODE ###

import sys
k = int(input())

if k%2 == 0 or k%5 ==0:
    print(-1)
else:
    a = 7%k
    if a == 0:
        print(1)
    else:
        for i in range(2, 10000000):
            a = (10*a+7)%k
            if a == 0:
                print(i)
                sys.exit()
        print(-1)
### BUGGY CODE ###

N,K=map(int,input().split())
Ds=list(input().split())
Di=list(map(int,Ds))
nex=[1]*10
for i in reversed(Di):
    nex[i-1]=nex[i]+1

def check(n):
    ns = str(N)
    for nss in ns:
        if nss in Ds:
            return False
    return True

def next(i):
    global N
    ns='{0:0>4}'.format(N)
    t=nex[int(ns[i])]
    pp=int(ns[i])+t
    if pp >=10:
        t=t-10
        N+=t*(10**(3-i))
        next(i-1)
    else:
        N+=t*(10**(3-i))

while not check(N):
    next(3)
print(N)

### FIXED CODE ###

N,K=map(int,input().split())
Ds=list(input().split())
Di=list(map(int,Ds))
nex=[1]*10
for i in reversed(Di):
    nex[i-1]=nex[i]+1

def check(n):
    ns = str(N)
    for nss in ns:
        if nss in Ds:
            return False
    return True

def next(i):
    global N
    ns='{0:0>5}'.format(N)
    t=nex[int(ns[i])]
    pp=int(ns[i])+t
    if pp >=10:
        t=t-10
        N+=t*(10**(4-i))
        next(i-1)
    else:
        N+=t*(10**(4-i))

while not check(N):
    next(4)
print(N)
### BUGGY CODE ###

N = int(input())
numList = list(map(int, input().split()))
ans = 1
for i in range(N):
  ans *= numList[i]
  if ans == 0:
    break
print(ans) if ans <= 10**18 else print("-1")

### FIXED CODE ###

import collections

N = int(input())
cNum = collections.Counter(list(map(int, input().split())))
ans = 1
if cNum[0] != 0:
  print("0")
  exit()
for n in cNum.keys():
  ans *= n**cNum[n]
  if ans > 10**18:
    ans = -1
    break
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
for _ in range(Q):
    inp = input()
    if len(inp) == 1:
        S = S[::-1]
    else:
        T, F = map(int, inp.split()[:2])
        C = inp.split()[-1]
        if F == 1:
            S = C + S
        else:
            S = S + C

print(S)

### FIXED CODE ###

from collections import deque

S = deque([x for x in input()])
Q = int(input())
switch = 0
for _ in range(Q):
    inp = input()
    if len(inp) == 1:
        T = int(inp)
        if switch:
            switch = 0
        else:
            switch = 1
    else:
        T, F = map(int, inp.split()[:2])
        C = inp.split()[-1]
        if F == 1:
            if switch:
                S.append(C)
            else:
                S.appendleft(C)
        else:
            if switch:
                S.appendleft(C)
            else:
                S.append(C)
if switch:
    print("".join(list(S)[::-1]))
else:
    print("".join(S))
### BUGGY CODE ###

N = int(input())
n = 1
for i in range(1, N + 1):
    n *= i

a,b = divmod(n , 10**9 + 7)
print(b)   

### FIXED CODE ###

N = int(input())
n = 1
for i in range(1, N + 1):
    n *= i
    n %= (10**9 + 7)
print(n)
### BUGGY CODE ###

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

for i in range(m):
  max_index = a.index(max(a))
  a[max_index] = int(a[max_index] / 2)
    
print(sum(a))

### FIXED CODE ###

import heapq

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

def minus_int(x):
  return -1 * int(x)

a = list(map(minus_int, input().split()))
heapq.heapify(a)

for i in range(m):
  maxp = heapq.heappop(a)
  maxp = -int(-maxp // 2)
  heapq.heappush(a, maxp)
  
print(-sum(a))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
ri = lambda: int(input())
rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
#rl = lambda: list(input().split()))
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7


N,Q=rl()
STX = [rl() for _ in range(N)]
D = rr(Q)[0]

STX.sort(key=lambda x: (x[2],x[0],x[1]))
STX = [[s-x,t-x,x] for s,t,x in STX]
for d in D:
    flag = 0
    for s,t,x in STX:
        if d < s:
            continue
        elif d < t:
            print(x)
            flag = 1
            break
    if flag == 0:
        print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
ri = lambda: int(input())
rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
#rl = lambda: list(input().split()))
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7


N,Q=rl()
TT = []
now = set()
for _ in range(N):
    s,t,x = rl()
    TT.append((s-x-0.5,1,x))
    TT.append((t-x-0.5,-1,x))
for i in range(Q):
    d = ri()
    TT.append((d,0,i))


TT.sort()
mx = INF
mx_f = False
ans = [-1]*Q
for st,w,x in TT:
    if w > 0:
        now.add(x)
        if mx > x:
            mx = x
            mx_f = True
    elif w < 0:
        now.remove(x)
        if mx == x:
            mx_f = False
    elif len(now) > 0:
        if not mx_f:
            mx = min(now)
            mx_f = True
        ans[x] = mx
print(*ans,sep='\n')
### BUGGY CODE ###


N, H = map(int, input().split())
A, B = [], []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

attack = 0

FWA = max(A)
FW = A.index(max(A))
D = max(B)
FA = 0

while FWA < D:
    W = B.index(D)
    if FW == W:
        FA = D
        B[W] = 0
        D = max(B)
        continue
    H -= D
    attack += 1
    B[W] = 0
    D = max(B)

if FWA >= FA:
    attack += H // FWA
    if H % FWA > 0:
        attack += 1
else:
    H -= FA
    attack += H // FWA + 1
    if H % FWA > 0:
        attack += 1
    
print(attack)
 


### FIXED CODE ###

import sys
N, H = map(int, input().split())
A, B = [], []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

attack = 0

FWA = max(A)
B.append(0)
B.sort()

while True: 
    D = B.pop()
    if FWA >= D:
        break
    H -= D
    attack += 1
    if H <= 0:
        print(attack)
        sys.exit()

attack += H // FWA
if H % FWA > 0:
    attack += 1

print(attack)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
sum = 0
for i in range(1, len(a)):
	if a[i-1] > a[i]:
		while not a[i] == a[i-1]:
			a[i] += 1
			sum += 1
print(sum)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
sum = 0
for i in range(1, len(a)):
	if a[i-1] > a[i]:
		sum += a[i - 1] - a[i]
		a[i] = a[i - 1]
print(sum)
### BUGGY CODE ###

from collections import deque
h, w = map(int, input().split())
a = [[] for i in range(h)]
for i in range(h):
    a[i] = list(input())

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

que = deque()

white = h * w

# スタート地点をqueueに追加
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            que.append([i, j])
            white -= 1

count = 0
while 1:
    if white == 0:
        break
    count += 1
    loop = len(que)
    for i in range(loop):
        p = que.popleft()
        for j in range(4):
            ny = p[0] + dy[j]
            nx = p[1] + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and a[ny][nx] == ".":
                a[ny][nx] = "#"
                white -= 1
                que.append([ny, nx])


print(count)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
a = [[] for i in range(h)]
for i in range(h):
    a[i] = list(input())

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

que = deque()

white = h * w

# スタート地点をqueueに追加
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            que.append([i, j])
            white -= 1

count = 0
while 1:
    if white == 0:
        break
    count += 1
    loop = len(que)
    for i in range(loop):
        p = que.popleft()
        for j in range(4):
            ny = p[0] + dy[j]
            nx = p[1] + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and a[ny][nx] == ".":
                a[ny][nx] = "#"
                white -= 1
                que.append([ny, nx])


print(count)