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

from collections import deque

def cndP(l,n,p1,p2):
    d = set()
    min = sum(l[:])
    length = len(l)
    for i in range(length-n+1):
        s = sum(l[i:i+n])
        if s < min:
            min = s
        if p2 == None:
            if p1 < s:
                d.add(s)
        else:
            if p1 < s < p2:
                d.add(s)
    d.add(min)
    return sorted(d)

def pIsAccptbl(w,k,p):
    tr = 0
    c = 0
    d = deque(w)
    while(d):
        tmp = d.popleft()
        if(tmp > p):
            return False
        
        if( tr + tmp > p):
            tr = tmp
            c += 1
        else:
            tr += tmp
        if c+1>k:
            return False
    return True

n,k = [int(x) for x in input().split()]
w = []
for i in range(n):
    e = int(input())
    w.append(e)

p = max(w)

if(pIsAccptbl(w,k,p)):
    print(p)
else:
    n=2
    p1 = p
    p2 = None
    while(1):
        s = cndP(w,n,p1,p2)
        if not p2 == None:
            if s[0] > p2:
                print(p2)
                break
        for i in s:
            if(pIsAccptbl(w,k,i)):
                p2 = i
                break
            if(p2==None):
                p1 = i
        if (n == len(w)):
            print(p2)
            break
        n+=1

### FIXED CODE ###

from collections import deque

def isPa(w,k,p):
    tr = 0
    c = 0
    d = deque(w)
    while(d):
        tmp = d.popleft()
        if(tmp > p):
            return False
        
        if( tr + tmp > p):
            tr = tmp
            c += 1
        else:
            tr += tmp
        if c+1>k:
            return False
    return True

def MaxInP(w,k,p):
    maxinp = 0
    tmp = 0
    d = deque(w)
    while(d):
        tmp += d.popleft();
        if(tmp > p):
            if(tmp > maxinp):
                maxinp = tmp
            tmp = 0
    return maxinp

n,k = [int(x) for x in input().split()]
w = deque()
for i in range(n):
    w.append(int(input()))
    
mean = int(sum(w)/k)
maxinp = MaxInP(w,k,mean)

if k == 1:
    print(mean)
else:
    minP = mean
    maxP = maxinp
    while(True):
        m = int ((minP + maxP)/2)
        if ( isPa(w,k,m) ):
            maxP = m
        else:
            minP = m
        if (minP+1 == maxP or minP == maxP):
            print(maxP)
            break
### BUGGY CODE ###

String = input()
sbstr_list = []
tmp = ''
isRzone = True
for s in String:
    if (isRzone):
        isRzone = (s=='R')
        tmp += s
    else:
        if (s == 'R'):
            sbstr_list.append(tmp)
            isRzone = True
            tmp = s
        else:
            tmp += s
sbstr_list.append(tmp)
for sbstr in sbstr_list:
    length = len(sbstr)
    subans = ["0"] * length
    pos = sbstr.find('RL')
    # print(pos)
    subans[pos] = str(1 + pos//2 + (length-pos-1)//2)
    subans[pos+1] = str(1 + (pos+1)//2 + (length-pos-2)//2)
    print(" ".join(subans), end=' ')
print('')


### FIXED CODE ###

String = input()
sbstr_list = ['R' + substr + 'L' for substr in String.split('LR')]
sbstr_list[0] = sbstr_list[0][1:]
sbstr_list[-1] = sbstr_list[-1][:-1]
for sbstr in sbstr_list:
    length = len(sbstr)
    subans = ["0"] * length
    pos = sbstr.find('RL')
    # print(pos)
    subans[pos] = str(1 + pos//2 + (length-pos-1)//2)
    subans[pos+1] = str(1 + (pos+1)//2 + (length-pos-2)//2)
    print(" ".join(subans), end=' ')
print('')
### BUGGY CODE ###

N, P = map(int, input().split())
p = P**(1/N)
if p % 1 == 0:
    print(int(p))
    exit()


p = int(p) + 1

n = 0
for i in range(1,p+1):
    if P % (i**N) == 0:
        n = i
print(n)

### FIXED CODE ###

N, P = map(int, input().split())
p = P**(1/N)
if p % 1 == 0:
    print(int(p))
    exit()

lim = int(p) + 1

dic = {}

def my(N,newP):
    for i in range(2,lim+1):
        while newP % i == 0:
            dic[i] = dic.get(i,0) + 1
            newP = newP // i
        if newP < i or i == lim:
            res = 1
            for j,k in dic.items():
                res *= j**(k//N)
            print(res)
            exit()
my(N,P)
### BUGGY CODE ###

import sys

n = int(input())
aaa = list(map(int, sys.stdin.readlines()))

dp = [-1]
for a in aaa:
    for i, m in enumerate(dp):
        if m < a:
            dp[i] = a
            break
    else:
        dp.append(a)
print(len(dp))


### FIXED CODE ###

import sys
from bisect import bisect

n = int(input())
aaa = list(map(int, sys.stdin.readlines()))

dp = [1]
for a in aaa:
    a *= -1
    i = bisect(dp, a)
    if i < len(dp):
        dp[i] = a
    else:
        dp.append(a)
print(len(dp))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(500*500) # default 1000

def dfs(v,p=-1): # vertices & parent idx
    for child in to[v]:
        if child==p:
            continue
        ans[child]+=ans[v]
        # print('vertices=',v)
        # print('child=',child)
        # print('parent=',p)
        dfs(child,v)
        
N, Q = map(int, input().strip().split())

to=[[] for j in range(N)] # N points
ans=[0]*N # N points

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

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

dfs(0)
for i in range(N):
    print(ans[i],end=' ')

### FIXED CODE ###

N, Q = map(int, input().strip().split())

# visited = [False for _ in range(N)]
# def dfs(v): # vertices & parent idx
#     visited[v]=True
#     for child in to[v]:
#         if visited[child]==True:
#             continue
#         ans[child]+=ans[v]
#         dfs(child)
# def dfs(v,p=-1): # vertices & parent idx
#     for child in to[v]:
#         if child==p:
#             continue
#         ans[child]+=ans[v]
#         dfs(child,v)

to=[[] for j in range(N)] # N points
ans=[0]*N # N points

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

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

# dfs(0)
stack=[0]
visited=[False]*N
while stack:
    v=stack.pop()
    visited[v]=True
    for child in to[v]:
        if visited[child] ==False:
            # visited[v]=True
            ans[child]+=ans[v]
            stack.append(child)
for i in range(N):
    print(ans[i],end=' ')
# print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    not_n = (int(i) for i in range(1,n))
    print(sum(not_n))
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    not_n = ((n-1) * n)// 2
    print(not_n)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
d = dict()
for o in range(N):
    d[o] = A[o]
B = sorted(A)
B.append(0)
p = B[0]
y = dict()
u = 0
for k in range(N+1):
    q = B[k]
    if p != q:
        y[p] = u
        u=0
    u += 1
    p = q
for j in range(N):
    g = 0
    x = d[j]
    y[x] -= 1
    va = list(y.values())
    for l in va:
        g += l*(l-1)//2
    print(g)
    y[x] += 1

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = sorted(A)
B.append(0)
p = B[0]
y = dict()
u = 0
for k in range(N+1):
    q = B[k]
    if p != q:
        y[p] = u
        u = 0
    u += 1
    p = q
All = 0
for l in y.values():
    All +=l*(l-1)//2
for j in range(N):
    x = A[j]
    print(All+(y[x]-1)*(y[x]-2)//2-y[x]*(y[x]-1)//2)
### BUGGY CODE ###

import sys
from sys import stdin
input = stdin.readline
N,A=map(int, input().split())
x=[int(x) for x in input().split()]
x.append(0)
x.sort()
W=sum(x)
dp=[[[0]*(W+1) for _ in range(N+1)] for _ in range(N+1)]
for j in range(N+1):
    dp[j][0][0]=1
for j in range(1,N+1):
    xj=x[j]
    for k in range(1, N+1):
        for s in range(1, W+1):
            if s<xj:
                dp[j][k][s]=dp[j-1][k][s]
            else:
                dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-xj]

ans=0
for k in range(1,N+1):
    if k*A<=W:
        ans+=dp[N][k][k*A]
    else:
        break
print(ans)


### FIXED CODE ###

import sys
from sys import stdin
input = stdin.readline

def solve(N, A, x):
    W=sum(x)
    dp=[[[0]*(W+1) for _ in range(N+1)] for _ in range(N+1)]
    for j in range(N+1):
        dp[j][0][0]=1
    for j in range(1,N+1):
        xj=x[j-1]
        for k in range(1, N+1):
            for s in range(1, W+1):
                if s<xj:
                    dp[j][k][s]=dp[j-1][k][s]
                else:
                    dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-xj]

    ans=0
    for k in range(1,N+1):
        if k*A<=W:
            ans+=dp[N][k][k*A]
        else:
            break
    return ans


def main(args):
    N,A=map(int, input().split())
    x=[int(x) for x in input().split()]
    ans=solve(N,A,x)
    print(ans)

if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

def resolve():
    def Dijkstra(s, g):
        import heapq
        d = {}
        d[s] = 0
        queue = []
        for q in edge[s]:
            heapq.heappush(queue, q)
        while queue:
            dist, point = heapq.heappop(queue)
            q = [point]
            while q:
                point = q.pop()
                if point in d:
                    continue
                d[point] = dist
                if point == g:
                    return dist
                for nextdist, nextp in edge[point]:
                    if not nextp in d:
                        if nextdist == 0:
                            q.append(nextp)
                        else:
                            heapq.heappush(queue, (dist + nextdist, nextp))
        return -1
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    n, m = map(int, input().split())
    edge = defaultdict(set)
    for _ in range(m):
        p, q, c = map(int, input().split())
        p, q = p - 1, q - 1
        edge[(p, -1)].add((1, (p, c)))
        edge[(q, -1)].add((1, (q, c)))
        edge[(p, c)].add((0, (p, -1)))
        edge[(q, c)].add((0, (q, -1)))
        edge[(p, c)].add((0, (q, c)))
        edge[(q, c)].add((0, (p, c)))
    print(Dijkstra((0, -1), (n - 1, -1)))


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

def resolve():
    def Dijkstra(s, g):
        from collections import deque
        d = {s}
        queue = deque()
        for q in edge[s]:
            queue.append((1, q))
        while queue:
            dist, point = queue.popleft()
            if point in d:
                continue
            d.add(point)
            if point == g:
                return dist
            for nextp in edge[point]:
                if not nextp in d:
                    if not -1 in point or -1 in nextp:
                        queue.appendleft((dist, nextp))
                    else:
                        queue.append((dist + 1, nextp))
        return -1
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    n, m = map(int, input().split())
    edge = defaultdict(set)
    for _ in range(m):
        p, q, c = map(int, input().split())
        p, q = p - 1, q - 1
        edge[(p, c)].add((q, c))
        edge[(q, c)].add((p, c))
        edge[(p, c)].add((p, -1))
        edge[(q, c)].add((q, -1))
        edge[(p, -1)].add((p, c))
        edge[(q, -1)].add((q, c))
    print(Dijkstra((0, -1), (n - 1, -1)))


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

# coding: utf-8

n=int(input())
p=list(map(int,input().split()))
P=[]
cnt=0

for i in p:
    P.append(i)
    if i==min(P):
        cnt+=1

print(cnt)

### FIXED CODE ###

# coding: utf-8

import sys
input=sys.stdin.readline

n=int(input())
p=list(map(int,input().split()))
P=[]
cnt=0
lowest=float("inf")

for i in p:
    if i<=lowest:
        lowest=i
        cnt+=1

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

n, m, k = map(int, input().split())
a = list(map(int, input().split())) 
a.insert(0,0)
b = list(map(int, input().split())) 
b.insert(0,0)


max = 0
for i in range(n+1):
    sum_a = sum(a[ii] for ii in range(i+1))
    if sum_a > k:
        max = i-1 if i-1 > max else max
        break
    else:
        for j in range(m+1):
            sum_ab = sum_a + sum(b[jj] for jj in range(j+1))
            if sum_ab > k:
                max = i+j-1 if i+j-1 > max else max
                break
            else:
                max = i+j if i+j > max else max

print(max)

### FIXED CODE ###

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


sum_a = [0]
for i in range(n):
    sum_a.append(sum_a[i] + a[i])

sum_b = [0]
for i in range(m):
    sum_b.append(sum_b[i] + b[i])


a_i = 0
b_i = 0
for i in range(n+1):
    if sum_a[i] > k:
        break
    else:
        a_i = i

for i in range(m+1):
    if sum_a[a_i] + sum_b[i] > k:
        break
    else:
        b_i = i


ans = a_i + b_i
for i in range(a_i, -1, -1):
    for j in range(b_i, m+1):
        if sum_a[i] + sum_b[j] > k:
            b_i = j - 1
            break
        else:
            ans = max(ans, i+j)

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

n =int(input())
s = input()

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

### FIXED CODE ###


n =int(input())
s = input()


ans = n
if n < 10:
	for i in range(n):
		ans = min((s[:i].count("W")+s[i+1:].count("E")),ans)
else:
	change = (s[1:].count("E"))
	ans = change
	for i in range(1,n):

		t = 0
		if s[i-1] == "W":
			t += 1
		if s[i] == "E":
			t -= 1
		change += t
		ans = min(ans,change)

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

h, n = map(int, input().split())
a = []
b = []
for i in range(n):
    a_, b_ = map(int, input().split())
    a.append(a_)
    b.append(b_)

f_inf = float("inf")
dp = [f_inf] * (h + max(a))
dp[0] = 0
for i in range(n):
    for j in range(h):
        if dp[j] != f_inf:
            if dp[j + a[i]] > dp[j] + b[i]:
                dp[j + a[i]] = dp[j] + b[i]

print(min(dp[h:]))

### FIXED CODE ###

h, n = map(int, input().split())
a = []
b = []
for i in range(n):
    a_, b_ = map(int, input().split())
    a.append(a_)
    b.append(b_)

f_inf = float("inf")
dp = [f_inf] * (h + max(a))
dp[0] = 0
for i in range(n):
    for j in range(h):
        if dp[j] != f_inf:
            if dp[j + a[i]] > dp[j] + b[i]:
                dp[j + a[i]] = dp[j] + b[i]

print(min(dp[h:]))
### BUGGY CODE ###

import bisect
n=int(input())
lists=list(map(int,input().split()))
lists=sorted(lists)

cnt=0
import math
for i in range(n):
    for j in range(i+1,n):
        #i<j 
        x=lists[i]
        y=lists[j]
        left=i 
        right=j 
        index=bisect.bisect_right(lists,y-x)
        cnt+=min(j-i-1,j-index)

print(cnt)

### FIXED CODE ###

import bisect
n=int(input())
lists=list(map(int,input().split()))
lists=sorted(lists)

cnt=0
import math
for i in range(n):
    for j in range(i+1,n):
        #i<j 
        x=lists[i]
        y=lists[j]
        left=i 
        right=j 
        index=bisect.bisect_right(lists,y-x)
        cnt+=min(j-i-1,j-index)

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

import math
import collections

def combinations_count(n, r):
	if n < 2:
		return 0
	return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

_ = int(input())
ns = input().split(" ")
cs = collections.Counter(ns)

c = 0
for n in ns:
	for k, v in cs.items():
		if v==1:
			c += 0
		elif n==k:
#			c += math.factorial(v-2)
			c += combinations_count(v-1, 2)
		else:
#			c += math.factorial(v-1)
			c += combinations_count(v, 2)
	print(c)
	c = 0


### FIXED CODE ###

N = int(input())
A = [int(a)-1 for a in input().split()]
X = [0] * N
for a in A:
	X[a] += 1
s = 0
for x in X:
	s += x * (x-1) // 2
for a in A:
	print(s - (X[a] - 1))
### BUGGY CODE ###

N = int(input())
X = input()
ans = [1 for _ in range(N)]
#original 1 count
l = 0
for k in range(N):
  if X[k] == '1':
    l+=1


intN = int(X, 2)
if l >1:
  N1 = intN %(l-1)
N0 = intN % (l+1)


start = []
if N == 1:
  if X[0] == '1':
    print(0)
    exit()
  else:
    print(1)
    exit()

else:
  for k in range(N):
    if X[k] == '1':
      if l == 1:
        ans[k] = 0
        ia =0
      else:  
        ia = (N1 - pow(2,N-k-1))%(l-1)
    else:
      ia = (N0 + pow(2, N-k-1))%(l+1)
    start.append(ia)

ml = len(bin(l+1))-2
poplist = [[] for _ in range(ml)]
poplist[0] = [0,1]
for k in range(1, ml):
  for m in range(k):
    poplist[k] += poplist[m]
  for m in range(len(poplist[k])):
    poplist[k][m] += 1

newpoplist = []
for _ in range(len(poplist)):
  newpoplist += poplist[_] 

for k in range(len(start)):
  for count in range(10*5):
    if start[k] == 0:
      ans[k] += count
      break
    else:
      start[k] = start[k] % newpoplist[start[k]]

for k in range(N):
  print(ans[k])

### FIXED CODE ###

N = int(input())
X = input()
ans = [1 for _ in range(N)]
#original 1 count
l = 0
for k in range(N):
  if X[k] == '1':
    l+=1
if l == 0:
  for _ in range(N):
    print(1)
  exit()
if l == 1:
  if X[-1] == '1':
    for _ in range(N-1):
      ans[_] = 2
  else:
    ans[-1] = 2 
  for k in range(N):
    if X[k] =='1':
      ans[k] = 0 
  for _ in range(N):
    print(ans[_])
  exit()


intN = int(X, 2)
N1 = intN %(l-1)
N0 = intN % (l+1)


start = []
if N == 1:
  if X[0] == '1':
    print(0)
    exit()
  else:
    print(1)
    exit()
else:
  s1 = 1
  s0 = 1
  for k in range(N-1, -1, -1):
    if X[k] == '1':      
      ia = (N1 - s1)%(l-1)
    else:
      ia = (N0 + s0)%(l+1)
    start.append(ia)
    s1 = s1*2%(l-1)
    s0 = s0*2%(l+1)
start = start[::-1]
"""
ml = len(bin(l+1))-2
poplist = [0 for _ in range(N)]
t = 1
while t < N + 1:
  t *= 2
  for k in range(t//2, N, t):
    for j in range(t//2):
      if k+j>N-1:
        break
      poplist[k+j] += 1
"""

def popcount(n):
  c = 0
  n = bin(n)[2:]
  for k in range(len(n)):
    if n[k] == '1':
      c+=1
  return c

for k in range(len(start)):
  for count in range(10*5):
    if start[k] == 0:
      ans[k] += count
      break
    else:
      start[k] = start[k] % popcount(start[k])

for k in range(N):
  print(ans[k])
### BUGGY CODE ###

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

S_ba = []
S_ab = []
for i in range(N):
    if A[i] < B[i]: S_ba.append(B[i] - A[i])
    else: S_ab.append(A[i] - B[i])

if sum(S_ba) > sum(S_ab):
    print(-1)
    exit()
    
ans = len(S_ba)
now = 0
S_ab.sort(reverse=True)
for i in range(len(S_ab)):
    # now += A[i] - B[i]
    if sum(S_ba) <= now: break
    now += S_ab[i]
    ans += 1

print(ans)


### FIXED CODE ###

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

S_ba = []
S_ab = []
for i in range(N):
    if A[i] < B[i]: S_ba.append(B[i] - A[i])
    elif A[i] > B[i]: S_ab.append(A[i] - B[i])

if sum(S_ba) > sum(S_ab):
    print(-1)
    exit()
    
ans = len(S_ba)
now = 0
rem = sum(S_ba)
S_ab.sort(reverse=True)
for i in range(len(S_ab)):
    if rem <= now: break
    now += S_ab[i]
    ans += 1

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

import numpy as np

n = int(input())
a = input().split()
np_a=np.array(a, dtype=int)

ans=np.zeros(n, dtype=int)

for i in range(0,n):
  loop=list(range(0,n))
  loop.pop(i)
  for j in loop:
    if (j == loop[0]): 
      atai=np_a[j]
    else:
      atai=atai ^ np_a[j]
  ans[i]=atai
  
print (*ans)

### FIXED CODE ###

import numpy as np

n = int(input())
a = input().split()
np_a=np.array(a, dtype=int)

ans=np.zeros(n, dtype=int)

all=np_a[0]
for i in range(1,n):
  all=all ^ np_a[i]
  

for i in range(0,n):
  ans[i]=all ^ np_a[i]
  
print (*ans)
### BUGGY CODE ###

if __name__ == '__main__':
    N = int(input())
    C = list(input())
    cnt = 0
    red_cnt = 0
    for c in sorted(C):
        if c == 'R':
            red_cnt += 1
        else:
            break
    for i in range(N):
        if C[i] == 'W':
            for j in range(red_cnt, N):
                if C[j] == 'R':
                    C[i] = 'R'
                    C[j] = 'W'
                    cnt += 1
                    red_cnt = j+1
    print(cnt)

### FIXED CODE ###

if __name__ == '__main__':
    N = int(input())
    C = list(input())
    cnt = 0
    red_cnt = 0
    for c in C:
        if c == 'R':
            red_cnt += 1

    for i in range(red_cnt):
        if C[i] == 'W':
            for j in range(red_cnt, N):
                if C[j] == 'R':
                    C[i] = 'R'
                    C[j] = 'W'
                    cnt += 1
                    red_cnt = j+1
    print(cnt)
### BUGGY CODE ###

from operator import mul
from functools import reduce
    

if __name__ == '__main__':
    try:

        N = int(input())
        A = list(map(int, input().split()))
        ans = reduce(mul, A)
        if ans > 10 ** 18:
            print(-1)
        else:
            print(ans)
    except:
        if 0 in A:
            print(0)
        else:
            print(-1)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 1
for a in A:
    ans *= a
    if ans > 1000000000000000000:
            print(-1)
            quit()
print(ans)
### BUGGY CODE ###

import collections as c
n = int(input())
s = [input() for _ in range(n)]

ans = []
for i in range(n):
    ans.append(c.Counter(s[i]))

cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        if ans[i] == ans[j]:
            cnt += 1

print(cnt)

### FIXED CODE ###

import collections as c

N = int(input())
S = sorted(["".join(sorted(input())) for _ in range(N)])

D = c.Counter(S)

D_value = []

for a in D.values():
	D_value.append(a)

ans = 0

for i in D_value:
	if i == 0:
		continue
	ans += (i * (i-1)) // 2

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

N, M = map(int,input().split())
G = [[10 ** 9 for _ in range(N)] for _ in range(N)]
for i in range(M):
  l,r,c = map(int,input().split())
  G[l-1][r-1] = c
for i in range(1,N):
  G[i][i-1] = 0
#print(G)
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra
G = csgraph_from_dense(G, null_value=10**9)
dist_matrix = dijkstra(G,indices = 0)
print(-1 if dist_matrix[-1] == float("inf") else int(dist_matrix[-1]))

### FIXED CODE ###

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, M = map(int, readline().split())
lines = readlines()
edge = np.array([line.split() for line in lines], dtype = np.int64)
edge = sorted(edge,key=lambda x:(x[0],x[1],x[2]))

for i in range(1,M):
  if edge[i][0] == edge[i-1][0] and edge[i][1] == edge[i-1][1]:
    edge[i][2] = 0
#print(edge)
x = np.arange(N,1,-1)
y = np.arange(N-1,0,-1)
z = np.zeros(N-1,int)
X = np.vstack([x,y,z]).T
edge = np.concatenate([X,edge]).T
graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
distance_mat = dijkstra(graph, directed = True, indices = 0)
#print(distance_mat)
print(-1 if distance_mat[-1] == float("inf") else int(distance_mat[-1]))
### BUGGY CODE ###

import bisect

def solve():
    N, Q = [int(_) for _ in raw_input().split()]
    STX = []
    for i in range(N):
        Si, Ti, Xi = [int(_) for _ in raw_input().split()]
        STX.append((Si - Xi, Ti - Xi, Xi))
    D = []
    for i in range(Q):
        D.append((int(raw_input()), i))
    STX.sort(key = lambda x:x[2], reverse=True)
    # D have already been sorted based on settings on problem
    ans = [-1] * Q
    for i in range(N):
        Li, Ri, Xi = STX[i]
        if len(D) == 0:
            break
        it = bisect.bisect_left(D, (Li, -1))
        while it < len(D):
            if D[it][0] >= Ri:
                break
            ans[D[it][1]] = Xi
            it += 1
    for i in range(Q):
        print ans[i]

if __name__ == '__main__':
    solve()


### FIXED CODE ###

import bisect

def solve():
    N, Q = [int(_) for _ in raw_input().split()]
    STX = []
    for i in range(N):
        Si, Ti, Xi = [int(_) for _ in raw_input().split()]
        STX.append((Si - Xi, Ti - Xi, Xi))
    D = []
    for i in range(Q):
        D.append((int(raw_input()), i))
    STX.sort(key = lambda x:x[2])
    # D have already been sorted based on settings on problem
    ans = [-1] * Q
    l = [None] * Q
    for i in range(N):
        Li, Ri, Xi = STX[i]
        lit = bisect.bisect_left(D, (Li, -1))
        rit = bisect.bisect_left(D, (Ri, -1))
        while lit < rit:
            if l[lit] is not None:
                lit = l[lit]
            else:
                ans[D[lit][1]] = Xi
                l[lit] = rit
                lit += 1
    for i in range(Q):
        print ans[i]

if __name__ == '__main__':
    solve()