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

import sys
import copy
from collections import deque

sys.setrecursionlimit(10000000)

n = int(sys.stdin.readline().rstrip())
a = [deque(map(int, sys.stdin.readline().split())) for _ in range(n)]

def deepPop(x):
    global a
    global days
    target = a[x][0] -1
    if a[target][0] -1 == x:
        a[target].popleft()
        a[x].popleft()
        maxd = max(days[x] +1, days[target] +1)
        days[x] = maxd
        days[target] = maxd
        if len(a[x]) > 0:
            deepPop(x)
        if len(a[target]) > 0:
            deepPop(target)


day = 0
days = [0] * n
setn = set(range(n))
while True:
    popped = 0
    zeros = 0
    tmpns = copy.copy(setn)
    for i in setn:
        if len(a[i]) == 0:
            tmpns.remove(i)
            continue
        num = a[i][0] - 1
        if num < i:
            continue
        if a[num][0] - 1 == i:
            deepPop(i)
            popped += 1
    if popped == 0:
        if len(tmpns) == 0:
            break
        else:
            day = -1
            break
    setn = tmpns

if day == -1:
    print(day)
else:
    print(max(days))


### FIXED CODE ###

import sys
from collections import deque

n = int(input())
a = [deque(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]

current = []

for i in range(n):
    target = a[i][0] -1
    if a[target][0] -1 == i and i < target:
        current.append([i, target])

day = 0
zc = 0
while True:
    popped = 0
    plist = set()
    zeros = 0
    tc = []
    for i in current:
        a[i[0]].popleft()
        a[i[1]].popleft()
        if len(a[i[0]]) > 0:
            plist.add(i[0])
        else:
            zc += 1
        if len(a[i[1]]) > 0:
            plist.add(i[1])
        else:
            zc += 1
    for i in plist:
        target = a[i][0] -1
        if a[target][0] -1 == i:
            if not target in plist or i < target:
                tc.append([i, target])
    day += 1
    if len(tc) == 0:
        break
    current = tc

if zc != n:
    day = -1

print(day)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

for i in range(M):
  A[A.index(max(A))] = A[A.index(max(A))]//2

print(sum(A))

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = [-i for i in map(int, input().split())]
heapq.heapify(A)
for i in range(M):
  tmp = -((-heapq.heappop(A))//2)
  heapq.heappush(A, tmp)

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

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

    mod = 10**9 + 7
    answer = 0

    for i in range(n):
        for j in range(i+1, n):
            answer += a[i] * a[j]
            if answer >= mod:
                answer %= mod
    print(answer)


if __name__ == "__main__":
    main()


### FIXED CODE ###

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

    mod = 10**9 + 7
    answer = 0
    sum_a = sum(a) % mod

    for i in range(n):
        sum_a = sum_a - a[i]
        answer += a[i] * sum_a
        answer %= mod

    print(answer)


'''
    for i in range(n):
        sum_sub = 0
        for j in range(i+1, n):
            sum_sub += a[j]
            if sum_sub >= mod:
                sum_sub %= mod
        answer += a[i] * sum_sub
        if answer >= mod:
            answer %= mod
    print(answer)
'''

'''
    for i in range(n):
        for j in range(i+1, n):
            answer += a[i] * a[j]
            if answer >= mod:
                answer %= mod
    print(answer)
'''

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

INF = 99999999999

N, K = map(int, input().split())
hN = list(map(int, input().split()))

dp = [INF for _ in range(N)]

dp[0] = 0

for i in range(N):
    for k in range(1, K + 1):
        if i + k < N:
            diff = dp[i] + abs(hN[i] - hN[i + k])
            dp[i + k] = min(dp[i + k], diff)
        else:
            break
    # print("i={}, dp={}".format(i, dp))

print(dp[N - 1])


### FIXED CODE ###

INF = 99999999999

N, K = map(int, input().split())
hN = list(map(int, input().split()))

dp = [INF for _ in range(N)]

dp[0] = 0

for i in range(N):
    for k in range(1, K + 1):
        if i + k < N:
            diff = dp[i] + abs(hN[i] - hN[i + k])
            dp[i + k] = min(dp[i + k], diff)
        else:
            break
    # print("i={}, dp={}".format(i, dp))

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

n = int(input())
s = list(input())
ans = n
for i in range(n):
    ans = min(ans, s[i+1:].count('E') + s[:i].count('W'))
print(ans)

### FIXED CODE ###

n = int(input())
s = list(input())
total = s[1:].count('E')
ans = s[1:].count('E')
for i in range(n-1):
    if s[i]=='W':
        total += 1
    if s[i+1]=='E':
        total -= 1
    ans = min(ans, total)
print(ans)
### BUGGY CODE ###

from functools import lru_cache

import sys
sys.setrecursionlimit(1000000)

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

A = [int(input()) for _ in range(M)]

@lru_cache(1000000)
def dfs(pos):
    if pos > N:
        return 0
    if pos == N:
        return 1
    if pos in A:
        return 0
    return dfs(pos + 2) + dfs(pos + 1)

print(dfs(0) % 1000000007)


### FIXED CODE ###

from functools import lru_cache

import sys
sys.setrecursionlimit(1000000)

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

A = set(int(input()) for _ in range(M))

@lru_cache(None)
def dfs(pos):
    if pos > N:
        return 0
    if pos == N:
        return 1
    if pos in A:
        return 0
    return dfs(pos + 2) + dfs(pos + 1)

for i in reversed(range(N+1)):
    dfs(i)

print(dfs(0) % 1000000007)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N = int(input())
S = input().strip()
Q = int(input())
n = 1
while n < N:
    n *= 2
T = [set()] * (2 * n)

def update(k, a):
    k += n-1
    T[k] = {a}
    while k > 0:
        k = (k - 1) // 2
        T[k] = T[k*2+1] | T[k*2+2]

def query(a, b, k, l, r):
    # print(a, b, k, l, r)
    if r <= a or b <= l:
        # print('  ', set())
        return set()
    if a <= l and r <= b:
        # print('  ', T[k])
        return T[k]
    else:
        vl = query(a, b, k*2+1, l, (l+r)//2)
        vr = query(a, b, k*2+2, (l+r)//2, r)
        return vl | vr

for i in range(N):
    update(i, S[i])

for q in range(Q):
    f, i, c = [x for x in input().strip().split()]
    if f == '1':
        # print(T,T[int(i)-1])
        update(int(i)-1, c)
    elif f == '2':
        # print(int(i)-1, int(c)-1)
        print(len(query(int(i)-1, int(c), 0, 0, n)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N = int(input())
S = input().strip()
Q = int(input())
n = 1
while n < N:
    n *= 2
T = [0] * (2 * n)

def update(k, a):
    k += n-1
    T[k] = 1 << ord(a) - 97
    while k > 0:
        k = (k - 1) // 2
        T[k] = T[k*2+1] | T[k*2+2]

def query(a, b, k, l, r):
    # print(a, b, k, l, r)
    if r <= a or b <= l:
        # print('  ', set())
        return 0
    if a <= l and r <= b:
        # print('  ', T[k])
        return T[k]
    else:
        vl = query(a, b, k*2+1, l, (l+r)//2)
        vr = query(a, b, k*2+2, (l+r)//2, r)
        return vl | vr

for i in range(N):
    update(i, S[i])

for q in range(Q):
    f, i, c = [x for x in input().strip().split()]
    if f == '1':
        # print(T,T[int(i)-1])
        update(int(i)-1, c)
    elif f == '2':
        # print(int(i)-1, int(c)-1)
        tmp = query(int(i)-1, int(c), 0, 0, n)
        ans = 0
        for i in range(26):
            ans += tmp >> i & 1
         
        print(ans)
### BUGGY CODE ###

import itertools
import sys
input = sys.stdin.readline

n, m, r = [ int(v) for v in input().split() ]
town_list = [ int(v)-1 for v in input().split() ]

road_matrix = [ [ 10**9 for j in range(n) ] for i in range(n) ]


for i in range(m):
	s, e, d = [ int(v) - 1 for v in input().split() ]
	road_matrix[s][e] = d + 1
	road_matrix[e][s] = d + 1


min_dist_matrix = []
for h in range(n):
	min_dist = road_matrix[h]
	searched_point = []
	sarching_point = []
	j = h
	while len(searched_point) < n:
		searched_point.append(j)
		for i in range(n):
			if road_matrix[j][i] != 10**9 and i != h:
				sarching_point.append((road_matrix[j][i],i))
				min_dist[i] = min(min_dist[i],min_dist[j] + road_matrix[j][i])
		sarching_point.sort()

		for k in range(len(sarching_point)):
			if sarching_point[k][1] not in searched_point:
				j = sarching_point[k][1]
				sarching_point = sarching_point[k+1:]
				break
	min_dist_matrix.append(min_dist)


mindist = 10**9
for i in itertools.permutations(town_list,r):
	dist = 0
	for j in range(r-1):
		dist += min_dist_matrix[i[j]][i[j+1]]

	mindist = min(mindist,dist)
print(mindist)

### FIXED CODE ###

import itertools
import sys
input = sys.stdin.readline

n, m, r = [ int(v) for v in input().split() ]
town_list = [ int(v)-1 for v in input().split() ]

road_matrix = [ [ 10**9 for j in range(n) ] for i in range(n) ]


for i in range(m):
	s, e, d = [ int(v) - 1 for v in input().split() ]
	road_matrix[s][e] = d + 1
	road_matrix[e][s] = d + 1


for k in range(n):
	 for i in range(n):
		 for j in range(n):
			 road_matrix[i][j]  = min(road_matrix[i][k] + road_matrix[k][j], road_matrix[i][j])


mindist = 10**9
for i in itertools.permutations(town_list,r):
	dist = 0
	for j in range(r-1):
		dist += road_matrix[i[j]][i[j+1]]

	mindist = min(mindist,dist)
print(mindist)
### BUGGY CODE ###

apples = [(0, 'X') for x in range(300001)]
apples_idx = 0

def append_a(n):
    global apples
    global apples_idx
    apples[apples_idx] = (n, 'A')
    apples_idx += 1

def append_b(n):
    global apples
    global apples_idx
    apples[apples_idx] = (n, 'B')
    apples_idx += 1

def append_c(n):
    global apples
    global apples_idx
    apples[apples_idx] = (n, 'C')
    apples_idx += 1
    
X, Y, A, B, C = map(int, input().split())
for i in input().split():
    append_a(int(i))

for i in input().split():
    append_b(int(i))

for i in input().split():
    append_c(int(i))

apples.sort(reverse=True)
xn, yn = 0, 0
value = 0

for i, apple in enumerate(apples):
    if xn == X and yn == Y:
        break
    if apple[1] == 'A':
        if xn == X:
            continue
        xn += 1
        value += apple[0]
        continue
    if apple[1] == 'B':
        if yn == Y:
            continue
        yn += 1
        value += apple[0]
        continue

    # Apple C
    next_type = 'C'
    if xn < X and yn < Y:
        for j in range(i+1, len(apples)):
            if apples[j][1] == 'A':
                next_type = 'A'
            elif apples[j][1] == 'B':
                next_type = 'B'
    elif xn < X:
        next_type = 'A'
    else:
        next_type = 'B'

    if next_type == 'A':
        xn += 1
        value += apple[0]
    else:
        yn += 1
        value += apple[0]

print(value)



### FIXED 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.sort(reverse=True)
q.sort(reverse=True)

apples = p[:X] + q[:Y] + r
apples.sort(reverse=True)

value = sum(apples[:X+Y])
print(value)
### BUGGY CODE ###

import sys,time
sys.setrecursionlimit(10**7)

start_time = time.time()
N,M = map(int,input().split())
S = input()
src = [list(map(lambda x:int(x)-1,input().split())) for i in range(M)]

outdeg = [set() for i in range(2*N)]
for x,y in src:
    if S[x] == S[y]:
        #A0->A1, B0->B1
        outdeg[x].add(y+N)
        outdeg[y].add(x+N)
    else:
        #A1->B0, B1->A0
        outdeg[x+N].add(y)
        outdeg[y+N].add(x)

mem = [0] * (2*N)
def visit(v):
    if time.time() - start_time > 1.7:
        return # gori~~~
    if mem[v] == 1:
        print('Yes')
        exit()
    if mem[v] == 0:
        mem[v] = 1
        for to in outdeg[v]:
            visit(to)
        mem[v] = 2

for i in range(2*N):
    visit(i)

print('No')

### FIXED CODE ###

import sys,time
sys.setrecursionlimit(10**7)

start_time = time.time()
N,M = map(int,input().split())
S = input()
src = [tuple(map(lambda x:int(x)-1,sys.stdin.readline().split())) for i in range(M)]

outdeg = [set() for i in range(2*N)]
for x,y in src:
    if S[x] == S[y]:
        #A0->A1, B0->B1
        outdeg[x].add(y+N)
        outdeg[y].add(x+N)
    else:
        #A1->B0, B1->A0
        outdeg[x+N].add(y)
        outdeg[y+N].add(x)

mem = [0] * (2*N)
def visit(v):
    if time.time() - start_time > 1.8:
        # gori~~~
        print('No')
        exit()
    if mem[v] == 1:
        print('Yes')
        exit()
    if mem[v] == 0:
        mem[v] = 1
        for to in outdeg[v]:
            visit(to)
        mem[v] = 2

for i in range(2*N):
    visit(i)

print('No')
### BUGGY CODE ###

import math

X = int(input())

for i in range(-int(X**0.2),int(1e7)):
    tmp = (X+i**5)**0.2
    if tmp%1 == 0:
        print(int(tmp),i)
        exit()
    

### FIXED CODE ###

X = int(input())

for i in range(-1000,1000):
    for j in range(-1000,1000):
        if i**5 - j**5 == X:
            print(i,j)
            exit()
### BUGGY CODE ###

import os
import sys
from collections import defaultdict
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 = int(sys.stdin.readline())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

graph = defaultdict(list)
for i in range(N):
    for j in range(N - 2):
        a, b = i + 1, A[i][j]
        c, d = i + 1, A[i][j + 1]

        if a > b:
            a, b = b, a
        if c > d:
            c, d = d, c

        graph[(a, b)].append((c, d))

dist = defaultdict(int)


@lru_cache(maxsize=None)
def dfs(a, b):
    if (a, b) in hist:
        raise
    hist.add((a, b))
    ret = 1
    for c, d in graph[(a, b)]:
        ret = max(ret, dfs(c, d) + 1)
    return ret


hist = set()
try:
    ans = 0
    for a, b in list(graph.keys()):
        ans = max(dfs(a, b), ans)
        hist = set()
    print(ans)
except:
    print(-1)


### FIXED CODE ###

import os
import sys
from collections import defaultdict, deque
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 = int(sys.stdin.readline())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

graph = [[] for _ in range(N ** 2)]
ins = [0] * (N ** 2)
for i in range(N):
    for j in range(N - 2):
        a, b = i, A[i][j] - 1
        c, d = i, A[i][j + 1] - 1

        if a > b:
            a, b = b, a
        if c > d:
            c, d = d, c

        graph[a * N + b].append(c * N + d)
        ins[c * N + d] += 1

zeros = []
seen = []
for v, cnt in enumerate(ins):
    if cnt == 0:
        zeros.append(v)
        seen.append(v)

ans = 0
while zeros:
    nz = []
    for v in zeros:
        for u in graph[v]:
            ins[u] -= 1
            if ins[u] == 0:
                nz.append(u)
                seen.append(u)
    zeros = nz
    ans += 1
if len(seen) == len(graph):
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

import copy

S = input()
nN = len(S)
nAns = [ 1 for i in range(nN)]
nAnsC = [ 0 for i in range(nN)]

for j in range(10**2):
  nAnsT = [ 0 for i in range(nN)]
  for i in range(nN):
    sTmp = S[i]
    
    if nAns[i]==0:
      continue
    nNum = nAns[i]
    nAns[i] = 0
    if sTmp =='R':
      nTmp = i + 1
    elif sTmp =='L':
      nTmp = i - 1
    nAnsT[nTmp] += nNum
  
  nAns = copy.deepcopy(nAnsT)
  if i==1:
    nAnsC = copy.deepcopy(nAnsT)
  else:
    nTmp2 = i
    nTmp2 &= 1
    if nTmp2 == 1:
      if nAns == nAnsC:
        break
      else:
        nAnsC = copy.deepcopy(nAns)
      
#    print(*nAns)
#  sTmp = S[nTmp]
#  if sTmp =='R':
#    nTmp += 1
#  elif sTmp =='L':
#    nTmp -= 1
  
#  nAns[nTmp] += 1
  
print(*nAns)



### FIXED CODE ###

import sys
import copy

S = input()
nN = len(S)
nAns = [ 0 for i in range(nN)]
nAnsT = [ 0 for i in range(nN)]
nAnsR = [ 0 for i in range(nN)]

nCnt = S.count('RL')
nRLp = [ 0 for i in range(nCnt)]

nTmpP = 0
for i in range(nCnt):
  nTmp = S.find('RL',nTmpP)
  nRLp[i] = nTmp
  nTmpP = nTmp + 1

nCntE = S.count('LR')
nLRp = [ 0 for i in range(nCntE)]
nTmpP = 0
for i in range(nCntE):
  nTmp = S.find('LR',nTmpP)
  nLRp[i] = nTmp
  nTmpP = nTmp + 1
  
# print(nRLp)
# print(nLRp)

nTmpS = 0
for i in range(nCnt):
  nTmpR = nRLp[i]
  nTmpL = nTmpR + 1
  
  if i == nCnt - 1:
    nTmpE = nN - 1
  else:
    nTmpE = nLRp[i]
    
  nSize = nTmpE-nTmpS+1
  nB1 = nSize // 2
  nB2 = nSize // 2
  nChk = nSize % 2
  if nChk == 1:
    nB1 += 1
  
  nChk = nTmpR - nTmpS
  nChk %= 2
  if nChk == 0:
    nAns[nTmpR]=nB1
    nAns[nTmpL]=nB2
  else:
    nAns[nTmpR]=nB2
    nAns[nTmpL]=nB1
  
  nTmpS = nTmpE + 1

print(*nAns)
### BUGGY CODE ###


import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
##############################

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

if N == 1:
    A[0] //= (2**M)
    print(A[0])
    exit()

A.sort(reverse=True)
count = 0

A[0] //= 2
M -= 1
while M > 0:
    max_i = 0
    max_p = A[0]

    for i in range(1, N):
        if max_p < A[i]:
            max_p = A[i]
            max_i = i

        if A[i-1] < A[i]:
            break

    A[max_i] //= 2
    M -= 1

print(sum(A))


### FIXED CODE ###


import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

import heapq

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

if N == 1:
    A[0] //= (2**M)
    print(A[0])
    exit()

hq = []
for a in A:
    heapq.heappush(hq, -a)

while M > 0:
    high = -1 * heapq.heappop(hq)
    high //= 2
    M -= 1
    heapq.heappush(hq, -high)

ans = 0
for i in range(N):
    ans += heapq.heappop(hq)

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

n = int(input())
*a, = map(int, input().split())
for i in range(n):
    print(a.count(i+1))

### FIXED CODE ###

n = int(input())
*a, = map(int, input().split())
d = {}
for i in range(1, -~n): d[i] = 0
for i in a:
    if i not in d: d[i] = 1
    else: d[i] += 1
for i in d.values():
    print(i)
### BUGGY CODE ###

# abc177_c.py
# https://atcoder.jp/contests/abc177_c


# [開発時用] ログ関数
def lg(value):
    flag = False
    # flag = True
    if flag:
        print(str(value))


# [開発時用] exit処理
def xt(log):
    lg('★exit() - ' + str(log))
    exit()


# 本体
def get_results():

    # 引数処理部
    lines = list()
    # 仕様でn行と決まっている場合(の例)
    lines_count = 2
    # 先頭行のNで行数が決まる場合(の例)
    # line = input()
    # lines.append(line)
    # N = int(line)
    # lines_count = N
    for _ in range(lines_count):
        lines.append(input())

    # 演算部
    # S = lines[0]
    N = int(lines[0])
    # N, M = list(map(int, lines[0].split()))
    values = list(map(int, lines[1].split()))
    # values = list(map(int, lines[2].split()))
    # values = list()
    # for i in range(N):
    #     values.append(int(lines[i]))
    # valueses = list()
    # for i in range(N):
    #     valueses.append(list(map(int, lines[i+1].split())))

    lg(f'values=[{values}]')

    su = 0
    for i in range(N-1):
        for j in range(i+1, N):
            lg(i * 100 + j)
            su = (su + values[i] * values[j]) % (10**9+7)

    return [su]


# 主処理
def main():
    results = get_results()

    for result in results:
        print(result)


# 起動処理
if __name__ == '__main__':
    main()


### FIXED CODE ###

# abc177_c.py
# https://atcoder.jp/contests/abc177_c


# [開発時用] ログ関数
def lg(value):
    flag = False
    # flag = True
    if flag:
        print(str(value))


# [開発時用] exit処理
def xt(log):
    lg('★exit() - ' + str(log))
    exit()


# 本体
def get_results():

    # 引数処理部
    lines = list()
    # 仕様でn行と決まっている場合(の例)
    lines_count = 2
    # 先頭行のNで行数が決まる場合(の例)
    # line = input()
    # lines.append(line)
    # N = int(line)
    # lines_count = N
    for _ in range(lines_count):
        lines.append(input())

    # 演算部
    # S = lines[0]
    N = int(lines[0])
    # N, M = list(map(int, lines[0].split()))
    values = list(map(int, lines[1].split()))
    # values = list(map(int, lines[2].split()))
    # values = list()
    # for i in range(N):
    #     values.append(int(lines[i]))
    # valueses = list()
    # for i in range(N):
    #     valueses.append(list(map(int, lines[i+1].split())))

    lg(f'values=[{values}]')

    targets = list()
    # [1, 2, 3] => targets = [3, 5]
    su = 0
    for j in range(1, N):
        # targets.append(3)
        # targets.append(5)
        su += values[N - j]
        targets.append(su)

    su = 0
    for i in range(N-1):
        # for j in range(i+1, N):
        #     target += values[j]
        su = (su + values[i] * targets[N-2-i]) % (10**9+7)

    return [su]


# 主処理
def main():
    results = get_results()

    for result in results:
        print(result)


# 起動処理
if __name__ == '__main__':
    main()
### BUGGY CODE ###

k, s = map(int, input().split())
c = 0
for i_x in range(k+1):
    for i_y in range(k+1):
        for i_z in range(k+1):
            if i_x + i_y + i_z == s:
                c += 1
print(c)

### FIXED CODE ###

k, s = map(int, input().split())
c = 0
for i_x in range(k+1):
    for i_y in range(k+1):
        z = s - (i_x + i_y)
        if z >= 0 and z <= k:
            c += 1
print(c)
### BUGGY CODE ###

n,q = map(int, input().split())
# stx = [tuple(map(int, input().split())) for _ in range(n)]
stx = [0]*n
for i in range(n):
    stx[i] = tuple(map(int, input().split()))
# d = [int(input()) for _ in range(q)]
d = [0]*q
for i in range(q):
    d[i] = int(input())

#これはセグ木 * bisect
import bisect
inf = 10**9 + 100

# 定数倍高速化
b_left = bisect.bisect_left
b_right = bisect.bisect_right

def init(n,init_num=0):
    num = len(str(bin(n-1))) + 1
    seg = [init_num] * (2**num)
    # seg[0] = 2**(num-1)
    seg0 = 2**(num-1)
    return(seg,seg0)

def update(head, tail, x):
    # print('{} {} {}'.format(head, tail, x))
    head += seg0
    tail += seg0
    points = []
    while(head <= tail):
        if(head == tail):
            points.append(head)
            break

        if(head % 2 ==1):
            points.append(head)
            head += 1
        head = head//2

        if(tail % 2 == 0):
            points.append(tail)
            tail -= 1
        tail = (tail-1)//2

    for point in points:
        seg[point] = min(seg[point], x)

def execute_all():
    for i in range(2,len(seg)):
        seg[i] = min(seg[i], seg[i//2])


seg,seg0 = init(q, init_num = inf)

for i in range(n):
    left = b_left(d, stx[i][0] -stx[i][2])
    right = b_right(d, stx[i][1] - stx[i][2] -1) -1
    update(left, right, stx[i][2])
    # print('{} {} {}'.format(left, right, stx[i][2]))

execute_all()

for i in seg[seg0: seg0 + q]:
    if(i == inf):
        print(-1)
    else:
        print(i)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n,q = map(int, input().split())
# stx = [tuple(map(int, input().split())) for _ in range(n)]
stx = [0]*n
for i in range(n):
    stx[i] = tuple(map(int, input().split()))
# d = [int(input()) for _ in range(q)]
d = [0]*q
for i in range(q):
    d[i] = int(input())

#これはセグ木 * bisect
import bisect
inf = 10**9 + 100

# 定数倍高速化
b_left = bisect.bisect_left
b_right = bisect.bisect_right

def init(n,init_num=0):
    num = len(str(bin(n-1))) + 1
    seg = [init_num] * (2**num)
    # seg[0] = 2**(num-1)
    seg0 = 2**(num-1)
    return(seg,seg0)

def update(head, tail, x):
    # print('{} {} {}'.format(head, tail, x))
    head += seg0
    tail += seg0
    points = []
    while(head <= tail):
        if(head == tail):
            points.append(head)
            break

        if(head % 2 ==1):
            points.append(head)
            head += 1
        head = head//2

        if(tail % 2 == 0):
            points.append(tail)
            tail -= 1
        tail = (tail-1)//2

    for point in points:
        seg[point] = min(seg[point], x)

def execute_all():
    for i in range(2,len(seg)):
        seg[i] = min(seg[i], seg[i//2])


seg,seg0 = init(q, init_num = inf)

for i in range(n):
    left = b_left(d, stx[i][0] -stx[i][2])
    right = b_right(d, stx[i][1] - stx[i][2] -1) -1
    update(left, right, stx[i][2])
    # print('{} {} {}'.format(left, right, stx[i][2]))

execute_all()

for i in seg[seg0: seg0 + q]:
    if(i == inf):
        print(-1)
    else:
        print(i)