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

import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    way = [[] for i in range(n)]
    for _ in [0]*(n-1):
        a,b = map(int,ipt().split())
        way[a].append(b)
        way[b].append(a)
    rt = -1
    for i in range(n):
        if len(way[i]) > 2:
            rt = i
            break

    def dp(pp,np):
        sum = 0
        n0 = 0
        for i in way[np]:
            if i == pp:
                continue
            tmp = dp(np,i)
            sum += tmp
            if tmp == 0:
                n0 += 1
        if n0 > 1:
            sum += n0-1
        return sum

    if rt == -1:
        print(1)
        exit()
    else:
        print(dp(-1,rt))

    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    way = [[] for i in range(n)]
    for _ in [0]*(n-1):
        a,b = map(int,ipt().split())
        way[a].append(b)
        way[b].append(a)
    rt = -1
    for i in range(n):
        if len(way[i]) > 2:
            rt = i
            break

    def dp(pp,np):
        sum = 0
        n0 = 0
        for i in way[np]:
            if i == pp:
                continue
            tmp = dp(np,i)
            sum += tmp
            if tmp == 0:
                n0 += 1
        if n0 > 1:
            sum += n0-1
        return sum

    if rt == -1:
        print(1)
        exit()
    else:
        print(dp(-1,rt))

    return

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

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

cnt = [0] * 1000
l = len(s)
for i in range(l-2):
    for j in range(i+1, l-1):
        for k in range(j+1, l):
            S = ''.join([s[i], s[j], s[k]])
            cnt[int(S)] += 1

ans = 0
for i in range(len(cnt)):
    if cnt[i] > 0:
        ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())
PIN = []
b1 = []
for i in range(N-2):
    b2 = []
    if S[i] in b1:
        continue
    else:
        b1.append(S[i])
    for j in range(i+1, N-1):
        b3 = []
        if S[j] in b2:
            continue
        else:
            b2.append(S[j])
        for k in range(j+1, N):
            if S[k] in b3:
                continue
            else:
                b3.append(S[k])
            cand = S[i] + S[j] + S[k]
            PIN.append(cand)

print(len(set(PIN)))
### BUGGY CODE ###

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

median=(N//2)-1
for i in range (N):
    X_instant=X[:i] +X[i+1:]
    X_instant.sort()
    print(X_instant[median])

### FIXED CODE ###

N=int(input())
X=list(map(int, input().split()))
 
import copy
X_sort=copy.deepcopy(X)
X_sort.sort()
X_sort
 
median_control=(X_sort[N//2-1]+X_sort[N//2])/2
for i in range (N):
    if X[i]>median_control:
        print (X_sort[N//2-1])
    if X[i]<=median_control:
        print (X_sort[N//2])
### BUGGY CODE ###

K, S = map(int, input().split())

count = 0

x = 0
while (x <= K):
    if x > S:
        break
    y = 0
    while (y <= K):
        if y > S:
            break
        if S - (x + y) <= K and 0 <= S - (x + y):
            count += 1
        y += 1
    x += 1



print(count)

### FIXED CODE ###

K, S = map(int, input().split())

count = 0

x = 0
while (x <= K):
    y = 0
    while (y <= K):
        if 0 <= S - (x + y) <= K:
            count += 1
        y += 1
    x += 1



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

temp=input().split()
L=int(temp[0])
R=int(temp[1])

print(min([(i*j)%2019 for i in range(L, R) for j in range(i+1, R+1)]))

### FIXED CODE ###

temp=input().split()
L=int(temp[0])
R=int(temp[1])

if R-L>=2019:
  print(0)
else:
  print(min([(i*j)%2019 for i in range(L, R) for j in range(i+1, R+1)]))
### BUGGY CODE ###

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

L.sort()
ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        ans += np.count_nonzero((L[j] < L) & (L < L[i] + L[j]))

print(ans)





### FIXED CODE ###

import bisect

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

L.sort()
ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        index = bisect.bisect_right(L, L[i] + L[j]-1)
        ans += index - j - 1

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

#素因数分解、計算量はO(√N)
from collections import defaultdict
def factorize(n):
  b = 2
  dic = defaultdict(lambda: 0)
  while b * b <= n:
    while n % b == 0:
      n //= b
      dic[b] += 1
    b = b + 1
  if n > 1:
    dic[n] += 1
  return dic
N = int(input())
fct = factorize(2*N)
lis = []
for k,v in fct.items():
  lis.append(pow(k,v))
ans = 10**18
from itertools import groupby, accumulate, product, permutations, combinations
for pro in product([0,1],repeat=len(lis)):
  prod1 = 1
  for i,p in enumerate(pro):
    if p==1:
      prod1 *= lis[i]
  prod2 = (N*2)//prod1
  if prod1<prod2:
    prod1,prod2 = prod2,prod1
    # continue
  for i in range(1,prod2+1):
    # if prod1*i>ans:
      # break
    if (prod1*i-1)%prod2==0:
      ans = min(ans, prod1*i-1)
      break
    if (prod1*i+1)%prod2==0:
      ans = min(ans, prod1*i)
      break
print(ans)



### FIXED CODE ###

#素因数分解、計算量はO(√N)
from collections import defaultdict
def factorize(n):
  b = 2
  dic = defaultdict(lambda: 0)
  while b * b <= n:
    while n % b == 0:
      n //= b
      dic[b] += 1
    b = b + 1
  if n > 1:
    dic[n] += 1
  return dic
N = int(input())
fct = factorize(2*N)
lis = []
for k,v in fct.items():
  lis.append(pow(k,v))
ans = 10**18
from itertools import groupby, accumulate, product, permutations, combinations
for pro in product([0,1],repeat=len(lis)):
  if sum(pro)==0:
    continue
  prod1 = 1
  for i,p in enumerate(pro):
    if p==1:
      prod1 *= lis[i]
  prod2 = (N*2)//prod1
  if prod1<prod2:
    prod1,prod2 = prod2,prod1
  
  for i in range(1,prod2+1):
    if prod1*i>ans:
      break
    if (prod1*i-1)%prod2==0:
      ans = min(ans, prod1*i-1)
      break
    if (prod1*i+1)%prod2==0:
      ans = min(ans, prod1*i)
      break

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

H, W = map(int, input().split())

ans = 0
for i in range(H):
    for j in range(W):
        if (i+j) % 2 == 0:
            ans += 1

print(ans)



### FIXED CODE ###

import math

H, W = map(int, input().split())

if H == 1 or W == 1:
    print(1)
else:
    o = math.ceil(W/2)
    e = W//2

    if H % 2 == 0:
        print((o+e)*(H//2))
    else:
        print((o+e)*(H//2) + o)
### BUGGY CODE ###


k = int(input())


def lunlunfinder(k):
    l = [int(x) for x in list(str(k))]
    status = 0
    for i in range(len(l) - 1):
        if abs(l[i] - l[i + 1])  <= 1:
            continue
        else:
            status = 1
            break

    if status == 1:
        return False
    else:
        return True


lunlunlist = []
i = 1

while len(lunlunlist) < k:
    if lunlunfinder(i) == True:
        lunlunlist.append(i)
    i += 1

print(lunlunlist[k - 1])

### FIXED CODE ###

def last_number(n):
    if n == 0:
        return [0, 1]
    elif n == 9:
        return [8, 9]
    else:
        return [n-1, n, n+1]

k = int(input())
lun = {1, 2, 3, 4, 5, 6, 7, 8, 9}
temp = set()
while len(lun) < k:
    for i in lun:
        last = int(str(i)[-1])
        for j in last_number(last):
            temp.add(int(str(i) + str(j)))
    lun.update(temp)
    temp = set()
answer = sorted(list(lun))
print(answer[k - 1])
### BUGGY CODE ###

from heapq import heappush, heappop
import heapq
import sys
sys.setrecursionlimit(10 ** 7)

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

event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x,1,x))
    event.append((t-x,-1,x))

for i in range(q):
    event.append((int(input()),2,i))
event.sort()

ans=[0]*q

stop=set()
hq=[]
for t,op,x in event:
    if op==1:
        heappush(hq,x)
        stop.add(x)
    elif op==-1:
        stop.remove(x)

    else:
        while hq and hq[0] not in stop:
            heappop(hq) 
        ans[x]=hq[0] if hq else -1
    
for x in ans:
    print(x)

### FIXED CODE ###

def main():
    from heapq import heappush, heappop
    import sys
    sys.setrecursionlimit(10 ** 7)

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

    event=[]
    for _ in range(n):
        s,t,x=map(int,input().split())
        event.append((s-x,1,x))
        event.append((t-x,-1,x))

    for i in range(q):
        event.append((int(input()),2,i))
    event.sort()

    ans=[0]*q

    stop=set()
    hq=[]
    for t,op,x in event:
        if op==1:
            heappush(hq,x)
            stop.add(x)
        elif op==-1:
            stop.remove(x)

        else:
            while hq and hq[0] not in stop:
                heappop(hq) 
            ans[x]=hq[0] if hq else -1
        
    for x in ans:
        print(x)

main()
### BUGGY CODE ###

N = int(input())
words_list = []
for i in range(N):
  ss = input()
  ss_dict = {}
  for s in ss:
    ss_dict.setdefault(s, 0)
    ss_dict[s] += 1
  ss_dict = sorted(ss_dict.items())
  ss = [str(k)+str(v) for (k, v) in ss_dict]
  words_list.append(''.join(ss))
count = 0
for i in range(len(words_list)):
  for j in range(i+1, len(words_list)):
    if words_list[i] == words_list[j]:
      count += 1
print(count)

### FIXED CODE ###

N = int(input())
words_dict = {}
count = 0
for i in range(N):
  ss = input()
  ss = "".join(sorted(ss))
  words_dict.setdefault(ss, 0)
  count += words_dict[ss]
  words_dict[ss] += 1
print(count)
### BUGGY CODE ###

k=int(input())
ans=0
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = gcd(a,l[i])
    return a
sumlis={}
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            lis=sorted([a,b,c])
            if lis in sumlis.values(): 
                ans+=sumlis[lis]
            else:
                x=gcdlist(lis)
                sumlis[x]=sumlis
                ans+=x
                
print(ans)

### FIXED CODE ###

k=int(input())
ans=0
import math
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = gcd(a,l[i])
    return a

sumlis={}
for a in range(1,k+1):
    for b in range(1,k+1):
        t=math.gcd(a,b)
        for c in range(1,k+1):
            ans+=math.gcd(t,c)
                
print(ans)
### BUGGY CODE ###

n = int(input())
p_lst = [e for e in range(1,n+1)]
lst = [p_lst[-1]] + p_lst[0:-1]
res = 0
for i, e in enumerate(lst):
  r = e%(i+1)
  res += r
print(res)

### FIXED CODE ###

n = int(input())
first, last = 1, n-1
res = (n-1)*n//2
print(int(res))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
hL = list(map(int, input().split()))

for i in range(n):
    if hL[i] - min(hL[i:n])==1:
        hL[i]-=1
if hL ==sorted(hL):
    print('Yes')
else:
    print('No')

### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline
n = int(input())

L = np.array(list(map(int, input().split())))

for i in range(n-1, 0, -1):
    if L[i]-L[i-1] ==-1:
        L[i-1] -=1

if np.all(L ==sorted(L)):
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

S=input()
T=input()
memo = [[0]*(len(T)+1) for _ in range(len(S)+1)]

for i in range(1, len(S)+1):
    for j in range(1, len(T)+1):
        if S[i-1] == T[j-1]:
            memo[i][j] = memo[i-1][j-1] + 1
        else:
            memo[i][j] = max(memo[i-1][j], memo[i][j-1])
 
ans = ''
i = len(S)
j = len(T)
while i > 0 and j > 0:
    if memo[i][j] == memo[i-1][j]:
        i-=1
    elif memo[i][j] == memo[i][j-1]:
        j-=1
    else:
        i-=1
        j-=1
        ans = ans + S[i]

ans = ''.join(reversed(ans))
print(ans)

### FIXED CODE ###

S=input()
T=input()
memo = [[0]*(len(T)+1) for _ in range(len(S)+1)]

for i in range(1, len(S)+1):
    for j in range(1, len(T)+1):
        if S[i-1] == T[j-1]:
            memo[i][j] = memo[i-1][j-1] + 1
        else:
            memo[i][j] = max(memo[i-1][j], memo[i][j-1])
 
ans = ''
i = len(S)
j = len(T)
while i > 0 and j > 0:
    if memo[i][j] == memo[i-1][j]:
        i-=1
    elif memo[i][j] == memo[i][j-1]:
        j-=1
    else:
        i-=1
        j-=1
        ans = ans + S[i]

ans = ''.join(reversed(ans))
print(ans)
### BUGGY CODE ###

s = input()
t = input()

ls, lt = len(s), len(t)

dp = [[0]*(lt+1) for _ in range(ls+1)]
for i in range(1, ls+1):
    for j in range(1, lt+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1)
        dp[i][j] = max(dp[i][j], dp[i][j-1])
        dp[i][j] = max(dp[i][j], dp[i-1][j])

ans = ''
while ls > 0 and lt > 0:
    if dp[ls][lt] == dp[ls-1][lt]:
        ls -= 1
    elif dp[ls][lt] == dp[ls][lt-1]:
        lt -= 1
    else:
        ans = t[lt-1] + ans
        ls -= 1
        lt -= 1

print(ans)


### FIXED CODE ###

s = input()
t = input()

ls, lt = len(s), len(t)

dp = [[0]*(lt+1) for _ in range(ls+1)]
for i in range(1, ls+1):
    for j in range(1, lt+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1)
        dp[i][j] = max(dp[i][j], dp[i][j-1])
        dp[i][j] = max(dp[i][j], dp[i-1][j])

ans = ''
while ls > 0 and lt > 0:
    if dp[ls][lt] == dp[ls-1][lt]:
        ls -= 1
    elif dp[ls][lt] == dp[ls][lt-1]:
        lt -= 1
    else:
        ans = t[lt-1] + ans
        ls -= 1
        lt -= 1

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

n, total = map(int, input().split(" "))

x = -1
y = -1
z = -1

num_max_10k = total // 10000
num_max_5k = total // 5000
num_max_1k = total // 1000

for num_10k in range (num_max_10k + 1):
    sum_10k = num_10k * 10000
    for num_5k in range(num_max_5k + 1):
        sum_5k = num_5k * 5000
        if (num_10k + num_5k >= n):
            num_1k = 0
        else:
            num_1k = n - (num_10k + num_5k)
        sum_1k = num_1k * 1000

        #print(num_10k, num_5k, num_1k, sep=" ")
        if (total == (sum_10k + sum_5k + sum_1k)
            and n == (num_10k + num_5k + num_1k)):
            x, y, z = num_10k, num_5k, num_1k
            break
    else:
        continue
    break

print(x, y, z, sep=" ")


### FIXED CODE ###

n, total = map(int, input().split(" "))

x = -1
y = -1
z = -1

for x_tmp in range(0, n + 1):
    for y_tmp in range(0, (n - x_tmp) + 1):
        z_tmp = n - (x_tmp + y_tmp) if n >= (x_tmp + y_tmp) else 0
        if total == (x_tmp * 10000 + y_tmp * 5000 + z_tmp * 1000):
            x, y, z = x_tmp, y_tmp, z_tmp

print(x, y, z, sep = " ")
### BUGGY CODE ###

s,_,*q=open(0)
a=s[:-1]
p=1
for q in q:
  try:
    q,f,c=q.split()
    if(f<'2')^p:a+=c
    else:a=c+a
  except:p^=1
print(a[::p or-1])

### FIXED CODE ###

from collections import*
s,_,*q=open(0)
d=deque(s[:-1])
p=1
for q in q:
  try:
    q,f,c=q.split()
    if(f<'2')^p:d+=c,
    else:d.appendleft(c)
  except:p^=1
print(''.join(d)[::p or-1])
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
use = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
usecase = [use[i] for i in a]

dp = [""] * (n+1)
for i in range(1,n+1):
    kouho = []
    for j in a:
        if i - use[j] >= 0:
            if dp[i-use[j]] == "" and i - use[j] != 0: # マッチの数が合わない場合
                continue #何もしない
            else:
                for k in range(len(dp[i-use[j]])+1):
                    kouho.append(dp[i-use[j]][:k]+str(j)+dp[i-use[j]][k:])
    if kouho == []: #空の場合
        continue #何もしない
    else:
        dp[i] = str(max(map(int,kouho)))
print(dp[n])

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
use = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [[0] * 10 for i in range(n+1)]
for i in range(1,n+1):
    for j in a:
        if i - use[j] >= 0:
            if dp[i-use[j]] == [0] * 10 and i - use[j] != 0: # マッチの数が合わない場合
                continue #何もしない
            else:
                if sum(dp[i-use[j]])+1 >= sum(dp[i]):
                    copy = dp[i-use[j]][:]
                    copy[j] += 1
                    dp[i] = copy
ans = ""
for i in range(9,0,-1):
    ans += (str(i) * dp[n][i])
print(ans)
### BUGGY CODE ###

N = int(input())
p = list(map(int,input().split()))
ppp = [0]*N
for i in range(N):
    if i == p[i] - 1:
        ppp[i] = 1
cnt = 0
while True:
    if 1 not in ppp:
        print(cnt)
        exit()
    a = ppp.index(1)
    if a == len(ppp) - 1:
        ppp[a] = 0
    elif ppp[a+1] == 1:
        ppp[a],ppp[a+1] = 0,0
    else:
        ppp[a] = 0
    cnt += 1

### FIXED CODE ###

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

ans = 0
for i in range(1,N+1):
    if i == p[i-1]:
        ans += 1

k = 0
for i in range(1,N):
    i += k
    if i >= N:
        break
    if i == p[i-1] and i+1 == p[i]:
        ans -= 1
        k += 1
print(ans)
### BUGGY CODE ###

Q = 998244353
N = int( input())
A = [ int( input()) for _ in range(N)]
S = sum(A)
H = (S+1)//2
dp = [0]*(S+1)
dp[0] = 1
for a in A:
    for s in range(S, a-1, -1):
        dp[s] = (dp[s]*2 + dp[s-a])%Q
    for s in range(a-1,-1,-1):
        dp[s] = dp[s]*2%Q
ans = (pow(3, N, Q) - sum(dp[H:])%Q*3%Q)%Q
if S%2 == 0:
    dp = [0]*(S+1)
    dp[0] = 1
    for a in A:
        for s in range(S,a-1,-1):
            dp[s] = (dp[s] + dp[s-a])%Q
    ans += dp[H]*3
    ans %= Q
print(ans)

### FIXED CODE ###

Q = 998244353
N = int( input())
A = [ int( input()) for _ in range(N)]
S = sum(A)
H = (S+1)//2
dp = [0]*(S+1)
dp[0] = 1
for a in A:
    for s in range(S, a-1, -1):
        dp[s] = (dp[s]*2 + dp[s-a])%Q
    for s in range(a-1,-1,-1):
        dp[s] = dp[s]*2%Q
ans = (pow(3, N, Q) - sum(dp[H:])%Q*3%Q)%Q
if S%2 == 0:
    dp = [0]*(S+1)
    dp[0] = 1
    for a in A:
        for s in range(S,a-1,-1):
            dp[s] = (dp[s] + dp[s-a])%Q
    ans += dp[H]*3
    ans %= Q
print(ans)
### BUGGY CODE ###

n, w = map(int, input().split())
l1 = [list(map(int, input().split())) for i in range(n)]
v = 0
for i in range(n):
  v += l1[i][1]
d = [10 ** 9 + 1] * (v + 1)
d[0] = 0
for i in range(n):
    for j in range(v, -1, -1):
        d[j] = min(d[j], d[j - l1[i][1]] + l1[i][0])
answer = 0
for j in range(v + 1):
    if  w >= d[j]:
        answer = max(answer, j)
print(answer)

### FIXED CODE ###

n, w = map(int, input().split())
l1 = [list(map(int, input().split())) for i in range(n)]
v = 0
for i in range(n):
  v += l1[i][1]
d = [10 ** 9 + 1] * (v + 1)
d[0] = 0
for i in range(n):
    for j in range(v, -1, -1):
        d[j] = min(d[j], d[j - l1[i][1]] + l1[i][0])
answer = 0
for j in range(v + 1):
    if  w >= d[j]:
        answer = max(answer, j)
print(answer)
### BUGGY CODE ###

N = int(input())

pre = list(map(int,input().split()))

ans = 1

for i in range (N):
    ans *= pre[i]



if ans > 1000000000000000000:
    print("-1")

else:
    print(ans)

### FIXED CODE ###

N = int(input())

pre = list(map(int,input().split()))

flag = 0

for i in range (N):
    if pre[i] == 0:
        flag = 1

if flag == 0:

    ans = 1

    for i in range (N):
        ans *= pre[i]

        if ans > 10**18:
            print("-1")
            break

    if ans <= 10**18:
        print(ans)

else:
    print("0")
### BUGGY CODE ###

import numpy as np

n = int(input())
a = np.array(list(map(int, input().split())), dtype=np.int32)
b = np.array(list(map(int, input().split())), dtype=np.int32)

ans = 0
mod = 1
for k in range(30):
    mod *= 2
    t = mod // 2
    cnt = 0
    bb = np.sort(b % mod)
    for e in a:
        e %= mod
        for i in range(2):
            l = (2 * i + 1) * t - e
            r = (2 * i + 2) * t - e
            il = np.searchsorted(bb, l)
            ir = np.searchsorted(bb, r)
            cnt += ir - il

    if cnt % 2:
        ans += t

print(ans)


### FIXED CODE ###

import numpy as np

n = int(input())
a = np.array(list(map(int, input().split())), dtype=np.int32)
b = np.array(list(map(int, input().split())), dtype=np.int32)

ans = 0
mod = 1
for k in range(30):
    mod *= 2
    t = mod // 2
    cnt = 0
    bb = np.sort(b % mod)
    aa = a % mod
    l1, r1, l2, r2 = (np.searchsorted(bb, v - aa).sum() for v in (t, 2*t, 3*t, 4*t))
    cnt += r1 - l1
    cnt += r2 - l2

    if cnt % 2:
        ans += t

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

import sys
import bisect

input = sys.stdin.readline

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

STX = [list(map(int, input().split())) for _ in range(N)]
# xの昇順に工事の区間をsort
STX = sorted(STX, key=lambda x: x[2])

D = [int(input()) for _ in range(Q)]
ans = [-1 for _ in range(Q)]
for s, t, x in STX:
    left = bisect.bisect_left(D, s - x - 0.5)
    right = bisect.bisect_left(D, t - x - 0.5)
    
    for i in range(left, right):
        if ans[i] == -1:
            ans[i] = x

for a in ans:
    print(a)

### FIXED CODE ###

import sys
import bisect

input = sys.stdin.readline

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

STX = [list(map(int, input().split())) for _ in range(N)]
# xの昇順に工事の区間をsort
STX = sorted(STX, key=lambda x: x[2])

D = [int(input()) for _ in range(Q)]
ans = [-1] * Q
index = [-1] * Q
for s, t, x in STX:
    left = bisect.bisect_left(D, s - x - 0.5)
    right = bisect.bisect_left(D, t - x - 0.5)
    now = left
    while now < right:
        if index[now] == -1:  # まだansが更新されていない場合
            ans[now] = x
            index[now] = right
            now += 1
        else:
            now = index[now]
            

for a in ans:
    print(a)
### BUGGY CODE ###

MOD = 1000000007

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

result = 0

for i in range(N):

    for j in range(N-i-1):
        result += n_list[i] * n_list[j+i+1] % MOD
        result = result % MOD

print(result)


### FIXED CODE ###


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

result = 0

s = sum(n_list)
m = 10**9+7

for num in n_list:
    s -= num
    result += num * s % m
    result %= m

print(result)
### BUGGY CODE ###

import  collections
import numpy as np

s = input().strip()
t = []
for i in range(len(s)):
    t.append(int(s[i:]) % 2019) 
    
t.append(0)
counts = dict(collections.Counter(t))
counts = np.array(list(counts.values()))
print(int(np.sum(counts * (counts -1) /2)))


### FIXED CODE ###

import numpy as np

s = input().strip()
t = 0
counts = np.array([0] * 2019)
counts[0] += 1
m = 1

for a  in reversed(s):
    t = (t + m * int(a)) % 2019
    counts[t] += 1
    m = m * 10 % 2019
    
print(int(np.sum(counts * (counts - 1) /2)))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
Ans = 0
for i in range(N-1):
    Ans += A[N-i-1]*sum(A[:N-i-1])

print(Ans%((10**9)+7))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Ans = 0
S = sum(A)

for i in range(N-1):
    S -= A[N-i-1]
    Ans += A[N-i-1]*S

print(Ans%((10**9)+7))