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

s = list(input())
q = int(input())

for _ in range(q):
    t = [x for x in input().split()]
    if t[0] == "1":
        s.reverse()
    else:
        if t[1] == "1":
            s.insert(0,t[2])
        else:
            s.append(t[2])

print(*s, sep="")


### FIXED CODE ###

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

rev = False

for _ in range(q):
    t = [x for x in input().split()]
    if t[0] == "1":
        rev = not rev
    else:
        if t[1] == "1":
            s.append(t[2]) if rev else s.appendleft(t[2])
        else:
            s.appendleft(t[2]) if rev else s.append(t[2])

if rev:
    s.reverse()
print("".join(s))
### BUGGY CODE ###

n = map(int, input().split())
a = list(map(int, input().split()))
ans = 1
for i in a:
    ans *= i
if ans > 10**18:
    print(-1)
else :
    print(ans)


### FIXED CODE ###

n = input()
a = list(map(int, input().split()))
if 0 in a:
  print(0)
  exit()
ans = 1
for x in a:
  ans *= x
  if ans > 10**18:
    print(-1)
    exit()
print(ans)
### BUGGY CODE ###

from collections import deque

n = int(input())
li = deque(list(map(int,input().split())) for i in range(1,n+1))

cnt = 0
check = []
play = 0

while play < n*(n-1) // 2:
    s = play
    for i in range(1,n):
        if i in check or len(li[i-1]) == 0:
            continue
        temp = li[i-1][0]
        if temp <= i:
            continue
        if li[temp-1][0] == i and temp not in check:
            del li[i-1][0]
            del li[temp-1][0]
            play += 1
            check.append(temp)
    cnt += 1
    check = []
    
    if s == play:
        print(-1)
        exit()

print(cnt)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 
N = int(input())
A = [[-1] + [int(x)-1 for x in row.split()][::-1] for row in sys.stdin.readlines()]
 
A.append([-1])

def f(cand):
    cand1 = set()
    can_use = []
    for n in cand:
        if A[A[n][-1]][-1] == n:
            can_use.append(n)
    for n in can_use:
        A[n].pop()
        cand1.add(n)
        if A[n][-1] != -1:
            cand1.add(A[n][-1])
    return len(can_use), cand1
    
answer = 0
rest = N*(N-1)
cand = set(range(N))
while True:
    answer += 1
    x,cand = f(cand)
    if x == 0:
        answer = -1
        break
    rest -= x
    if rest == 0:
        break
    
print(answer)
### BUGGY CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
def inpl_str():
    '''
    一行に複数の文字
    '''
    return list(input().split())


s = list(map(int,list(input())[:-1]))
n=len(s)
right = [0] * (n + 1)
for i in range(n):
    right[-i - 2] = (right[-i - 1] + s[-i-1] * 10**i) % 2019
log = defaultdict(lambda: 0)
ans=0
for i in range(n + 1):
    log[right[-i - 1]] += 1
    value = log[right[-i - 1]]
    if value!=1:
        ans+=2*(value-1)-1
# ans=0
# for value in log.values():
#     if value > 1:
#         ans += value * (value - 1) // 2
print(ans)

### FIXED CODE ###

'''
1~9の文字列で構成されたSの中で
i文字目からj文字目までが2019の倍数になっているものの個数を求めよ

terms:
    1<=|S|<=2*10**5

input:
    1817181712114

output:
    3
'''
from collections import defaultdict
import sys
input = sys.stdin.readline
s = input()[:-1]
n=len(s)
arr = [int(s[i]) for i in range(n)]
ans = 0
dic = defaultdict(int)
dic[0] = 1
now = 0
for i in range(n - 1, -1, -1):
    now += arr[i] * pow(10, n - i - 1, 2019)
    now %= 2019
    ans += dic[now]
    dic[now] += 1
print(ans)
### BUGGY CODE ###

print(sum(range(1,int(input()))))

### FIXED CODE ###

n=int(input())
n-=1
print(n*(n+1)//2)
### BUGGY CODE ###

n,h=map(int,input().split())
A,B=[],[]
for i in range(n):
  a,b=map(int,input().split())
  A.append(a)
  B.append(b)
ma=max(A)
BB=[]
for i in range(n):
  if B[i]>ma:
    BB.append(B[i])
BB.sort(reverse=True)
count=0
dmg=0
while dmg<h:
  if count<len(BB):
    dmg+=BB[count]
    count+=1
  else:
    dmg+=ma
    count+=1
print(count)

### FIXED CODE ###

n,h=map(int,input().split())
A,B=[],[]
for i in range(n):
  a,b=map(int,input().split())
  A.append(a)
  B.append(b)
ma=max(A)
BB=[]
for i in range(n):
  if B[i]>ma:
    BB.append(B[i])
BB.sort(reverse=True)
count=0
dmg=0
while dmg<h:
  if count<len(BB):
    dmg+=BB[count]
    count+=1
  else:
    r=(h-dmg-1)//ma+1
    dmg=h
    count+=r
print(count)
### BUGGY CODE ###

n,m = map(int,input().split())
cards = list(map(int,input().split()))

from collections import deque
import bisect

cards = deque(sorted(cards))

for _ in range(m):
    b,c = map(int,input().split())

    for _ in range(b):
        cards.append(c)


cards = sorted(cards,reverse=True)[:n]

print(sum(cards))


### FIXED CODE ###

n,m = map(int,input().split())
cards = list(map(int,input().split()))

from collections import Counter

d = dict(Counter(cards))

for _ in range(m):
    b,c = map(int,input().split())

    if c in d:
        d[c]+=b
    else:
        d[c]=b

d= sorted(d.items(),key=lambda x: x[0],reverse=True)

ans = 0
cnt = 0
for j in d:
    cnt +=j[1]
    ans +=j[0] * j[1]



    if cnt>n:
        ans -=j[0]*(cnt-n)
        print(ans)
        exit(0)

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

N=int(input())
S=input()


num=S.count("#")
if num>S.count("."):#全部黒にする
  num=S.count(".")
  
for i in range(0,N): #i番目まで白
  n=0
  for j in range(0,i):
    if S[j]=="#":
      n=n+1
      if n>=num: break
  for k in range(i,N):
    if S[k]==".":
      n=n+1    
      if n>=num: break
  if n<num:
    num=n
 
print(num)

### FIXED CODE ###

N=int(input())
S=input()


num=S.count("#")
if num>S.count("."):#全部黒にする
  num=S.count(".")
  
  
c_w=0
c_b=S.count(".")

for i in range(0,N): #i番目まで白
  if S[i]=="#":
    c_w+=1
  else:
    c_w=c_w
    c_b-=1
  num=min(num,c_w+c_b)
 
print(num)
### BUGGY CODE ###

t = input().split(" ")

N = int(t[0])
K = int(t[1])

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

for i in range(len(p)):
    #a = list(range(1,p[i]+1))
    #print(a)
    p[i] = sum(list(range(1,p[i]+1)))/p[i]
#    print(p[i])

ans = 0
for i in range(N-K+1):
    
    a =0
#    print(i)
    for j in range(K):
#        print(p[i+j])
        a += p[i+j]

    if a > ans:
        ans = a

print(ans)

    
    






### FIXED CODE ###

t = input().split(" ")

N = int(t[0])
K = int(t[1])

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

ans = 0
a =0

for i in range(len(p)):
    #a = list(range(1,p[i]+1))
    #print(a)
    p[i] = ((p[i]*(p[i]+1))/2)/p[i]
    a += p[i]
    
    if i >= K-1:
        
        if i >= K:
            a += -(p[i-K])
        if a > ans:
            ans = a

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

a, b, k = map(int, input().split())
for i in range(k):
    if 1 <= a:
        a -= 1
    elif 1 <= b:
        b -= 1
    #else:
    #   pass
print(a, b)

### FIXED CODE ###

a, b, k = map(int, input().split())
aout = max(0, a - k)
bout = max(0, b - max(0, k - a))
print(aout, bout)
### BUGGY CODE ###

n = int(input())
#from tqdm import tqdm
for i in range(1, n+1):
    ans=0
    for x in range(1, 10):
        for y in range(1, 10):
            for z in range(1, 10):
                if x**2 + y**2 + z**2 + x*y + y*z + z*x == i:
                    ans+=1
                    #print(i, x,y,z)
    if ans != 0:
        print(ans)
    else:
        print(ans)

### FIXED CODE ###

n = int(input())
#from tqdm import tqdm
ans=[0 for _ in range(10001)]
for x in range(1, 105):
    for y in range(1, 105):
        for z in range(1, 105):
            v = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if v < 10001:
                ans[v]+=1
                #print(i, x,y,z)
for i in range(n):
    print(ans[i+1])
### BUGGY CODE ###

N,M=(int(i) for i in input().split())
a=[int(i) for i in input().split()]
for i in range(M):
    b,c=(int(i) for i in input().split())
    l=[c]*b
    a.extend(l)

a=sorted(a,reverse=True)
answer=0
for i in range(N):
    answer+=a[i]
print(answer)

### FIXED CODE ###

N,M=(int(i) for i in input().split())
a=[[int(i),1] for i in input().split()]

for i in range(M):
    b,c=(int(i) for i in input().split())
    a.append([c,b])
    

a=sorted(a,key=lambda x:x[0],reverse=True)
answer=0
i=0
n=0
while True:
    answer+=a[i][0]*a[i][1]
    i+=1
    n+=a[i-1][1]
    if n>=N:
        answer-=a[i-1][0]*(n-N)
        break
print(answer)
### BUGGY CODE ###



import math
def solve():
  n = int(input())
  s = input()
  dp = [[] for _ in range(4)]

  for i in range(n):
    number = s[i]
    

    for k in dp[2]:
      dp[3].append(k+number)
    for l in dp[1]:
      dp[2].append(l+number)  
    dp[1].append(number)
    
    for i in range(4):
      dp[i] = list(set(dp[i]))
  print(len(dp[3]))
    
      
solve()

### FIXED CODE ###

import sys
#input = sys.stdin.readline
def solve():
  n = int(input())
  s = input()
  ans = 0
  for i in range(0,1000):
    t1,t2,t3 = 0,0,0
    c3 = str(i%10)
    c2 = str((i//10)%10)
    c1 = str(i//100)
    for t in range(n):
      if not t1:
        if s[t] == c1:
          t1 = 1
      elif not t2:
        if s[t] == c2:
          t2 = 1
      elif not t3:
        if s[t] == c3:
          t3 = 1
      
    
      if t1 and t2 and t3: 
        ans += 1
        break
  print(ans)
solve()
### BUGGY CODE ###

n = int(input())

l = []
num = 0
for s in range(n):
    i = input()
    if i not in l:
        l.append(i)
        num += 1

print(num)

### FIXED CODE ###

n = int(input())

l = set()
num = 0
for s in range(n):
    i = input()
    l.add(i)
print(len(l))
### BUGGY CODE ###

from bisect import bisect_left
n, Q = [int(x) for x in input().split()]
stx = [[int(x) for x in input().split()] for i in range(n)]
q = [int(input()) for i in range(Q)]
stx.sort(key=lambda x: x[2])
ans = [-1 for i in range(Q)]
skip = [-1 for i in range(Q)]

for (s, t, x) in stx:
  begin = bisect_left(q, s-x)
  end = bisect_left(q, t-x)
  while begin<end:
    if skip[begin]==-1:
      ans[begin] = x
      skip[begin] = end
      begin += 1
    else:
      begin = skip[begin]
for e in ans:
  print(e)

### FIXED CODE ###

from bisect import bisect_left
n, Q = list(map(int, input().split()))
stx = [list(map(int, input().split())) for i in range(n)]
q = [int(input()) for i in range(Q)]
stx.sort(key=lambda x: x[2])
ans = [-1 for i in range(Q)]
skip = [-1 for i in range(Q)]

for (s, t, x) in stx:
  begin = bisect_left(q, s-x)
  end = bisect_left(q, t-x)
  while begin<end:
    if skip[begin]==-1:
      ans[begin] = x
      skip[begin] = end
      begin += 1
    else:
      begin = skip[begin]
for e in ans:
  print(e)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def main():
    n, u, v = map(int, input().split())
    u, v = u-1, v-1
    G = [[] for i in range(n)]
    for i in range(n-1):
        a,b = map(int, input().split())
        a,b = a-1,b-1
        G[a].append(b)
        G[b].append(a)

    N = n
    # Euler Tour Technique
    S = []
    FS = [0]*N
    depth = [0]*N
    is_leaf = [0]*N
    def dfs(v, p, d):
        depth[v] = d
        FS[v] = len(S)
        S.append(v)
        f = True
        for w in G[v]:
            if w == p:
                continue
            dfs(w, v, d+1)
            S.append(v)
            f = False
        if f:
            is_leaf[v] = 1

    dfs(v, -1, 0)

    # Sparse Table
    L = len(S)
    lg = [0]*(L + 1)
    for i in range(2, L+1):
        lg[i] = lg[i >> 1] + 1
    st = [None]*(lg[L] + 1)
    st0 = st[0] = S
    b = 1
    for i in range(lg[L]):
        st0 = st[i+1] = [p if depth[p] <= depth[q] else q for p, q in zip(st0, st0[b:])]
        b <<= 1

    # LCA O(1)
    def LCA(u, v):
        x = FS[u]; y = FS[v]
        if x > y:
            x, y = y, x
        l = lg[y - x + 1]
        px = st[l][x]; py = st[l][y - (1 << l) + 1]
        return px if depth[px] <= depth[py] else py

    def dist(u, v):
        return abs(depth[u]-depth[v])

    ans = 0
    for i in range(n):
        if not is_leaf[i]:
            continue
        lca = LCA(u, i)
        if lca == v:
            continue
        if dist(lca, u) >= dist(lca, v):
            continue
        tmp = 0
        d = dist(u, lca) + dist(lca, i)
        if d != 0:
            tmp = 2*d
            aoki = d
        else:
            aoki = 0
        tak = depth[i]
        m = tak-aoki
        if m%2==1:
            tmp += 2*m -1
        else:
            tmp += 2*(m-1)
        ans = max(ans, tmp)
    print(ans//2)

main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

from collections import deque

def main():
    n, u, v = map(int, input().split())
    u, v = u-1, v-1
    G = [[] for i in range(n)]
    for i in range(n-1):
        a,b = map(int, input().split())
        a,b = a-1,b-1
        G[a].append(b)
        G[b].append(a)

    def bfs(start):
        dist = [0]*n
        is_leaf = [0]*n
        que = deque()
        que.append((start, -1, 0))
        while que:
            c,p,d = que.pop()
            dist[c] = d
            cnt = 0
            for to in G[c]:
                if to != p:
                    que.append((to,c,d+1))
                    cnt += 1
            if not cnt:
                is_leaf[c] = 1
        return dist, is_leaf

    a, is_leaf = bfs(v)
    b, _ = bfs(u)

    ans = 0
    for i in range(n):
        if not is_leaf[i]:
            continue
        if b[i] >= a[i]:
            continue
        tmp = 0
        d = b[i]
        if d != 0:
            tmp = 2*d
            aoki = d
        else:
            aoki = 0
        tak = a[i]
        m = tak-aoki
        if m%2==1:
            tmp += 2*m -1
        else:
            tmp += 2*(m-1)
        ans = max(ans, tmp)
    print(ans//2)

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

class Node(object):
	def __init__(self, key):
		self.key = key
		self.prev = None
		self.next = None

nil = Node(None)
nil.prev = nil
nil.next = nil

def insert(key):
	node = Node(key)
	node.next = nil.next
	nil.next.prev = node
	nil.next = node
	node.prev = nil;

def search(key):
	cur = nil.next
	while ((cur != nil) and (cur.key != key)):
		cur = cur.next
	return cur

def delete(t):
	if t!=nil:
		t.prev.next = t.next
		t.next.prev = t.prev
		del t

def deleteFirst():
	delete(nil.next)

def deleteLast():
	delete(nil.prev)

n = input()
for _ in range(int(n)):
	command = input()
	if command[0] == 'i':
		insert(command[7:])
	else:
		if command[6] == " ":
			delete(search(command[7:]))
		else:
			if command[6] == 'L':
				deleteLast()
			else:
				deleteFirst()

cur = nil.next
while(1):
	if cur.next == nil:
		break;
	print(cur.key, end=" ")
	cur = cur.next
print(cur.key)

### FIXED CODE ###

from collections import deque
n = input()
d = deque()
for i in range(int(n)):
	command = input()
	if command[0] == 'i':
		d.appendleft(command[7:])
	else:
		if command[6] == " ":
			if  command[7:] in d:
				d.remove(command[7:])
		else:
			if command[6] == 'L':
				d.pop()
			else:
				d.popleft()
for _ in range(len(d)-1):
	print(d.popleft(), end=" ")
print(d.pop())
### BUGGY CODE ###

import sys
import math
#import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

def F(i):
    return (limit // i)%MOD

def Z(s, t):
    return (s*t)%MOD

N = ri()
X = rl()
MOD = 10 ** 9 + 7
limit = math.factorial(N-1)
last = X[-1]
X = [last - x for x in X[:-1]] #最後までの距離
Y = [F(i) for i in range(1, N)]
answer = 0
for x, y in zip(X, Y):
    answer += Z(x, y)
    answer %= MOD

print(answer)

### FIXED CODE ###

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

MOD = 10 ** 9 + 7
U = 10 ** 5 + 10 # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)
N = ir()
X = np.array(lr())

inv = np.zeros(U, np.int64)
inv[1:] = fact_inv[1:] * fact[:-1] % MOD
coef = inv[1:N].cumsum() % MOD
answer = (np.diff(X) * coef % MOD).sum() % MOD
answer *= fact[N-1]
print(answer % MOD)
# 35
### BUGGY CODE ###

import fractions
import math

K = int(input())
sum = 0
kl = range(1, K+1)
combdict = {}

for i in kl:
    for j in kl:
        for k in kl:
            sum += math.gcd(i, math.gcd(j, k))
print(sum)

### FIXED CODE ###

import math

K = int(input())
sum = 0
kl = range(1, K+1)

for i in kl:
    for j in kl:
        for k in kl:
            sum += math.gcd(i, math.gcd(j, k))
print(sum)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split(" ")))
list = [a.index(x)+1 for x in range(1, n+1)]
print(*list)

### FIXED CODE ###

n = int(input())


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

d = {}

for val in range(n):
    d[val] = a_L[val]

#print(d)
ans = sorted(d.items(),key=lambda x:x[1])
#print(ans)

ans_L = []

for val in ans:
    ans_L.append(str(val[0]+1))

print(" ".join(ans_L))
### BUGGY CODE ###

n,a,b = map(int,input().split())
i = 1
p = 0
if (b-a)%2==0:
    print((b-a)//2)
else:
    if a <= (n//2):
        for i in range(1,n):
            b -= 1
            if p == 1:
                a += 1
            elif a <= 1:
                a = 1
                p += 1
            else:
                a -= 1
            if a == b:
                print(i)
                break
    else:
        for i in range(1,n):
            a += 1
            if p == 1:
                b -= 1
            elif b >= n:
                b = n
                p += 1
            else:
                b += 1
            if a == b:
                print(i)
                break

### FIXED CODE ###

n,a,b = map(int,input().split())
i = 1
p = 0
if (b-a)%2==0:
    print((b-a)//2)
else:
    if a-1 < n-b:
        print(min((1+b+(a-2))//2,b-1))
    else:
        print(min((n-a+(n-b+1))//2,n-a))
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))
pow2 = [2 ** i for i in range(61)]
a = sorted(a, reverse=True)
d = defaultdict(int)
for i in a:
    d[i] += 1


num = 0
for i in range(N):
    for k in range(60):
        if pow2[k] - a[i] != a[i]:
            if d[pow2[k] - a[i]] > 0 and d[a[i]] > 0:
                num += 1
                d[pow2[k] - a[i]] -= 1
                d[a[i]] -= 1
        else:
            if d[a[i]] >= 2:
                num += 1
                d[a[i]] -= 2
print(num)


### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
pow2 = [1]
for i in range(31):
    pow2.append(pow2[-1] * 2)
a = sorted(a, reverse=True)
d = defaultdict(int)
for i in a:
    d[i] += 1


num = 0
for i in range(N):
    if d[a[i]] == 0:
        continue
    for k in range(30, -1, -1):
        inv = pow2[k] - a[i]
        if inv < 0 or inv > a[i]:
            continue
        if inv != a[i]:
            if d[inv] > 0 and d[a[i]] > 0:
                p = min(d[inv], d[a[i]])
                num += p
                d[inv] -= p
                d[a[i]] -= p
                break
        else:
            if d[a[i]] >= 2:
                num += d[a[i]] // 2
                d[a[i]] %= 2
                break
print(num)
### BUGGY CODE ###

def N():
    return int(input())
def L():
    return list(map(int,input().split()))
def NL(n):
    return [list(map(int,input().split())) for i in range(n)]
mod = pow(10,9)+7
#import numpy
#import sympy
import math
def divisors(n):
    num = 0
    for i in range(1, int(math.sqrt(n) + 1)):
        if n % i == 0:
            num += 1
            if n != i**2:
                num += 1
    
    return num
n = N()
cnt = 0
for i in range(1,n):
    ab = n-i
    cnt += divisors(ab)
print(cnt)

### FIXED CODE ###

def N():
    return int(input())
def L():
    return list(map(int,input().split()))
def NL(n):
    return [list(map(int,input().split())) for i in range(n)]
mod = pow(10,9)+7
#import numpy
#import sympy
import math
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
def divi(n):
    ans = {1}
    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            ans |= l[i]
            ans |= l[n//i]
    ans.add(n)
    return ans

n = N()
cnt = 1
l = [{} for _ in range(n)]
l[1] = {1}
tab = [0]*(n+1)
for i in range(1,n+1):
    for j in range(i, n + 1, i):
        tab[j] += 1
tab[n]=0
print(sum(tab))
### BUGGY CODE ###

import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
 
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)

### FIXED CODE ###

import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    S, T, X = list(map(int, input().split()))
    STX.append((X, S, T))
STX = sorted(STX, key=lambda x: x[0])

for i in range(Q):
    D.append(int(input()))

skip = [-1]*Q

dist = [-1]*Q

for X, S, T in STX:
    s = S - X
    t = T - X - 1
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_right(D, t)
    #print(D)
    j = a
    while j < b:
        if skip[j] == -1:
            skip[j] = b
            dist[j] = X
            j+=1
        else:
            j=skip[j]


for i in range(Q):
    print(dist[i])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

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

sum = 0

if n <= a:
    sum = n

elif n <= (a + b):
    sum = a

else:
    while n >= (a + b):
        sum += a
        n -= (a + b)

    if n <= a:
        sum += n

    elif n <= (a + b):
        sum += a

print(sum)


### FIXED CODE ###

# -*- coding: utf-8 -*-

#入力
n, a, b = map(int, input().split())

sum = 0

if n <= a:
    sum = n

elif n <= (a + b):
    sum = a

else:
    p = n // (a + b)
    sum += a * p
    n -= p * (a + b)

    if n <= a:
        sum += n

    elif n <= (a + b):
        sum += a


#出力
print(sum)
### BUGGY CODE ###

n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
total = pow(2, n, mod) - 1
product = 1
div = 1
for i in range(1, max(a, b) + 1):
    product *= (n - i + 1)
    div *= i
    if i == a or i == b:
        total -= product // div
print(total % mod)

### FIXED CODE ###

n, a, b = map(int, input().split())
MOD = 10 ** 9 + 7
# Pythonのpowは繰り返し二乗法で実装されている
ans = pow(2, n, MOD) - 1
product = 1
div = 1
for i in range(1, b + 1):
    product = product * (n - i + 1) % MOD
    div = div * i % MOD
    if i == a or i == b:
        # 逆元を求める
        ans -= product * pow(div, MOD - 2, MOD)
print(ans % MOD)