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

import sys
sys.setrecursionlimit(10**7)
n, q = map(int, input().split(' '))
inf = [[] for _ in range(n+1)]
ab = [[x for x in map(int, input().split(' '))] for _ in range(n-1)]
for a,b in ab:
    inf[a].append(b)
    inf[b].append(a)
point = [0 for _ in range(n+1)]
px = [[x for x in map(int, input().split(' '))] for _ in range(q)]
for p,x in px:
    point[p] += x
def add_p(num, oya):
    for k in inf[num]:
        if k != oya:
            point[k] += point[num]
            add_p(k, num)  
for i in inf[1]:
    point[i] += point[1]
    add_p(i,1)
point.pop(0)
print(*point)

### FIXED CODE ###

def main():
    n, q = map(int, input().split(' '))
    import sys
    from collections import deque
    sys.setrecursionlimit(10**7)

    visit = [True for _ in range(n)]
    point = [0 for _ in range(n)]
    dic = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split(' '))
        dic[a-1].append(b-1)
        dic[b-1].append(a-1)
    for _ in range(q):
        p, x = map(int, input().split(' '))
        point[p-1] += x
    next_visit = deque()
    next_visit.append(0)
    visit[0] = False
    counter = 1
    while counter < n:
        t = next_visit.pop()
        for s in dic[t]:
            if visit[s]:
                point[s] += point[t]
                visit[s] = False
                counter += 1
                next_visit.append(s)
    print(*point)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

lst = []
for i in range(N):
    flag = False
    for j in range(len(lst)):
        if lst[j] < A[i]:
            lst[j] = A[i]
            lst.sort(reverse = True)
            flag = True
            break
    if flag == False:
        lst.append(A[i])
        lst.sort(reverse = True)

print (len(lst))

### FIXED CODE ###

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

dp = [-A[0]]
def solve():
    import bisect
    for i in range(1, N):
        a = bisect.bisect_left(dp, -A[i]+0.1) #入れるべき場所
        # print (a)
        if a == len(dp):
            dp.append(-A[i])
        else:
            dp[a] = -A[i]
        # print (dp)
    return len(dp)


print (solve())
### BUGGY CODE ###

def is_even(n):
    return n & 1 == 0

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


count = 0
while True:
    maxidx = 0
    maxval = 0
    even_flag = False
    for i, v in enumerate(a):
        if is_even(v):
            even_flag = True
            if maxval < v:
                maxval = v
                maxidx = i
        a[i] *= 3

    if not even_flag:
        break

    a[maxidx] = int(a[maxidx] / 6)
    count += 1

print(count)


### FIXED CODE ###

def is_even(n):
    return n & 1 == 0

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


count = 0
for v in a:
    while is_even(v):
        v = int(v / 2)
        count += 1

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

N, M = map(int,input().split())
A = list(map(int,input().split()))
change = [list(map(int,input().split())) for i in range(M)]
A.sort()
for i in range(M):
    for j in range(change[i][0]):
        while  A[j] < change[i][1]:
            A[j] = change[i][1]
    A.sort()

ans = 0
for a in A:
    ans += a
print(ans)

### FIXED CODE ###

N, M = map(int,input().split())
A = list(map(int,input().split()))
B = [list(map(int,input().split())) for i in range(M)]
A.sort()
B.sort(reverse=True, key=lambda x: x[1])

cot = 0
add = 0
for b,c in B:
    cot += b
    if cot > N:
        add = N-cot+b
        A.extend([c]*add)
        break
    else:
        A.extend([c]*b)
print(sum(sorted(A, reverse=True)[:N]))
### BUGGY CODE ###

n,m,q = map(int,input().split())
query = [[0 for j in range(501)] for i in range(501)]
for h in range(m):
    k,l = map(int,input().split())
    query[k][l] += 1

def search(l,r):
    ans = 0
    for i in range(l,r+1):
        for j in range(l,r+1):
            ans += query[i][j]
    return ans

for h in range(q):
    k,l = map(int,input().split())
    print(search(k,l))

### FIXED CODE ###

n,m,q = map(int,input().split())
query = [[0 for j in range(501)] for i in range(501)]

for h in range(m):
    k,l = map(int,input().split())
    query[k][l] += 1

#リストを累積和にする
for i in range(501):
    for j in range(501):
        if j == 0:
            continue
        query[i][j] = query[i][j] + query[i][j-1]
for i in range(501):
    for j in range(501):
        if j == 0:
            continue
        query[i][j] = query[i][j] + query[i-1][j]
        

for h in range(q):
    k,l = map(int,input().split())
    A,B,C = 0,0,0
    if k > 1:
        A = query[k-1][l]
        B = query[l][k-1]
        C = query[k-1][k-1]
    print(query[l][l] - A - B + C)
### BUGGY CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

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

lis = {}
flg1 = True
flg2 = True

for i in range(n):
  temp =  make_divisors(a[i])
  for j in temp:
    if j == 1:
      continue
    if not  j in lis:
      lis[j]=1
    else:
      flg1 = False
      lis[j]+=1
      if lis[j]==n:
        flg2 = False
      
if flg1:
  print("pairwise coprime")
elif flg2:
  print("setwise coprime")
else:
  print("not coprime")

### FIXED CODE ###

from math import gcd
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return set(a)
  
n = int(input())
a = list(map(int, input().split()))
dic = {}
g = a[0]
flg = True
for i in range(n):
  g = gcd(g, a[i])
  if flg:
    tmp = prime_factorize(a[i])
    for j in tmp:
      if j in dic:
        flg = False
      else:
        dic[j]=1
        
if flg:
  print("pairwise coprime")
elif g == 1:
  print("setwise coprime")
else:
  print("not coprime")
### BUGGY CODE ###

Q = int(input())
queries = []
for _ in range(Q):
    queries.append(input())

from bisect import insort_left

ary, bsum, c = [], 0, 0
for query in queries:
    if query[0] == '2':
        absum = sum(abs(a - ary[(c-1)//2]) for a in ary)
        print(' '.join(map(str, (ary[(c-1)//2], absum + bsum))))
    else:
        _, a, b = map(int, query.split())
        insort_left(ary, a)
        bsum += b
        c += 1


### FIXED CODE ###

Q = int(input())
INF = 10 ** 9

queries = []
for _ in range(Q):
    queries.append(input())

from bisect import insort_left
from heapq import heappush, heappop

absum, bsum, c = 0, 0, 0
# left, right = -INF, INF
lefts, rights = [INF], [INF]
for query in queries:
    if query[0] == '2':
        # absum = sum(abs(a - ary[(c-1)//2]) for a in ary)
        # absum = asum - (c//2 + 1) * ary[(c-1)//2]
        # print(' '.join(map(str, (ary[(c-1)//2], absum + bsum))))
        # print(str(ary[(c-1)//2]) + ' ' + str(absum + bsum))
        print(-lefts[0], absum + bsum)
    else:
        _, a, b = map(int, query.split())
        if c % 2 == 0:
            if -lefts[0] <= a <= rights[0]:
                heappush(lefts, -a)
                heappush(rights, a)
                absum += 0
            elif a < -lefts[0]:
                heappush(lefts, -a)
                heappush(rights, -lefts[0])
                absum += -lefts[0] - a
            else:
                heappush(rights, a)
                heappush(lefts, -rights[0])
                absum += a - rights[0]
        else:
            if a < -lefts[0]:
                absum += -lefts[0] - a
                heappop(lefts)
                heappush(lefts, -a)
            else:
                absum += a - rights[0]
                heappop(rights)
                heappush(rights, a)
        # left, right = ary[(c-1)//2], ary[c - (c-1)//2 - 1]        
        bsum += b
        c += 1
### BUGGY CODE ###

INF = float('inf')

H, W = map(int, input().split())
Sss = ['#'*(W+2)] + ['#'+input()+'#' for _ in range(H)] + ['#'*(W+2)]

def convGrid2Graph(Sss):
    dxys = [(-1,0), (1,0), (0,-1), (0,1)]
    sizeX, sizeY = len(Sss)-2, len(Sss[0])-2

    numV = sizeX * sizeY
    adjL = [[] for _ in range(numV)]
    for x in range(1, sizeX+1):
        for y in range(1, sizeY+1):
            if Sss[x][y] != '.': continue
            z = (x-1)*sizeY + (y-1)
            for dx, dy in dxys:
                x2, y2 = x+dx, y+dy
                if Sss[x2][y2] != '.': continue
                z2 = (x2-1)*sizeY + (y2-1)
                adjL[z].append(z2)
    return adjL

def WarshallFloyd(adjList, INF):
    numV = len(adjList)
    D = [[INF]*numV for _ in range(numV)]
    for u, adj in enumerate(adjList):
        for v in adj:
            D[u][v] = 1
        D[u][u] = 0
    for k in range(numV):
        Dk = D[k]
        for i in range(numV):
            Di = D[i]
            Dik = Di[k]
            for j in range(numV):
                D2 = Dik + Dk[j]
                if D2 < Di[j]:
                    D[i][j] = D2
    return D

adjL = convGrid2Graph(Sss)

distss = WarshallFloyd(adjL, INF)

ans = 0
for i in range(H*W):
    for j in range(H*W):
        if distss[i][j] != INF:
            ans = max(ans, distss[i][j])

print(ans)


### FIXED CODE ###

dxys = [(-1,0), (1,0), (0,-1), (0,1)]

H, W = map(int, input().split())
Sss = ['#'*(W+2)] + ['#'+input()+'#' for _ in range(H)] + ['#'*(W+2)]

N = H*W
adjL = [[] for _ in range(N)]
for x in range(1, H+1):
    for y in range(1, W+1):
        if Sss[x][y] != '.': continue
        for dx, dy in dxys:
            x2, y2 = x+dx, y+dy
            if Sss[x2][y2] != '.': continue
            z = (x-1)*W + y-1
            z2 = (x2-1)*W + y2-1
            adjL[z].append(z2)

# 重みなしグラフの直径を求める
def getDiameterOfUnweightedGraph(adjList):
    numV = len(adjList)
    def bfs(vSt):
        costs = [-1] * numV
        costs[vSt] = cost = 0
        vs = [vSt]
        while vs:
            cost += 1
            v2s = []
            for v in vs:
                for v2 in adjList[v]:
                    if costs[v2] == -1:
                        costs[v2] = cost
                        v2s.append(v2)
            vs = v2s
        return cost - 1
    return max([bfs(vSt) for vSt in range(numV)])

maxDist = getDiameterOfUnweightedGraph(adjL)
print(maxDist)
### BUGGY CODE ###

N, M = (int(d) for d in input().split())

C = [[] for i in range(N+1)]
for i in range(M):
    A, B = (int(d) for d in input().split())
    C[A].append(B)
    C[B].append(A)

# BFS
Q = []
ungrouped = [i for i in range(1, N+1)]
G = []

while len(ungrouped) > 0:
    init = ungrouped.pop(0)
    Q += C[init]
    G.append([])
    G[-1].append(init)

    while len(Q) > 0:
        I = Q.pop(0)
        if I in ungrouped:
            Q += C[I]
            G[-1].append(I)
            ungrouped.remove(I)

print(max([len(g) for g in G]))


### FIXED CODE ###

N, M = (int(d) for d in input().split())

C = [set() for i in range(N+1)]
for i in range(M):
    A, B = (int(d) for d in input().split())
    C[A].update([B])
    C[B].update([A])

# BFS
seen = set()
G = []

for i in range(1, N+1):
    if i in seen:
        continue

    # create new group
    G.append(set())

    # create queue
    Q = [i]
    G[-1].update(Q)
    seen.update(Q)

    while len(Q) > 0:
        # queue is not empty

        I = Q.pop(0)
        J = C[I].difference(seen)
        Q += list(J)
        G[-1].update(J)

        seen.update(J)

print(max([len(g) for g in G]))
### BUGGY CODE ###

n = int(input())
butnum = {}
for i in range(1,n+1):
    butnum[i] = int(input())
pushbut = 1
pushedbut =[]
for j in range(1,n+1):
    pushedbut.append(pushbut)
    pushbut = butnum[pushbut]
    if pushbut == 2:
        print(j)
        break
    elif pushbut in pushedbut:
        print(-1)
        break

### FIXED CODE ###

n = int(input())
butnum = {}
for i in range(1,n+1):
    butnum[i] = int(input())
pushbut = 1
pushedbut =[]
jud = 0
for j in range(1,n+1):
    pushbut = butnum[pushbut]
    if pushbut == 2:
        print(j)
        jud = 1
        break
if jud == 0:
    print(-1)
### BUGGY CODE ###

import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
X = list(map(int, sys.stdin.readline().split()))
L = int(sys.stdin.readline())
Q = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

N += 2
X = [X[0]] + X + [X[-1]]
X = np.array(X, dtype=int)
# dp[d][i]: i番のホテルから(2^d)日で何個右までいけるか
dp = np.zeros((N.bit_length() + 1, N), dtype=int)
dp[0] = np.searchsorted(X, X + L, side='right') - np.arange(N) - 1
for d in range(1, N.bit_length() + 1):
    dp[d] = dp[d - 1] + dp[d - 1][np.arange(N) + dp[d - 1]]


def solve(l, r):
    ret = 0
    while l < r:
        d = max(0, np.searchsorted(dp[:, l], r - l) - 1)
        ret += 2 ** d
        l += dp[d, l]
    return ret


for a, b in AB:
    r = solve(min(a, b), max(a, b))
    print(r)


### FIXED CODE ###

import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
X = list(map(int, sys.stdin.readline().split()))
L = int(sys.stdin.readline())
Q = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

N += 2
X = [X[0]] + X + [X[-1]]
X = np.array(X, dtype=int)
# dp[d][i]: i番のホテルから(2^d)日で何個右までいけるか
dp = np.zeros((N.bit_length() + 1, N), dtype=int)
dp[0] = np.searchsorted(X, X + L, side="right") - 1
for d in range(1, N.bit_length() + 1):
    dp[d] = dp[d - 1][dp[d - 1]]
dp = dp.tolist()


def solve(l, r):
    ret = 0
    d = len(dp) - 1
    while l + 1 < r:
        while d > 0 and dp[d][l] >= r:
            d -= 1
        ret += 1 << d
        l = dp[d][l]
    if l < r:
        ret += 1
    return ret


ans = []
for a, b in AB:
    ans.append(solve(min(a, b), max(a, b)))
print(*ans, sep='\n')
### BUGGY CODE ###

N = int(input())

a = []
for i in range(N):
    x = int(input())
    if x in a:
        a.remove(x)
    else:
        a.append(x)
print(len(a))


### FIXED CODE ###

N = int(input())

a = {}
for i in range(N):
    x = input()
    if x in a:
        del a[x]
    else:
        a[x] = 0
print(len(a))
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def solve():
    N,M = map(int,input().strip().split())
    ans = [0]*(N+1)
    g = dict()
    for i in range(M):
      ai,bi = map(int,input().strip().split())
      if ai in g:
        g[ai].append(bi)
      else:
        g[ai] = [bi]
      if bi in g:
        g[bi].append(ai)
      else:
        g[bi] = [ai]

    Q = int(input())
    for i in range(Q):
      v,d,c = map(int,input().strip().split())
      ans[v]=c
      done={v}
      queue = set(g.get(v,list()))
      for j in range(d):
        n_queue = set()
        for idx in queue:
          ans[idx]=c
          done.add(idx)
          for k in g.get(idx,list()):
            if k not in done:
              n_queue.add(k)
        queue = n_queue
    for i in range(N):
      print(ans[i+1])


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
input = sys.stdin.readline

INF = 10**14

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

maxd = 0
Q = int(input())
Query = []
Color = []
for _ in range(Q):
    v, d, c = map(int, input().split())
    if d > maxd:
        maxd = d
    Query.append((v-1, d))
    Color.append(c)

Query = Query[::-1]
Color = Color[::-1]

dp = [[INF]*(maxd+1) for _ in range(N)]
for i, (v, d) in enumerate(Query):
    if i < dp[v][d]:
        dp[v][d] = i

for d in reversed(range(maxd)):
    for v in range(N):
        if dp[v][d+1] < dp[v][d]:
            dp[v][d] = dp[v][d+1]
        for nv in graph[v]:
            if dp[v][d+1] < dp[nv][d]:
                dp[nv][d] = dp[v][d+1]

for v in range(N):
    seq = dp[v][0]
    if seq == INF:
        print(0)
    else:
        print(Color[seq])
### BUGGY CODE ###

from collections import deque
qs = []
n, q = map(int, input().split())
s = input()
for i in range(q):
    qs.append(list(map(int, input().split())))
for i in range(q):
    que = deque(maxlen = 2)
    cnt = 0
    l = qs[i][0]
    r = qs[i][1]
    for a in s[l-1: r]:
        que.append(a)
        if que == deque(['A', 'C']):
            cnt += 1
    print(cnt)
        

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
qs = [list(map(int, input().split())) for i in range(Q)]
t =[0] * N
for i in range(N-1):
    t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0)
def ans(l, r):
    return t[r-1] - t[l-1]
for l, r in qs:
    print(ans(l,r))
### BUGGY CODE ###

import copy
N = int(input())
nums = [int(input()) for _ in range(N)]
for i in range(len(nums)):
  nums_del = copy.deepcopy(nums)
  del nums_del[i]
  print(max(nums_del))

### FIXED CODE ###

import numpy as np
N = int(input())
nums = [int(input()) for _ in range(N)]
nums = np.array(nums)
max_num = max(nums)
max_index = np.where(nums == nums.max())[0]

if len(max_index) == 1:
  for i in range(len(nums)):
    if i == max_index[0]:
      print(sorted(nums)[-2])
    else:
      print(max_num)
else:
  for i in range(len(nums)):
    print(max_num)
### BUGGY CODE ###

n = int(input())
a_ls = list(map(int, input().split()))
ans = 0
for i in range(n):
    for j in range(i+1,n):
        target_ind = j
        target_h = a_ls[target_ind]
        diff = abs(target_ind - i)
        Sum = target_h + a_ls[i]
        if diff == Sum:
            ans += 1
print(ans)


### FIXED CODE ###

from collections import defaultdict
n = int(input())
a_ls = list(map(int, input().split()))
L_dict = defaultdict(int)
for i in range(n):
    Li = a_ls[i] + i + 1
    L_dict[Li] += 1

ans = 0
for j in range(n):
    Rj = j + 1 - a_ls[j]
    ans += L_dict[Rj]
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
H, W, M = map(int, input().split())#slow,行数H、列数W、爆弾数M
hcnt = [0] * H#何行目に何個あるか
wcnt = [0] * W#何列目に何個あるか
bomb = []
cnt = 0

for i in range(M):
    bh, bw = map(int, input().split())
    hcnt[bh - 1] += 1#行方向
    wcnt[bw - 1] += 1#列方向
    if bomb.count([bh - 1,bw - 1]) == 0:
        bomb.append([bh - 1,bw - 1])
#hcnt [2,1]
#wcnt[1,1,1]
hmax = max(set(hcnt))
wmax = max(set(wcnt))
for i in range(H):
    for j in range(W):
        if hcnt[i] == hmax and wcnt[j] == wmax and bomb.count([i, j]) == 0:
            cnt += 1

if cnt > 0:
    print(hmax + wmax)
else:
    print(hmax + wmax - 1)

### FIXED CODE ###


import sys
from collections import Counter

H, W, M = map(int, sys.stdin.readline().rstrip().split())#行数H、列数W、爆弾数M
hcnt = [0] * H#何行目に何個あるか
wcnt = [0] * W#何列目に何個あるか
bomb = []

for i in range(M):
    bh,bw=map(int,sys.stdin.readline().rstrip().split())
    hcnt[bh - 1] += 1#行方向
    wcnt[bw - 1] += 1#列方向
    bomb.append((bh - 1,bw - 1))
#hcnt [2,1]
#wcnt[1,1,1]
#bomb[[1,1],[0,0],[0,2]]
hmax = max(hcnt)#2
wmax = max(wcnt)#1

crs = 0#hmax and wmax crosspoint
for (i, j) in bomb:
    if hcnt[i] == hmax and wcnt[j] == wmax:
        crs += 1
#all crosspoint has bomb
if crs == Counter(hcnt)[hmax] * Counter(wcnt)[wmax]:
    print(hmax + wmax - 1)
#more than one crosspoint has no bomb
else:
    print(hmax + wmax)
### BUGGY CODE ###

from itertools import permutations, combinations
n = int(input())
s = []
for _ in range(n):
  s.append(input())

ilist = []
for a in range(len(s)):
  ilist.append(list(s[a]))

for ss in range(len(ilist)):
  ilist[ss].sort()

li = list(combinations(ilist, 2))
ans = 0

for b in range(len(li)):
  if(li[b][0] == li[b][1]):
    ans += 1
print(ans)

### FIXED CODE ###

from collections import *
 
n = int(input())
dic = defaultdict(int)
for i in range(n):
  dic["".join(sorted(input()))] += 1
 
ans = 0
for k,v in dic.items(): 
  ans += int(v*(v-1)/2)
  #ans += v*(v-1)//2
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

#input
N = int(input())
A = list(map(int, input().split()))
 
#output
from collections import Counter
from operator import itemgetter
l = Counter(A).most_common()
 
maximum_operation = [0] * N
for K in range(len(l)):
    l = Counter(A).most_common()
    while l[K][1] > 0:
        for i in range(K+1):
            l[i] = (l[i][0], l[i][1]-1)
        l.sort(key=itemgetter(1), reverse = True)
        maximum_operation[K] += 1
 
for m in maximum_operation:
    print(m)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

#output
from collections import Counter
import bisect

l = Counter(A).most_common()
l = [b for a, b in l]
M = len(l)
l.sort()
p = sum(l)

maximum_operation = [0] * N

ll = []
for x in reversed(range(1, N+1)):
    a = bisect.bisect_left(l, x)
    if a == 0:
        b = M*x
        c = 0
    elif a >= M:
        b = 0
        c = p
    else:
        b = (M-a)*x
        c = sum(l[0:a]) 
    ll.append((b + c)/x)

for K in range(M):
    maximum_operation[K] = N - bisect.bisect_left(ll, K+1)

for m in maximum_operation:
    print(m)
### BUGGY CODE ###

import bisect
N,Q = (int(x) for x in input().split())

stop_arr = [[] for _ in range(N)]
for i in range(N):
    S,T,X = (int(x) for x in input().split())
    stop_arr[i] = [S,T,X]
Q_arr = [0 for _ in range(Q)]
for i in range(Q):
    Q_arr[i] = int(input())

stop_arr_ind = list(range(N))
stop_arr_ind.sort(key=lambda x:stop_arr[x][2], reverse=True)
# stop_arr.sort(key=lambda x:x[2], reverse=True)
ans_arr = [-1]*Q

for i in stop_arr_ind:
    s,t,x = stop_arr[i]
    q_start = bisect.bisect_left(Q_arr, s-x)
    q_stop = bisect.bisect_left(Q_arr, t-x)
    for i in range(q_start, q_stop):
        ans_arr[i] = x

ans = ""
for a in ans_arr:
    ans += str(a)+"\n"

print(ans, end="")


### FIXED CODE ###

import bisect

N,Q = (int(x) for x in input().split())

stop_arr = [tuple(map(int, input().split())) for _ in range(N)]
Q_arr = [int(input()) for _ in range(Q)]

stop_arr_ind = list(range(N))
stop_arr_ind.sort(key=lambda x:stop_arr[x][2])
# stop_arr.sort(key=lambda x:x[2], reverse=True)
ans_arr = [-1]*Q
skip_arr = [-1]*(Q+1)

def update_skip(skip_arr, x):
    if skip_arr[x] == -1:
        return x
    x_dest = update_skip(skip_arr, skip_arr[x])
    skip_arr[x] = x_dest
    return x_dest

for i in stop_arr_ind:
    s,t,x = stop_arr[i]
    q_start = bisect.bisect_left(Q_arr, s-x)
    q_stop = bisect.bisect_left(Q_arr, t-x)
    l = q_start
    while l < q_stop:
        if skip_arr[l] == -1:
            skip_arr[l] = q_stop
            ans_arr[l] = x
            l += 1
        else:
            l = update_skip(skip_arr, l)

print(*ans_arr, sep="\n")
### BUGGY CODE ###

n = input()
arr = list(map(int, input().split()))
ar = [0 for i in range(max(arr))]
for i in arr:
    ar[i - 1] += 1
res = 0
for i in range(len(ar)):
    if ar[i] > i + 1:
        res += ar[i] - i - 1
    if ar[i] < i + 1:
        res += ar[i]
print(res)


### FIXED CODE ###

n = input()
arr = list(map(int, input().split()))
ar = [0 for i in range(100001)]
res = 0
for i in arr:
    if i > 100000:
        res += 1
    else:
        ar[i] += 1
for i in range(len(ar)):
    if ar[i] > i:
        res += ar[i] - i
    if ar[i] < i:
        res += ar[i]
print(res)
### BUGGY CODE ###

N,S =map(int,input().split())
A=list(map(int,input().split()))
mod=998244353
ans=0
q=[0]*(S+1)
for i in range(N):
    q[0]+=1
    q2=[0]*(S+1)
    for j in range(S+1):
        q[j]%=mod
        q2[j]+=q[j]
        if (j + A[i]) <= S:
            q2[j+A[i]]+=q[j]
    q = q2
    ans+=q[S]%mod
    ans%=mod
print(ans)


### FIXED CODE ###

N,S =map(int,input().split())
A=list(map(int,input().split()))
mod=998244353
ans=0
q=[0]*(S+1)
for i in range(N):
    q2=q.copy()
    if A[i]<=S:
        for j in range(A[i],S+1):
            q[j]+=q2[j-A[i]]
        q[A[i]]+=i+1
    ans+=q[S]
    ans%=mod
print(ans)