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

# -*- coding: utf-8 -*-
"""
Created on Tue Sep 15 01:01:58 2020

@author: liang
"""
#ゼロパディング＋インデックス
#str(1).zfill(6) + str(a.index(2) + 1).zfill(6)

N, M = map(int, input().split())
#d = [list() for _ in range(N)]
dic = dict()
P = list()

#insert O(M)
for i in range(M):
    p, y = map(int,input().split())
    #d[p-1].append(y)
    if p not in dic.keys():
        dic[p] = [y]
    else:
        dic[p].append(y)
    P.append((p,y))

#year sort O(N log N) => 重い　dict使用
#for i in range(N):
#    d[i].sort()
for key in dic.keys():
    dic[key].sort()

#search O(M)
for i in range(M):
    p, y = P[i]
    #ans = str(p).zfill(6)+str(d[p-1].index(y)+1).zfill(6)
    ans = str(p).zfill(6)+str(dic[p].index(y)+1).zfill(6)
    print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Sep 15 01:01:58 2020

@author: liang
"""
#ゼロパディング＋インデックス
#str(1).zfill(6) + str(a.index(2) + 1).zfill(6)
#index(x) が重い => indexを使わなくて良いようにする

N, M = map(int, input().split())
#d = [list() for _ in range(N)]
dic = dict()
dic2 = dict()
P = list()

#insert O(M)
for i in range(M):
    p, y = map(int,input().split())
    #d[p-1].append(y)
    if p not in dic.keys():
        dic[p] = [y]
    else:
        dic[p].append(y)
    P.append((p,y))

#year sort O(N log N) => 重い　dict使用
#for i in range(N):
#    d[i].sort()
for key in dic.keys():
    dic[key].sort()

for key in dic.keys():
    for i in range(len(dic[key])):
        dic2[dic[key][i]] = i+1
#search O(M)***
for i in range(M):
    p, y = P[i]
    #ans = str(p).zfill(6)+str(d[p-1].index(y)+1).zfill(6)
    # zfill 重い？
    ans = ''
    ans += '0'*( 6 - len(str(p))) + str(p)
    #t = dic[p].index(y)+1
    t = dic2[y]
    ans += '0'*( 6 - len(str(t))) + str(t)
    print(ans)
### BUGGY CODE ###

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

mo = 10**9 + 7
ans = 0
for i in range(len(li)):
    for j in range(i+1,len(li)):
       ans+=li[i]*li[j]
print(ans%mo)

### FIXED CODE ###

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

mo = 10**9 + 7
ans = 0
su = li[0]
for i in range(1,len(li)):
    ans += li[i]*su
    su+=li[i]
print(ans % mo)
### BUGGY CODE ###

N = int(input())
S = input()
sride = 1
count = 0
max_num = 0
for i in range(N-1):
  for j in range(N-sride):
    if S[j] == S[j+sride]:
      count += 1
      max_num = max(max_num, count)
    else:
      count = 0
    if count == sride:
      max_num = max(max_num, count)
      break
  sride += 1
  count = 0
print(max_num)


### FIXED CODE ###

N = int(input())
S = input()
sride = 1
count = 0
max_num = 0
for i in range(N-1):
  for j in range(N-sride):
    if S[j] == S[j+sride]:
      count += 1
      max_num = max(max_num, count)
    else:
      count = 0
    if count == sride:
      max_num = max(max_num, count)
      break
  sride += 1
  count = 0
print(max_num)
### BUGGY CODE ###

from collections import Counter
N = int(input())
S = [str(sorted(input())) for _ in range(N)]
count = 0
for i in range(N):
  for j in range(i+1, N):
    if Counter(S[i]) == Counter(S[j]):
      count += 1
print(count)

### FIXED CODE ###

from collections import Counter
N = int(input())
S = [str(sorted(input())) for _ in range(N)]
count = 0
for i in Counter(S).values():
  count += i*(i-1)//2
print(count)
### BUGGY CODE ###

from collections import deque
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
cost = [[600] * w for _ in range(h)]
nb = [(-1, 0), (0, -1), (1, 0), (0, 1)]
ans = 0


def bfs(sx, sy, gx, gy):
    q = deque([(sx, sy)])
    cost[sy][sx] = 0

    while q != deque([]):
        x, y = q.popleft()
        for dx, dy in nb:
            nx = x + dx
            ny = y + dy
            if 0 <= nx and nx < w and 0 <= ny and ny < h and s[ny][nx] == "." and cost[ny][nx] == 600:
                q.append((nx, ny))
                cost[ny][nx] = cost[y][x] + 1
                if nx == gx and ny == gy:
                    return cost[gy][gx]


ans = 0
for i in range(h):
    for j in range(w):
        for k in range(h):
            for l in range(w):
                cost = [[600] * w for _ in range(h)]
                tmp = bfs(j, i, l, k)
                if tmp != None:
                    ans = max(tmp, ans)

print(ans)

### FIXED CODE ###

def main():

    from collections import deque
    h, w = map(int, input().split())
    s = [input() for _ in range(h)]
    cost = [[600] * w for _ in range(h)]
    nb = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    ans = 0

    def bfs(sx, sy):
        q = deque([(sx, sy)])
        cost[sx][sy] = 0
        value = 0
        while q:
            x, y = q.popleft()
            for dx, dy in nb:
                nx = x + dx
                ny = y + dy
                if 0 <= nx and nx < h and 0 <= ny and ny < w and s[nx][ny] == "." and cost[nx][ny] == 600:
                    q.append((nx, ny))
                    cost[nx][ny] = cost[x][y] + 1
                    value = max(value, cost[nx][ny])
        return value

    ans = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == ".":
                cost = [[600] * w for _ in range(h)]
                tmp = bfs(i, j)
                ans = max(tmp, ans)

    print(ans)


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

n = int(input())

s = list(input())

res = 0
p = 0
p2 = 0

for i in range(n):
    fst = s[i]
    #print(i)
    p = i+1
    while (p < n):
        #print(p)
        
        if(s[p] != s[i]):
            scd = s[p]
            p2 = p+1
            while (p2 < n):
                if(s[p2] != fst and s[p2] != scd):
                    if(p-i != p2 -p):
                        res += 1
                
                p2 += 1
        
        p += 1
        
        
print(res)   

### FIXED CODE ###

n = int(input())

s = list(input())

res = 0

s_dif_g = [0]*n
s_dif_r = [0]*n
s_dif_b = [0]*n

for i in range(n):
    s_dif_r[i] = s[i::].count('R')
    s_dif_g[i] = s[i::].count('G')
    s_dif_b[i] = s[i::].count('B')

sample = ["R","G","B"]
for i in range(n):
    fst = s[i]
    for j in range(i+1,n-1):
        if(s[j] != fst):
            scd = s[j]
            for x in sample:
                if(x != fst and x != scd):
                    if(x == "R"):
                        res += s_dif_r[j+1]
                    if(x == "G"):
                        res += s_dif_g[j+1]
                    if(x == "B"):
                        res += s_dif_b[j+1]
                    if(2*j-i < n):    
                        if(s[2*j-i] == x):
                            res -= 1
            
            

print(res)
### BUGGY CODE ###

N=int(input())
l=list(map(int,input().split()))
a=0
for i in range(0,len(l)-1):
  for j in range(i+1,len(l)):
    a=(a+(l[i]*l[j])%(10**9+7))%(10**9+7)
print(a)

### FIXED CODE ###

N=int(input())
l=list(map(int,input().split()))
b=10**9+7
d=(sum(l))**2
c=0
for i in range(N):
  c=c+l[i]**2
print((d-c)//2%b)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	n,m=map(int,input().split())
	li=[]
	li2=[[] for _ in range(n+1)]
	for i in range(m):
		l,r,d=map(int,input().split())
		li.append((l,r,d))
		li.append((r,l,-d))
		li2[l].append((r,d))
		li2[r].append((l,-d))
	
	stack=[]
	check=set()
	a=[-10**10]*(n+1)

	for i in li:
		if i[0] in check:
			continue
		else:
			stack.append(i[0])
			a[i[0]]=0
			while stack:
				now=stack.pop()
				check.add(now)
				for j in li2[now]:
					if j[0] in check:
						if a[j[0]]-a[now]!=j[1]:
							print("No")
							exit(0)
						else:
							continue
					if j[0] in stack:
						continue
					a[j[0]] = a[now] + j[1]
					stack.append(j[0])
					
	print("Yes")
	
	
if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	n,m=map(int,input().split())
	li=[[] for _ in range(n+1)]
	for i in range(m):
		l,r,d=map(int,input().split())
		li[l].append((r,d))
		li[r].append((l,-d))
	
	q=deque()
	a=[None]*(n+1)

	for i in range(1,n+1):
		if a[i]==None:
			q=[i]
			a[i]=0
			while q:
				now=q.pop()
				for r,d in li[now]:
					if a[r]==None:
						a[r] = a[now] + d
						q.append(r)
					else:
						if a[r]-a[now]!=d:
							print("No")
							exit(0)
						else:
							continue
					
	print("Yes")
	
	
if __name__ == '__main__':
	main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

def resolve():
    def dfs(num, p=-1):
        for i in to[num]:
            if p == i:
                continue
            ns[i] += ns[num]
            dfs(i, num)

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

    to = [[] for _ in range(n)]

    for _ in range(n-1):
        a,b = map(int, input().split())
        a -= 1
        b -= 1
        to[a].append(b)
        to[b].append(a)

    ns = [0 for _ in range(n)]
    for _ in range(q):
        p, x = map(int, input().split())
        p -= 1
        ns[p] += x

    dfs(0)
    print(*ns)
resolve()

### FIXED CODE ###

from heapq import heappush,heappop

def resolve():
    n, q = map(int, input().split())

    hen = []
    for _ in range(n-1):
        a,b = map(int, input().split())
        heappush(hen,(a,b))

    ns = [0 for _ in range(n+1)]
    for _ in range(q):
        p, x = map(int, input().split())
        ns[p] += x

    # 操作はまとめられる。頂点nに対してpの和
    # 親から累積させながら末端へ下ろしていく

    while len(hen) > 0:
        a, b = heappop(hen)
        ns[b] += ns[a]

    print(*ns[1:n+1])
resolve()
### BUGGY CODE ###

N,K = (int(x) for x in input().split())
td_arr = []
for _ in range(N):
    td = tuple(int(x) for x in input().split())
    td_arr.append(td)

td_arr.sort(key=lambda x:x[1], reverse=True)

n_dm_set = set()
small_arr = []
d_dm = 0
for t,d in td_arr[:K]:
    if t in n_dm_set:
        small_arr.append(d)
    n_dm_set.add(t)
    d_dm += d

candidate_dict = {}
candidate_dict[len(n_dm_set)] = d_dm

n_x_set = set(n_dm_set)
d_x = d_dm
for t,d in td_arr[K:]:
    if t in n_x_set:
        continue
    if len(small_arr) == 0:
        break
    n_x_set.add(t)
    d_x += d
    d_x -= small_arr[-1]
    small_arr = small_arr[:-1]
    candidate_dict[len(n_x_set)] = d_x

ans = 0
for k,v in candidate_dict.items():
    ans = max(ans, k*k+v)

print(ans)


### FIXED CODE ###

N,K = (int(x) for x in input().split())
t_arr = [0]*(N+1)
d_arr = [0]*(N+1)
for i in range(N):
    t,d = tuple(int(x) for x in input().split())
    t_arr[i+1] = t
    d_arr[i+1] = d

td_index = list(range(1,N+1))
td_index.sort(key=lambda x:d_arr[x], reverse=True)

n_dm_set = set()
small_arr = []
d_dm = 0
for i in td_index[:K]:
    t = t_arr[i]
    d = d_arr[i]
    if t in n_dm_set:
        small_arr.append(d)
    n_dm_set.add(t)
    d_dm += d

current_max = len(n_dm_set)**2+d_dm

n_x_set = set(n_dm_set)
d_x = d_dm
nt_x = len(n_dm_set)
for i in td_index[K:]:
    if not small_arr:
        break
    t = t_arr[i]
    d = d_arr[i]
    if t in n_x_set:
        continue
    n_x_set.add(t)
    d_x += d
    d_x -= small_arr.pop()
    nt_x += 1
    current_max = max(current_max, nt_x**2+d_x)

print(current_max)
### BUGGY CODE ###

def resolve():
    S = input()
    Q = int(input())

    ans = list(S)

    for i in range(Q):
        T = list(input().split())

        if (T[0] == "1"):
            ans = ans[::-1]
        else:
            if (T[1] == "1"):
                ans.insert(0, T[2])
            else:
                ans.append(T[2])
            pass

    print("".join(ans))


resolve()

### FIXED CODE ###

def resolve():
    S = input()
    Q = int(input())

    rev = 0
    append_front_rev = ''
    append_rear = ''

    for i in range(Q):
        T = input().split()

        if (T[0] == "1"):
            rev ^= 1
            continue

        if (T[0] == "2" and T[1] == "1"):
            if rev == 0:
                append_front_rev += T[2]
            else:
                append_rear += T[2]
            continue

        if (T[0] == "2" and T[1] == "2"):
            if rev == 0:
                append_rear += T[2]
            else:
                append_front_rev += T[2]
            continue

    ans = append_front_rev[::-1] + S + append_rear
    if rev:
        ans = ans[::-1]

    print("".join(ans))


resolve()
### BUGGY CODE ###

N = int(input())
lis = [[0,0] for _ in range(N)]
X = [0 for _ in range(N)]
ans = []
for i in range(N):
    x,l = map(int, input().split(" "))
    lis[i] = (x-l,x+l)
    X[i] = x
s = []
ans_append = ans.append
s_append = s.append
for i in range(N):
    cnt = 0
    for j,v in enumerate(lis):
        a,b = v
        if i == j:
            continue
        else:
            if a < X[i] < b:
                cnt += 1
    if cnt == 0:
        ans_append(lis[i])
    if cnt == 1:
        s_append(lis[i])
print(len(ans) + len(s)//2)

### FIXED CODE ###

from collections import deque
N = int(input())
lis = []
ans = []
lis_append=lis.append
for i in range(N):
    x,l = map(int, input().split(" "))
    lis_append((x+l,x-l))
lis.sort()
lis = deque(lis)
ans.append(lis.popleft())
while lis:
    a = lis.popleft()
    if a[1] >= ans[-1][0]:
        ans.append(a)
print(len(ans))
### BUGGY CODE ###

import sys

n, m = [int(x) for x in sys.stdin.readline().split()]

s = []
d = []

for i in range(m):
	a, b = [int(x) for x in sys.stdin.readline().split()]
	if a == 1:
		s.append(b)
	if b == n:
		d.append(a)

for x in s:
	if x in d:
		print('POSSIBLE')
		break
	else:
		pass
else:
	print('IMPOSSIBLE')

### FIXED CODE ###

n, m = [int(x) for x in input().split()]

s = [0]*(n+1)
d = [0]*(n+1)

for i in range(m):
	a, b = [int(x) for x in input().split()]
	if a == 1:
		s[b] = 1
		if d[b] == 1:
			print('POSSIBLE')
			break
	elif b == n:
		d[a] = 1
		if s[a] == 1:
			print('POSSIBLE')
			break
else:
	print('IMPOSSIBLE')
### BUGGY CODE ###

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

a = []
j = 0
temp = 1
prev = s[0]
for i in s[1:]:
    if i == prev:
        prev = i
        temp += 1
    else:
        a.append(temp)
        prev = i        
        temp = 1
a.append(temp)

b = []
if s[0] == "1":
    b.append(sum(a[:2*k+1]))
    for i in range(len(a) - 2*k + 1):
        if i % 2 == 0:
            try:
                b.append(sum(a[i:i+(2*k) + 1]))
            except:
                continue
    print(max(b))

else:
    t = a[1:]
    b.append(sum(t[:2*k+1]))
    for i in range(len(t) - 2*k + 1):
        if i % 2 == 0:
            try:
                b.append(sum(t[i:i+(2*k) + 1]))
            except:
                continue
    b.append(sum(a[:2*k]))
    print(max(b))

### FIXED CODE ###

n, k = map(int, input().split())
s = input()
hand_list = []
for i in range(n):
    if i == 0:
        hand_list.append(i)
    else:
        if s[i] != s[i - 1]:
            hand_list.append(i)
hand_list.append(n)

ans_list = []
if len(hand_list) > 2 * k:
    for i in range(len(hand_list) - 2 * k):
        if s[hand_list[i]] == '1':
            ans = hand_list[min(i + 2 * k + 1, len(hand_list)-1)] - hand_list[i]
        else:
            ans = hand_list[i + 2 * k] - hand_list[i]
        ans_list.append(ans)
else:
    ans_list.append(n)
print(max(ans_list))
### BUGGY CODE ###

n = int(input())
c = list(input())
x = c.count("R")

end = []
for i in range(n+1):
    end.append("R"*i + "W"*(n-i))
#print(end)

newc = "".join(c)
ans = 0
j,k = -1,n
if newc in end:
    print(ans)
    exit()
while newc != end[x]:
    for i in range(j+1,n):
        if c[i] == "W":
            j = i
            c[i] = "R"
            break
    for i in reversed(range(k)):
        if c[i] == "R":
            k = i
            c[i] = "W"
            break
    newc = "".join(c)
    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
c = list(input())

x = c.count("R")

ans = 0
for i in range(x):
    if c[i] == "W":
        ans += 1

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

n, q = map(int, input().split())
s = input()

l = []
r = []

for i in range(q):
    _l, _r = map(int, input().split())
    l.append(_l)
    r.append(_r)

for i in range(q):
    ac = 0
	
    for j in range(l[i] - 1, r[i] - 1):
        if s[j : j + 2] == "AC":
            ac += 1
    
    print(ac)

### FIXED CODE ###

import re
 
n, q = map(int, input().split())
s = input()
 
l = []
r = []
 
for i in range(q):
    _l, _r = map(int, input().split())
    l.append(_l)
    r.append(_r)
 
memo = [0 for i in range(len(s))]
cnt = 0
 
for i in range(1, len(s)):
    if s[i - 1] == "A" and s[i] == "C":
        cnt += 1
    memo[i] = cnt
 
for i in range(q):
    print(memo[r[i] - 1] - memo[l[i] - 1])
### BUGGY CODE ###

import bisect

N=int(input())
S=list(input())
Q=int(input())

alphabet="abcdefghijklmnopqrstuvwxyz"
bag={l:[] for l in alphabet}
for i in range(N):
    bag[S[i]].append(i+1)
#print(bag)

for i in range(Q):
    Type,a,b=input().split()
    if Type=='1':
        a=int(a)
        bag[S[a-1]].remove(a)
        S[a-1]=b
        bisect.insort(bag[b],a)
    else:
        cnt=0
        a,b=int(a),int(b)
        for l in alphabet:
            bl=len(bag[l])
            if bl>0:
                left=bisect.bisect_left(bag[l],a)
                if left!=bl and bag[l][left]<=b:
                    cnt+=1
        print(cnt)

### FIXED CODE ###

import bisect

N=int(input())
S=list(input())
Q=int(input())

alphabet="abcdefghijklmnopqrstuvwxyz"
bag={l:[] for l in alphabet}
for i in range(N):
    bag[S[i]].append(i+1)
#print(bag)

for i in range(Q):
    Type,a,b=input().split()
    if Type=='1':
        a=int(a)
        if S[a-1]!=b:
            bag[S[a-1]].remove(a)
            S[a-1]=b
            bisect.insort(bag[b],a)
    else:
        cnt=0
        a,b=int(a),int(b)
        for l in alphabet:
            bl=len(bag[l])
            if bl>0:
                left=bisect.bisect_left(bag[l],a)
                if left!=bl and bag[l][left]<=b:
                        cnt+=1
        print(cnt)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000)

def main():
    n,q=map(int,input().split())
    G=[[] for i in range(n)] #隣接配列
    P=[0]*n #親のポイント
    for i in range(n-1):
        a,b=map(int,input().split())
        a-=1
        b-=1
        G[a].append(b)
        G[b].append(a)
    for i in range(q):
        p,x=map(int,input().split())
        p-=1
        P[p]+=x
    def dfs(s,p=-1):        
        for i in G[s]:
            if i==p:
                continue
            P[i]+=P[s]
            dfs(i,s)

    dfs(0)
    print(*P)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque

def main():
    n,q=map(int,input().split())
    G=[[] for i in range(n)] #隣接配列
    P=[0]*n #親のポイント
    for i in range(n-1):
        a,b=map(int,input().split())
        a-=1
        b-=1
        G[a].append(b)
        G[b].append(a)
    for i in range(q):
        p,x=map(int,input().split())
        p-=1
        P[p]+=x
    
    Chk=[0]*n #訪問済みチェック
    q=deque([0])
    while q: #qが空になるまで(BFS:幅優先探索)
        now=q.popleft() #取り出す
        Chk[now]=1 #訪問済みにする
        for i in G[now]: #子に対し
            if Chk[i]==0: #未訪問のとき
                P[i]+=P[now] #ポイント加算
                q.append(i) #親としてqに入れる

    print(*P)

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

import bisect


class SegTree:

    def __init__(self, n):
        # supposed that n = 2**m
        self.n = n
        self.val = [-1] * (2 * n - 1)

    def _update(self, a, b, v, k, l, r):
        if r <= a or b <= l:
            return
        if a <= l and r <= b:
            self.val[k] = v
        else:
            self._update(a, b, v, 2 * k + 1, l, (l + r) // 2)
            self._update(a, b, v, 2 * k + 2, (l + r) // 2, r)

    def update(self, a, b, v):
        # 区間[a, b)上の値をvに更新
        self._update(a, b, v, 0, 0, self.n)

    def query(self, x):
        # ノードxの値を返す
        k = self.n + x - 1
        ret = self.val[k]
        while k > 0:
            k = (k - 1) // 2
            ret = max(ret, self.val[k])
        return ret


def main():
    N, Q = list(map(int, input().split(' ')))
    work_list = list()
    for _ in range(N):
        work_list.append(list(map(int, input().split(' '))))
    # 工事は出発地から遠い順に並べておく
    work_list.sort(key=lambda work: work[2], reverse=True)
    D = list()
    for _ in range(Q):
        D.append(int(input()))
    # 一番最初に引っかかる工事のインデックスを求める
    QQ = 1
    while QQ < Q:
        QQ <<= 1
    tree = SegTree(QQ)
    for w, work in enumerate(work_list):
        s, t, x = work
        # s - x <= d < t - x だと工事に引っかかる
        left = bisect.bisect_left(D, s - x)
        right = bisect.bisect_left(D, t - x)
        tree.update(left, right, w)
    for q in range(Q):
        w = tree.query(q)
        if w == -1:
            print(-1)
        else:
            print(work_list[w][2])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import bisect
 
 
class SegTree:
 
    def __init__(self, n):
        # supposed that n = 2**m
        self.n = n
        self.val = [-1] * (2 * n - 1)
 
    def _update(self, a, b, v, k, l, r):
        # 区間[a, b)上の値をvに更新
        if r <= a or b <= l:
            return
        if a <= l and r <= b:
            self.val[k] = v
        else:
            self._update(a, b, v, 2 * k + 1, l, (l + r) // 2)
            self._update(a, b, v, 2 * k + 2, (l + r) // 2, r)
 
    def query(self, x):
        # ノードxの値を返す
        k = self.n + x - 1
        ret = self.val[k]
        while k > 0:
            k = (k - 1) // 2
            ret = max(ret, self.val[k])
        return ret
 
 
def main():
    N, Q = list(map(int, input().split(' ')))
    work_list = [list(map(int, input().split(' '))) for n in range(N)] 
    # 工事は出発地から遠い順に並べておく
    work_list.sort(key=lambda work: work[2], reverse=True)
    D = [int(input()) for q in range(Q)]
    # 一番最初に引っかかる工事のインデックスを求める
    QQ = 1
    while QQ < Q:
        QQ <<= 1
    tree = SegTree(QQ)
    for w, work in enumerate(work_list):
        s, t, x = work
        # s - x <= d < t - x だと工事に引っかかる
        left = bisect.bisect_left(D, s - x)
        right = bisect.bisect_left(D, t - x)
        tree._update(left, right, w, 0, 0, QQ)
    for q in range(Q):
        w = tree.query(q)
        if w == -1:
            print(-1)
        else:
            print(work_list[w][2])
 
 
if __name__ == '__main__':
    main()