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

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

################ DANGER ################
test = ""
#test = \
"""
5 3
10 30 40 50 20
ans 30
0 20 30 40 30
"""

"""
3 1
10 20 10
ans 20
"""

"""
2 100
10 10
ans 0
"""

"""
10 4
40 10 20 70 80 10 20 70 80 60
ans 40
0 30 20 30 40 30 20 30 40 40
"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################  

# B_Frog2
n, k = map(int, input2().split())
a = list(map(int, input2().split()))

k = min(n-1, k)

dp = [0] * n
for i in range(1, k+1):
    dp[i] = abs(a[i] - a[0])
    
for i in range(k+1, n):
    dp[i] = min(dp[j] + abs(a[i] - a[j]) for j in range(i-k, i))

print(dp[-1])



### FIXED CODE ###

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

import numpy as np

EDPC = "https://atcoder.jp/contests/dp/"
TDPC = "https://atcoder.jp/contests/tdpc/tasks"

################ DANGER ################
test = ""
#test = \
"""
5 3
10 30 40 50 20
ans 30
0 20 30 40 30
"""

"""
3 1
10 20 10
ans 20
"""

"""
2 100
10 10
ans 0
"""

"""
10 4
40 10 20 70 80 10 20 70 80 60
ans 40
0 30 20 30 40 30 20 30 40 40
"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################  

n, k = map(int, input2().split())
a = list(map(int, input2().split()))
k = min(n-1, k)

def main(n, k, a):
    aa = np.concatenate([a])
    dp = np.concatenate([np.abs(aa - aa[0])[:k+1], 
                                np.zeros(n-k-1, dtype="int")])
    for i in range(k+1, n):
        dp[i] = np.min(dp[i-k:i] + np.abs(aa[i-k:i] - aa[i]))
    
    return dp[-1]


if __name__ == "__main__":
    print(main(n, k, a))
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC134 D

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

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

b = []

for i in range(n//2,n):
    if a[i] == 1:
        b.append(i+1)

for i in range(1,n//2+1)[::-1]:
    s = 0
    if i == 1:
        if len(b) == 0 and a[0]:
            b.append(1)
        elif len(b) % 2 != a[0]:
            b.append(1)
        break
    for j in b:
        if j % i == 0:
            s += 1
    if s % 2:
        if a[i-1] == 1:
            continue
        b.append(i)
    elif s % 2 == 0 and a[i-1] == 1:
        b.append(i)

m = len(b)
if m == 0:
    print(0)
    quit()
else:
    b.sort()
    print(m)
    for i in range(m-1):
        print(b[i],end=' ')
    print(b[-1])


### FIXED CODE ###

#!/usr/bin/env python3
#ABC134 D

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

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

b = [0]*(n+1)

for i in range(n//2,n):
    if a[i] == 1:
        b[i+1] = 1

for i in range(1,n//2+1)[::-1]:
    s = 0
    if i == 1:
        if sum(b) == 0 and a[0]:
            b[1] = 1
        elif sum(b) % 2 != a[0]:
            b[1] = 1
        break
    for j in range(2,n):
        if i*j > n:
            break
        if b[i*j] == 1:
            s += 1
    if s % 2:
        if a[i-1] == 1:
            continue
        b[i] = 1
    elif s % 2 == 0 and a[i-1] == 1:
        b[i] = 1

m = sum(b)
if m == 0:
    print(0)
    quit()
else:
    print(m)
    ans = [i for i,v in enumerate(b) if v]
    print(*ans)
### BUGGY CODE ###

#coding: utf-8

N = int(input())

G = []
for i in range(N+1):
    G.append([-1]*(N+1))

for i in range(N-1):
    u, v, w = (int(n) for n in input().split())
    G[u][v] = w
    G[v][u] = w

ret = [-1] * (N+1)

def dfs(node, d):
    if ret[node] != -1:
        return

    if d % 2 == 0:
        ret[node] = 0
    else:
        ret[node] = 1 

    for i in range(N+1):
        if G[node][i] == -1:
            continue
        dfs(i, d + G[node][i])

dfs(1, 0)
for i in range(N):
    print(ret[i+1])



### FIXED CODE ###

#coding: utf-8
from collections import defaultdict, deque

N = int(input())
G = {}
for i in range(1, N+1):
    G[i] = []

for i in range(N-1):
    u, v, w = (int(n) for n in input().split())
    G[u].append((v, w))
    G[v].append((u, w))

ret = [-1] * (N+1)

que = deque()
que.append((1, 0))

while len(que) > 0:
    node, distance = que[0]
    que.popleft()

    ret[node] = distance % 2
    for next_node, next_distance in G[node]:
        if ret[next_node] == -1:
            que.append((next_node, distance + next_distance))

for i in range(N):
    print(ret[i+1])
### BUGGY CODE ###

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

dp = [True for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j: continue
        if A[i] % A[j] == 0:
            dp[i] = False
            break


ans = 0
for i,v in enumerate(dp):
    if v:
        ans += 1

print(ans)


### FIXED CODE ###

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

limit = max(A) + 1

dp = [True] * (limit + 1)
d = {}

for i in A:
    p = 2
    while i*p<=limit:
        dp[i*p] = False
        p += 1
    d.setdefault(i, 0)
    d[i] += 1

ans = []
for i in A:
    if dp[i] and d[i] == 1:
        ans.append(i)
print(len(ans))
### BUGGY CODE ###

n, m = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
for k in range(m):
  s, t = map(int,input().split())
  for i in range(n):
    if a[i] <= t:
      a[i:i] = [t]*s
      break
ans = 0
for v in range(n):
  ans += a[v]
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
b = [list(map(int,input().split())) for p in [0]*m]
b.sort(key=lambda q: -q[1])
#print(a)
#print(b)

c = 0
for s in b:
	for t in [0]*s[0]:
		#print(s)
		if c + 1 > n:
			break
		if s[1] <= a[c]:
			break
		a[c] = s[1]
		c += 1
		#print(a)
	else:
		continue
	break
print(sum(a))
### BUGGY CODE ###

n = int(input())
cnt = 0
while n != 0:
    cnt += n % 10
    cnt %= 9
    n //= 10
if cnt == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

n = str(input())
cnt = 0
for i in n:
    cnt += int(i)
    cnt %= 9
if cnt == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

S = input()[::-1]
N = len(S)
sum_of_mod = [0] * 2019
sum_of_mod[0] += 1
digit = 0
now = 0
for i in range(N):
    now = int(S[i])*(10**digit) + now
    sum_of_mod[now % 2019] += 1
    digit += 1

ans = 0
for i in range(2019):
    ans += sum_of_mod[i] * (sum_of_mod[i]-1) // 2
print(ans)


### FIXED CODE ###

S = input()[::-1]
N = len(S)
sum_of_mod = [0] * 2019
sum_of_mod[0] += 1
digit = 1
now = 0
for i in range(N):
    now = int(S[i])*digit + now
    now %= 2019
    digit *= 10
    digit %= 2019
    sum_of_mod[now] += 1

ans = 0
for i in range(2019):
    ans += sum_of_mod[i] * (sum_of_mod[i]-1) // 2
print(ans)
### BUGGY CODE ###


class BIT: # 1Indexed
    def __init__(self,size):
        self.array = [0]*size
        self.size  = size
    def add(self,ind,value):
        while ind <= self.size:
            self.array[ind-1] += value
            ind += ind & -ind
    def sum(self,x):
        out = 0
        while x > 0:
            out += self.array[x-1]
            x -= x & -x
        return out

################### ABC174F ###################

def main(N,Q,c,q):
    bit = BIT(N)
    rbi= {}
    ans = [0]*Q
    q.sort(key= lambda x:x[1])
    R = 0
    for l,r,ind in q:
        for i in range(R,r):
            if c[i] in rbi:
                bit.add(rbi[c[i]],-1)
            rbi[c[i]] = i+1
            bit.add(rbi[c[i]],1)
        ans[ind] = bit.sum(r)-bit.sum(l-1)
    return ans
                


if __name__ == "__main__":
    N,Q = map(int,input().split())
    c = list(map(int,input().split()))
    q = list( list(map(int,input().split()))+[i] for i in range(Q))
    ans = main(N,Q,c,q)
    for i in ans:
        print(i)

### FIXED CODE ###

class BIT: # 1Indexed
    def __init__(self,size):
        self.array = [0]*size
        self.size  = size
    def add(self,ind,value):
        while ind <= self.size:
            self.array[ind-1] += value
            ind += ind & -ind
    def sum(self,x):
        out = 0
        while x > 0:
            out += self.array[x-1]
            x -= x & -x
        return out

################### ABC174F ###################

import sys
input = sys.stdin.readline

def main(N,Q,c,q):
    bit = BIT(N)
    rbi= {}
    ans = [0]*Q
    q.sort(key= lambda x:x[1])
    R = 0
    for l,r,ind in q:
        for i in range(R,r):
            if c[i] in rbi:
                bit.add(rbi[c[i]],-1)
            rbi[c[i]] = i+1
            bit.add(rbi[c[i]],1)
        ans[ind] = bit.sum(r)-bit.sum(l-1)
        R = r
    return ans

if __name__ == "__main__":
    N,Q = map(int,input().split())
    c = list(map(int,input().split()))
    q = list( list(map(int,input().split()))+[i] for i in range(Q))
    ans = main(N,Q,c,q)
    for i in ans:
        print(i)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
for i in range(Q):
    B, C = list(map(int, input().split()))
    for j in range(len(A)):
        if A[j] == B:
            A[j] = C
    print(sum(A))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
count = [0 for i in range(110000)]
sum_ = sum(A)
for i in range(N):
  count[A[i]] += 1

Q=int(input())
for i in range(Q):
  b,c = map(int,input().split())
  count[c] += count[b]
  sum_ += (c-b)*count[b]
  count[b] = 0
  print(sum_)
### BUGGY CODE ###

import sys
#input = sys.stdin.buffer.readline

def main():
    N = int(input())
    S = input()
    Q = input()
    
    def count(k):
        d,m,dm,dmc = 0,0,0,0
        for i in range(N):
            st = S[i]
            if st == "D":
                d += 1
            elif st == "M":
                m += 1
                dm += d
            elif st == "C":
                dmc += dm
            if i >= k-1:
                if S[i-k+1] == "D":
                    dm -= m
                    d -= 1
                elif S[i-k+1] == "M":
                    m -= 1
        return dmc
        
    x = list(map(int,input().split()))
    for k in x:
        print(count(k))
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
#input = sys.stdin.buffer.readline

def main():
    N = int(input())
    S = input()
    Q = input()
    x = tuple(map(int,input().split()))
    for k in x:
        d,m,dm,dmc = 0,0,0,0
        for i in range(N):
            st = S[i]
            if st == "D":
                d += 1
            elif st == "M":
                m += 1
                dm += d
            elif st == "C":
                dmc += dm
            if i >= k-1:
                if S[i-k+1] == "D":
                    dm -= m
                    d -= 1
                elif S[i-k+1] == "M":
                    m -= 1
        print(dmc)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

def count_inversion(input_array):
    n = max(input_array)
    s = [0 for _ in range(n + 2)]

    def bit_add(i):
        x = i
        while x < n:
            s[x] += 1
            x += x & -x

    def bit_sum(i):
        #print(i, s)
        x = i
        ret = 0
        while x > 0:
            ret += s[x]
            x -= x & -x
        #print("ret", ret)
        return ret

    res = 0
    for i in range(len(input_array)):
        x = input_array[i]
        res += i - bit_sum(x)
        bit_add(x)
    return res

b = list(sorted(set(a)))

m = n * (n + 1) // 4 + 1

ans = len(b) // 2

l = 0
r = len(b) - 1
#print(b, m)
while 1:
    s = [n for _ in range(n)]
    s[0] = n
    for i in range(1,n):
        if a[i] >= b[ans]:
            s[i] = s[i - 1] + 1
        else:
            s[i] = s[i - 1] - 1
    base = min(s)
    for i in range(n):
        s[i] -= base - 1
    #print(s, count_inversion(s), l, r, ans)
    if count_inversion(s) > m:
        if ans == l:
            break
        elif ans == l + 1:
            ans = l
            break
        else:
            r = ans
            ans = l + (ans - l) // 2
    else:
        if ans == r:
            break
        else:
            l = ans
            ans = ans + (r - ans) // 2 + 1

print(b[ans])

### FIXED CODE ###

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

if n == 1:
    print(a[0])
    exit()

b = list(sorted(set(a)))

def count_inversion(ans):
    s = [0 for _ in range(2 * n + 2) ]

    def bit_add(i):
        x = i
        while x < 2 * n:
            s[x] += 1
            x += x & -x

    def bit_sum(i):
        x = i
        ret = 0
        while x > 0:
            ret += s[x]
            x -= x & -x
        return ret

    temp = [n for _ in range(n + 1)]
    temp[0] = n + 1
    for i in range(n):
        if a[i] >= b[ans]:
            temp[i + 1] = temp[i] + 1
        else:
            temp[i + 1] = temp[i] - 1
    res = 0
    for i in range(n + 1):
        x = temp[i]
        res += bit_sum(x)
        bit_add(x)
    return res

m = n * (n + 1) // 2

ans = 0

l = 0
r = len(b)
while 1:
    ans = (l + r) // 2
    if count_inversion(ans) * 2 >= m:
        l = ans
    else:
        r = ans
    if r - l <= 1:
        ans = l
        break

print(b[ans])
### BUGGY CODE ###

import sys
f=lambda:map(int,sys.stdin.readline().split())
h,n=f()
dp=[10**9]*(h+1)
dp[0]=0
for i in range(n):
  a,b=f()
  for j in range(h+1):
    dp[j]=min(dp[j],dp[max(j-a,0)]+b)
print(dp[h])

### FIXED CODE ###

import sys
f=lambda:map(int,sys.stdin.readline().split())
h,n=f()
INF=10**9
dp=[[INF]*(h+1) for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
  a,b=f()
  for j in range(h+1):
    dp[i+1][j]=min(dp[i][j],dp[i+1][max(j-a,0)]+b)
print(dp[n][h])
### BUGGY CODE ###

# from collections import deque

h,w=map(int, input().split())
c_h,c_w=map(int, input().split())
d_h,d_w=map(int, input().split())
map=[[-1]*w for i in range(h)]
 
for gyou in range(h):
    tmp=input()
    for retu in range(w):
        if tmp[retu]=="#":map[gyou][retu]=-2
 
# genzai=deque()
# wapu=deque()
genzai=[[c_h-1,c_w-1]]
wapu=[[c_h-1,c_w-1]]
 
map[c_h-1][c_w-1]=0
 
def idou(gyou,retu,kaisuu):
    wapu.append([gyou,retu])
    for i in (-1,1):
        if 0<=gyou+i and gyou+i<h:
            if map[gyou+i][retu]==-1:
                map[gyou+i][retu]=kaisuu
                genzai.append([gyou+i,retu])
                wapu.append([gyou+i,retu])
                
        if 0<=retu+i and retu+i<w:
            if map[gyou][retu+i]==-1:
                map[gyou][retu+i]=kaisuu
                genzai.append([gyou,retu+i])
                wapu.append([gyou,retu+i])

def idou_wapu(gyou,retu,kaisuu):
    for i in range(-2,3):
        for j in range(-2,3):
            if 0<=gyou+i and gyou+i<h and 0<=retu+j and retu+j<w:
                if map[gyou+i][retu+j]==-1:
                    map[gyou+i][retu+j]=kaisuu+1
                    genzai.append([gyou+i,retu+j])

wapu_kaisuu=0

while len(genzai)!=0:
 
    while len(genzai)>0:
        idou(genzai[0][0],genzai[0][1],wapu_kaisuu)
        genzai.pop(0)
    
    while len(wapu)>0:
        idou_wapu(wapu[0][0],wapu[0][1],wapu_kaisuu)
        wapu.pop(0)
    
    wapu_kaisuu+=1

    if map[d_h-1][d_w-1]!=-1:
        print(map[d_h-1][d_w-1])
        exit()


print(map[d_h-1][d_w-1])

### FIXED CODE ###

from collections import deque

h,w=map(int, input().split())
c_h,c_w=map(int, input().split())
d_h,d_w=map(int, input().split())
map=[[-1]*w for i in range(h)]
 
for gyou in range(h):
    tmp=input()
    for retu in range(w):
        if tmp[retu]=="#":map[gyou][retu]=-2
 
genzai=deque()
wapu=deque()
genzai.append((c_h-1,c_w-1))
wapu.append((c_h-1,c_w-1))
 
map[c_h-1][c_w-1]=0
 
def idou(gyou,retu,kaisuu):
    wapu.append((gyou,retu))
    for i in (-1,1):
        if 0<=gyou+i and gyou+i<h:
            if map[gyou+i][retu]==-1:
                map[gyou+i][retu]=kaisuu
                genzai.append((gyou+i,retu))
                wapu.append((gyou+i,retu))
                
        if 0<=retu+i and retu+i<w:
            if map[gyou][retu+i]==-1:
                map[gyou][retu+i]=kaisuu
                genzai.append((gyou,retu+i))
                wapu.append((gyou,retu+i))

def idou_wapu(gyou,retu,kaisuu):
    for i in range(-2,3):
        for j in range(-2,3):
            if 0<=gyou+i and gyou+i<h and 0<=retu+j and retu+j<w:
                if map[gyou+i][retu+j]==-1:
                    map[gyou+i][retu+j]=kaisuu+1
                    genzai.append((gyou+i,retu+j))

wapu_kaisuu=0

while len(genzai)!=0:
 
    while len(genzai)>0:
        idou(genzai[0][0],genzai[0][1],wapu_kaisuu)
        genzai.popleft()
    
    while len(wapu)>0:
        idou_wapu(wapu[0][0],wapu[0][1],wapu_kaisuu)
        wapu.popleft()
    
    wapu_kaisuu+=1

    if map[d_h-1][d_w-1]!=-1:
        print(map[d_h-1][d_w-1])
        exit()


print(map[d_h-1][d_w-1])
### BUGGY CODE ###

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

print(counter)


### FIXED CODE ###

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

print(counter)
### BUGGY CODE ###

N = int(input())
arr = list(input())
a = 0
b = 0
c = 0
count = 0
for i in range(N - 2):
  for j in range(i + 1, N - 1):
    for k in range(j + 1, N):
      if k - j != j - i:
        a = k
        b = j 
        c = i
        count += 1
        
        if arr[a] == arr[b] or arr[c] == arr[b] or arr[a] == arr[c]:
          count -= 1
print(count)

### FIXED CODE ###

N = int(input())
arr = list(input())
a = arr.count("R")
b = arr.count("G")
c = arr.count("B")
count = a * b * c

for i in range(N - 2):
  for j in range(i + 1, N - 1):
    k = i + (j - i) * 2
    if k < N and arr[i] != arr[j] and arr[j] != arr[k] and arr[k] != arr[i]:
      count -= 1
print(count)
### BUGGY CODE ###

n = int(input())
s = [[int(c) for c in input().strip()] for _ in range(n)]

def bfs(s, start):
    visited = [(start, 0)]
    plan = [(i, 1) for i, c in enumerate(s[start]) if c == 1]
    while len(plan) > 0:
        vertex, length = plan.pop(0)
        vf = False
        for v, l in visited:
            if v == vertex:
                if (l - length) % 2 != 0:
                    return -2
                else:
                    vf = True
                    break
        if not vf:
            visited.append((vertex, length))
            plan.extend([(i, length + 1) for i, c in enumerate(s[vertex]) if c == 1])
    return visited[-1][1]

print(max([bfs(s, start) for start in range(n)]) + 1)

### FIXED CODE ###

from collections import deque

n = int(input())
s = [[int(c) for c in input().strip()] for _ in range(n)]

def bfs(s, start):
    plan = deque([(start, 0)])
    lengths = {}
    while len(plan) > 0:
        vertex, length = plan.popleft()
        if vertex in lengths:
            if (lengths[vertex] - length) % 2 != 0:
                return -1
        else:
            lengths[vertex] = length
            plan.extend([(i, length + 1) for i, c in enumerate(s[vertex]) if c == 1 and i not in lengths])
    return max(lengths.values())

bfs_result = 0
for start in range(n):
    res = bfs(s, start)
    if res < 0:
        bfs_result = -2
        break
    elif res > bfs_result:
        bfs_result = res
print(bfs_result + 1)
### BUGGY CODE ###

N = int(input())
A = [int(n) for n in input().split()]
for i in range(1, N+1):
    print(A.count(i))


### FIXED CODE ###

from sys import stdin
N = int(input())
A = [0]*2 + [int(n) for n in stdin.readline().split()]
ans = [0]+[0]*N
for i in range(2, N+1):
    ans[A[i]] += 1
for i in range(1, N+1):
    print(ans[i])
### BUGGY CODE ###

monster, hisatu = map(int, input().split())
m_life = list(map(int, input().split()))
count = 0
if hisatu >= len(m_life):
    print(0)
else:
    while hisatu > 0:
        m_life.remove(max(m_life))
        hisatu -= 1
    for i in m_life:
        count += i
    print(count)


### FIXED CODE ###

monster, hisatu = map(int, input().split())
m_life = list(map(int, input().split()))
m_life.sort()
count = 0
for i in range(len(m_life)-hisatu):
    count += m_life[i]
print(count)
### BUGGY CODE ###

L, R = (int(i) for i in input().split())  
unko = []
flag = True
if flag:
  for i in range(L,R+1):
    for j in range(i+1,R+1):
      n = (i*j) % 2019
      unko.append((i*j) % 2019)
      if n == 0:
        flag = False
print(min(unko))


### FIXED CODE ###

l,r = (int(i) for i in input().split())
a = []
for i in range(l,min(r,l+2019)):
  for j in range(i+1,min(r,l+2019)+1):
    a.append(i*j%2019)
print(min(a))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
N, Q = map(int, input().split())
evs = [None] * 2*N
for i in range(N):
    s, t, x = map(int, input().split())
    evs[2*i] = [s-x, 1, x]
    evs[2*i+1] = [t-x, -1, x]
evs.sort()
s = set()
INF = 10**20
s.add(INF)
i, NN = 0, 2*N
for q in range(Q):
    d = int(input())
    while i < NN and evs[i][0] <= d:
        r, f, x = evs[i]
        if f == 1:
            s.add(x)
        else:
            s.remove(x)
        i += 1
    ans = min(s)
    if ans == INF:
        print(-1)
    else:
        print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
INF = float('inf')

class SegmentTree:

    def __init__(self, N):
        self.N = 1<<(N-1).bit_length()
        self.data = [None] * (2*self.N)

    def Update(self, l, r, t, v):
        L, R, val = l+self.N, r+self.N, (t, v)
        while L < R:
            if R & 1:
                R -= 1
                self.data[R-1] = val
            if L & 1:
                self.data[L-1] = val
                L += 1
            L >>= 1
            R >>= 1

    def getValue(self, x):
        x += self.N-1
        ret = (-1, INF)
        while x >= 0:
            if self.data[x]:
                ret = max(ret, self.data[x])
            x = (x-1)//2
        return ret[1]

N, Q = map(int, input().split())
stx = [[int(x) for x in input().split()] for i in range(N)]
stx.sort(key = lambda v : -v[2])
D = [(int(input()), i) for i in range(Q)]
D.sort(key = lambda v : v[0])
d, p = [d for d, p in D], [p for d, p in D]
seg = SegmentTree(Q)
for i, (s, t, x) in enumerate(stx):
    l = bisect_left(d, s-x)
    r = bisect_left(d, t-x)
    seg.Update(l, r, i, x)
ans = [None] * Q
for i in range(Q):
    tmp = seg.getValue(i)
    if tmp == INF:
        tmp = -1
    ans[p[i]] = tmp
print(*ans, sep = '\n')