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

import sys
sys.setrecursionlimit(10**8)
n,w=map(int,input().split())
l=[[]]
for i in range(n):
  l.append(list(map(int,input().split())))
dp=[[-1 for i in range(w+2)] for j in range(n+2)]
def knap(x,y):
  if dp[x][y]!=-1:
    return dp[x][y]
  if x==n+1:
    res=0
  elif y<l[x][0]:
    res=knap(x+1,y)
  else:
    res=max(knap(x+1,y),knap(x+1,y-l[x][0])+l[x][1])
  dp[x][y]=res
  return res
knap(1,w)
print(dp[1][w])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
def knapsack(N,W,weight,value):
  #初期化
  inf=float("inf")
  dp=[[-inf for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=0

  #DP
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
        dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])
      else: #入る可能性はない
        dp[i+1][w]=dp[i][w]
  return dp[N][W]
n1,w1=map(int,input().split())
lw=[]
lv=[]
for i in range(n1):
  w,v=map(int,input().split())
  lw.append(w)
  lv.append(v)
print(knapsack(n1,w1,lw,lv))
### BUGGY CODE ###

from sys import exit
n, m = map(int, input().split())
s = input()

if n <= m:
    print(n)
    exit()

one_sequence = 0
for i in range(1, n):
    if s[i] == "1":
        one_sequence += 1
        if one_sequence == m:
            print(-1)
            exit()
    else:
        one_sequence = 0

pos = n
ans = ""
while pos != 0:
    for i in range(1, m+1)[::-1]:
        if pos-i < 0:
            continue
        if s[pos-i] != "1":
            ans = str(i) + " " + ans
            pos -= i
            break
print(ans.strip())


### FIXED CODE ###

from sys import exit
n, m = map(int, input().split())
s = input()

one_sequence = 0
for i in range(1, n):
    if s[i] == "1":
        one_sequence += 1
        if one_sequence == m:
            print(-1)
            exit()
    else:
        one_sequence = 0

pos = n
ans = ""
while pos != 0:
    for i in range(1, m+1)[::-1]:
        if pos-i < 0:
            continue
        if s[pos-i] != "1":
            ans = str(i) + " " + ans
            pos -= i
            break
print(ans)
### BUGGY CODE ###

import functools
from math import gcd
N = int(input())
A = list(map(int, input().split()))


def factorization(n):
    arr = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt
    if temp!=1:
        arr[temp] = 1
    if arr==[]:
        arr[n] = 1
    return arr


B = []
for a in A:
    B += factorization(a).keys()

if len(set(B)) == len(B):
    print("pairwise coprime")
elif functools.reduce(gcd, A) == 1:
    print("setwise coprime")
else:
    print("not coprime")


### FIXED CODE ###

import functools
from math import gcd
N = int(input())
A = list(map(int, input().split()))
MAX = 10 ** 6 + 10

if functools.reduce(gcd, A) != 1:
    print("not coprime")
    exit()

prime_list = [i for i in range(MAX + 1)]
p = 2
while p * p <= MAX:
    if prime_list[p] == p:
        for q in range(2*p, MAX+1, p):
            if prime_list[q] == q:
                prime_list[q] = p
    p += 1

prime = set()
for a in A:
    tmp = set()
    while a > 1:
        tmp.add(prime_list[a])
        a //= prime_list[a]
    for p in tmp:
        if p in prime:
            print("setwise coprime")
            exit()
        prime.add(p)
else:
    print("pairwise coprime")
### BUGGY CODE ###

n,m=map(int,input().split())
to={}
rv={}
for _ in range(m):
    u,v=map(int,input().split())
    to.setdefault(u,[])
    to[u]+=[v]
    rv.setdefault(v, [])
    rv[v] += [u]
s,t=map(int,input().split())

ss=set()
ss.add(s)
gs=set()
gs.add(t)
vst1=set()
vst2=set()
cnt=0

while 1:
    cnt+=1
    for _ in range(3):
        nss=set()
        for i in ss:
            if i not in to:continue
            for j in to[i]:
                nss.add(j)
        ss=nss
    if ss&gs:
        print(cnt)
        exit()
    if ss<=vst1:
        print(-1)
        exit()
    vst1|=ss

    cnt+=1
    for _ in range(3):
        ngs=set()
        for i in gs:
            if i not in rv:continue
            for j in rv[i]:
                ngs.add(j)
        gs=ngs
    if ss&gs:
        print(cnt)
        exit()
    if gs<=vst2:
        print(-1)
        exit()
    vst2|=gs


### FIXED CODE ###

def f(n, m):
    to = {}
    for _ in range(m):
        u, v = map(int, input().split())
        to.setdefault(u, [])
        to[u] += [v]
    s, t = map(int, input().split())
    vst = [[False] * 3 for _ in range(n + 1)]
    a = [s]
    vst[s][0] = True
    cnt = 0
    while a:
        b = []
        cnt += 1
        j = cnt % 3
        for ak in a:
            if ak not in to: continue
            for i in to[ak]:
                if vst[i][j]: continue
                vst[i][j] = True
                b.append(i)
            if vst[t][0]:
                print(cnt // 3)
                exit()
        a = b
    print(-1)

n, m = map(int, input().split())
f(n, m)
### BUGGY CODE ###

m=10**9+7
i=s=r=0
f=1
input()
a=input().split()
for x in a:i+=1;s+=pow(i,m-2,m);r+=int(x)*~-s+int(a[-i])*s;f=f*i
print(r*f%m)

### FIXED CODE ###

m=10**9+7
i=s=r=0
f=1
_,*a=open(0).read().split()
for x in a:i+=1;s+=pow(i,m-2,m);r+=int(x)*~-s+int(a[-i])*s;f=f*i%m
print(r*f%m)
### BUGGY CODE ###

H,W,M = map(int, input().split())
grid = [[0 for _ in range(W)] for _ in range(H)]

hc = [(0, h) for h in range(H)]
wc = [(0, w) for w in range(W)]

for _ in range(M):
    h,w = map(int, input().split())
    h-=1
    w-=1
    grid[h][w] = 1
    hc[h] = (hc[h][0] + 1, hc[h][1])
    wc[w] = (wc[w][0] + 1, wc[w][1])

hc = sorted(hc, key=lambda p: p[0], reverse=True)
wc = sorted(wc, key=lambda p: p[0], reverse=True)

hmax = hc[0][0]
wmax = wc[0][0]

uh = 0
while uh < H and hc[uh][0] == hmax:
    uh += 1

uw = 0
while uw < W and wc[uw][0] == wmax:
    uw += 1

# print(uw, uh)
#print(grid)
#print(wc, uw)
#print(hc, uh)

found = False
for h in range(uh):
    for w in range(uw):
        if grid[hc[h][1]][wc[w][1]] == 0:
            found = True
            break
    if found:
        break

print(hmax + wmax if found else hmax + wmax - 1)

### FIXED CODE ###

H,W,M = map(int, input().split())
# grid = [[0 for _ in range(W)] for _ in range(H)]
bombs = set()

hc = [0 for h in range(H)]
wc = [0 for w in range(W)]

for _ in range(M):
    h,w = map(int, input().split())
    h-=1
    w-=1
    bombs.add((h, w))
    hc[h] += 1
    wc[w] += 1

hmax = max(hc)
wmax = max(wc)

htable = []
for h in range(H):
    if hc[h] == hmax:
        htable.append(h)

wtable = []
for w in range(W):
    if wc[w] == wmax:
        wtable.append(w)

# print(uw, uh)
#print(grid)
#print(wc, uw)
#print(hc, uh)

found = False
for h in htable:
    for w in wtable:
        if (h,w) not in bombs:
            print(hmax + wmax)
            exit(0)

print(hmax + wmax - 1)
### BUGGY CODE ###

s = input()
q = int(input())
X = [list(input().split()) for _ in range(q)]

flag = 0
for x in X:
    if int(x[0]) == 1:
        # s = s[::-1]
        if flag ==0:
            flag = -1
        else:
            flag = 0
        continue
    if int(x[1]) +flag == 1:
        s = ''.join([x[2] ,s])
    else:
        s = ''.join([s ,x[2]])
if flag == -1:
    print(s[::-1])
else:
    print(s)

### FIXED CODE ###

from collections import deque
s = input()
q = int(input())

header = []
footer = []
flag = 0
for i in range(q):
    x = list(input().split())
    if int(x[0]) == 1:
        if flag ==0:
            flag = -1
        else:
            flag = 0
        continue
    if int(x[1]) +flag == 1:
        header.append(x[2])
        # s2 = deque(s)
        # # s.insert(0, x[2])
        # s2.appendleft(x[2])
        # s = list(s2)
    else:
        # s.append(x[2])
        footer.append(x[2])
# ans = ''.join(s)
head = ''.join(reversed(header))
ans = head +s + ''.join(footer)
if flag == -1:
    print(ans[::-1])
else:
    print(ans)
### BUGGY CODE ###

import sys

input = sys.stdin.readline


def main():
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    dp = [float("inf")] * (H + 1)
    dp[0] = 0
    for h in range(H):
        for a, b in zip(A, B):
            next_h = min(H, h+a)
            dp[next_h] = min(dp[next_h], dp[h]+b)
    print(dp[H])


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline

INF = float("inf")


def main():
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    dp = [INF] * (H + max(A))
    dp[0] = 0
    for h in range(H):
        for a, b in zip(A, B):
            if dp[h]+b < dp[h+a]:
                dp[h+a] = dp[h]+b
    ans = min(dp[H:])
    print(ans)


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

A,B,C,D=map(int,input().split())
ans=0
for i in range(A,B+1):
  if i%C!=0 and i%D!=0:
    ans+=1
print(ans)    

### FIXED CODE ###

import fractions
A,B,C,D=map(int,input().split())
listA=range(A)
listB=range(B+1)
listC=range(0,B+1,C)
listAC=range(0,A,C)
listD=range(0,B+1,D)
listAD=range(0,A,D)
listCD=range(0,B+1,C*D//fractions.gcd(C,D))
listACD=range(0,A,C*D//fractions.gcd(C,D))
lenA=len(listA)
lenB=len(listB)
lenC=len(listC)
lenAC=len(listAC)
lenD=len(listD)
lenAD=len(listAD)
lenCD=len(listCD)
lenACD=len(listACD)
ans=lenB-lenA-lenC+lenAC-lenD+lenAD+lenCD-lenACD
print(ans)
### BUGGY CODE ###

def kukan(n, a):
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])
    return dp[0][n - 1]


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


### FIXED CODE ###

def kukan(n, a):
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            L = a[i] - dp[i + 1][j]
            R = a[j] - dp[i][j - 1]
            dp[i][j] = L if L > R else R
    return dp[0][n - 1]


n = int(input())
a = list(map(int, input().split()))
print(kukan(n, a))
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]

bmax = max(A)
bmin = min(A)-N

def getSadNess(b):
    return sum([abs(A[i]-(b+i+1)) for i in range(N)]) 

def binSearch(bmin,bmax):
    b = (bmin+bmax)//2
    sadb = getSadNess(b)
    sadm = getSadNess(b-1)
    sadp = getSadNess(b+1)
    if sadb<=sadp and sadb<=sadm:
        return sadb
    elif sadb>sadm:
        return binSearch(bmin,b-1)
    else:
        return binSearch(b+1,bmax)
    
print(binSearch(bmin,bmax))

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
B = [A[i]-i-1 for i in range(N)]
B.sort()
b = N//2
ans = sum([abs(B[i]-B[b]) for i in range(N)])
print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
l = []
r = []

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

# print("s: " + s)
# print("l: " + str(l))
# print("r: " + str(r))

for i in range(q):
    part = s[l[i]-1:r[i]]
    print(part.count('AC'))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
l = []
r = []
t = [0]*len(s)

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

for i in range(1, len(s)):
    if s[i-1] + s[i] == 'AC':
        t[i] = t[i-1] + 1
    else:
        t[i] = t[i-1]

#print(t)

for i in range(q):
    left = l[i] - 1
    right = r[i] - 1
    # print(left)
    # print(right)
    print(t[right] - t[left])
### BUGGY CODE ###

import numpy as np
N,K= map(int,input().split())
H = np.array(list(map(int, input().split())))

dp = [0] * N

for i in range(1,N):
  s=max(i-K,0)
  dp[i]=np.min(dp[s:i]+np.abs(H[s:i]-H[i]))

print(dp[-1])

### FIXED CODE ###

import numpy as np
N,K= map(int,input().split())
H = np.array(list(map(int, input().split())))

dp = np.zeros(N, dtype=int)

for i in range(1,N):
  s=max(i-K,0)
  dp[i]=np.min(dp[s:i]+np.abs(H[s:i]-H[i]))

print(dp[-1])
### 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])
    
ans = 0
tot = 0
S_ab.sort(reverse=True)
for i in range(len(S_ab)):
    # tot += A[i] - B[i]
    if sum(S_ba) <= tot: break
    tot += S_ab[i]
    ans += 1

if sum(S_ba) > sum(S_ab): print(-1)
else : print(len(S_ba) + 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 ###

N = int(input())
A = list(map(int, input().split()))
count = 1
for i in A:
    count *= i

if 10 ** 18 < count:
    count = -1

print(count)


### FIXED CODE ###

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

if 0 in A:
    print(0)
    exit()

count = 1
for i in A:
    count *= i
    if 10 ** 18 < count:
        break

if 10 ** 18 < count:
    count = -1

print(count)
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    box = []
    for i in range(M):
        LR = [j for j in map(int, input().split())]
        box += LR

    # for i in range(M):
    #     L, R = map(int, input().split())
    #     box.append(L)
    #     box.append(R)

    # print(box)
    num = 0
    for j in range(1, N+1):
        plus = 1
        # print(j)
        if plus == 1:
            for i in range(0, len(box), 2):
                # print(box[i], box[i+1])
                if j < box[i] or box[i+1] < j:
                    plus = 0
                    break

            num += plus

    print(num)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, M = map(int, input().split())

    L = []
    R = []
    for i in range(M):
        l, r = map(int, input().split())
        L.append(l)
        R.append(r)

    Lout = max(L)
    Rout = min(R)
    ans = Rout - Lout+1
    if ans < 0:
        print(0)
    else:
        print(ans)


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

import math
N,K = map(int,input().split())
P=list(map(int,input().split()))


maxnum=0
index=0
num=0
for i in range(len(P)):
    num+=P[i]
    if maxnum<num:
        maxnum=num
        index=i




    if i>=K-1:
        num-=P[i-(K-1)]


List=[]
for i in range(K):
    x1=P[index-i]
    sumx1=sum([j for j in range(1,x1+1)])


    sumx1=sumx1/x1
    List.append(sumx1)


print(sum(List))


### FIXED CODE ###

import math
N,K = map(int,input().split())
P=list(map(int,input().split()))


maxnum=0
index=0
num=0
for i in range(len(P)):
    num+=P[i]
    if maxnum<num:
        maxnum=num
        index=i




    if i>=K-1:
        num-=P[i-(K-1)]


List=[]
for i in range(K):
    x1=P[index-i]

    sumx1=(1+x1)/2
    List.append(sumx1)


print(sum(List))
### BUGGY CODE ###

import sys
# sys.setrecursionlimit(100000)
from collections import defaultdict
from functools import lru_cache


@lru_cache(None)
def gcd(x: int, y: int) -> int:
    if x < y:
        x, y = y, x
    while y > 0:
        r = x % y
        x, y = y, r
    return x


def merge_dict(d1, d2):
    for k, v in d2.items():
        d1[k] += v
    return d1


def input():
    return sys.stdin.readline().strip()


def prime_factorization(N: int) -> dict:
    primes = defaultdict(int)
    primes[1] = 1
    if N < 2:
        return primes
    i = 2
    while i * i <= N:
        while N % i == 0:
            primes[i] += 1
            N = N // i
        i += 1
    if N != 1:
        primes[N] = 1
    return primes


def main():
    n = int(input())
    A = [int(i) for i in input().split()]
    primes = defaultdict(int)
    is_pair_gcd = True
    set_gcd = A[0]
    for i in range(n):
        set_gcd = gcd(set_gcd, A[i])
        p = prime_factorization(A[i])
        if is_pair_gcd:
            for k, v in p.items():
                if k == 1:
                    continue
                if k in primes.keys():
                    is_pair_gcd = False
                else:
                    primes[k] += v

    if is_pair_gcd:
        print("pairwise coprime")
        return

    if set_gcd == 1:
        print("setwise coprime")
    else:
        print("not coprime")

    return


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
# sys.setrecursionlimit(100000)
from collections import defaultdict
from functools import lru_cache


@lru_cache(None)
def gcd(x: int, y: int) -> int:
    if x < y:
        x, y = y, x
    while y > 0:
        r = x % y
        x, y = y, r
    return x


def merge_dict(d1, d2):
    for k, v in d2.items():
        d1[k] += v
    return d1


def input():
    return sys.stdin.readline().strip()


def prime_factorization(N: int) -> dict:
    primes = defaultdict(int)
    primes[1] = 1
    if N < 2:
        return primes
    i = 2
    while i * i <= N:
        while N % i == 0:
            primes[i] += 1
            N = N // i
        i += 1
    if N != 1:
        primes[N] = 1
    return primes


def main():
    n = int(input())
    A = [int(i) for i in input().split()]
    primes = defaultdict(int)
    is_pair_gcd = True
    # pre-process
    for i in range(n):
        p = prime_factorization(A[i])
        for k, v in p.items():
            if k == 1:
                continue
            if k in primes.keys():
                is_pair_gcd = False
                break
            else:
                primes[k] += v
        else:
            continue
        break

    if is_pair_gcd:
        print("pairwise coprime")
        return

    set_gcd = A[0]
    for i in range(1, n):
        set_gcd = gcd(set_gcd, A[i])

    if set_gcd == 1:
        print("setwise coprime")
    else:
        print("not coprime")

    return


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

n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
mod=10**9+7
dp=[[0]*(m+1)for i in range(n+1)]
sum=[[0]*(m+1)for i in range(n+1)]
for i in range(1,n+1):
  for j in range(1,m+1):
    if s[i-1]==t[j-1]: dp[i][j]=sum[i-1][j-1]+1
    sum[i][j] = (sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+dp[i][j]+mod)%mod
ans=1
for d in dp: 
  for x in d: ans+=x
print(ans%mod)

### FIXED CODE ###

n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
mod=10**9+7
dp=[[0]*(m+1)for i in range(n+1)]
sum=[[0]*(m+1)for i in range(n+1)]
for i in range(1,n+1):
  for j in range(1,m+1):
    if s[i-1]==t[j-1]: dp[i][j]=sum[i-1][j-1]+1
    sum[i][j] = (sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+dp[i][j]+mod)%mod
ans=1
for d in dp: 
  for x in d: ans+=x
print(ans%mod)
### BUGGY CODE ###

S = input()
N = len(S)
S = int(S)
T = []
while S > 0:
    T.append(S)
    S = S % (10 ** (N - 1))
    N -= 1
amari = [0 for i in range(2019)]
for i in T:
    amari[i % 2019] += 1
ans = amari[0]
for i in amari:
    ans += i * (i - 1) // 2
print(ans)


### FIXED CODE ###

S = input()[::-1]
N = len(S)
amari = [0 for i in range(2019)]
before = int(S[0])
amari[before] += 1
S = S[1::]
keta = 1
for i in S:
    i = int(i)
    keta = (keta * 10) % 2019
    x = (keta * i + before) % 2019
    amari[x] += 1
    before = x
ans = amari[0]
for i in amari:
    ans += i * (i - 1) // 2
print(ans)
### BUGGY CODE ###

A, B, K = map(int, input().split())
l = [int(x) for x in range(A, B + 1)]
ans = set()
if K > len(l):
	for i in l:
		print(i)
else:
	for i in range(K):
		ans.add(l[i])
	l.reverse()
	for j in range(K):
		ans.add(l[j])
	ans = list(ans)
	ans.sort()
	for k in ans:
		print(k)

### FIXED CODE ###

A, B, K = map(int, input().split())
if 2 * K > B - A + 1:
	for i in range(A, B + 1):
		print(i)
else:
	for i in range(A, A + K):
		print(i)
	for j in range(B - K + 1, B + 1):
		print(j)
### BUGGY CODE ###

import sys
from operator import itemgetter
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
def main():
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while(e[0] > d):
			if cont == True:
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			else:
				mini = min(kouho)
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			cont = True
			if q < Q-1:
				q = q + 1
				d = int(inputs())
			else:
				flag = True
				q = q + 1
				break
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			cont = False
	for t in [None]*(Q-q):
		print(-1)
		
def sub():
	V = [list(map(int,inputs().split())) for p in [0]*N]
	M = [int(inputs()) for p in [0]*Q]
	V.sort(key = lambda x:(x[2],x[0],x[1]))
	for v in V:
		v[0] -= v[2]
		v[1] -= v[2] + 1
	for m in M:
		for n in range(N):
			if V[n][0] <=m and m <= V[n][1]:
				print(V[n][2])
				break
		else:
			print(-1)


if N>200000:
	sub()
else:
	main()

### FIXED CODE ###

import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				print(mini-(mini//1000000001)*1000000002)
			else:
				mini = min(kouho)
				print(mini-(mini//1000000001)*1000000002)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			if mini == e[2]:
				cont = False
	for t in [None]*(Q-q):
		print(-1)
main()