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

from collections import deque
A =input()
S = deque(A)
H = 0
Q = int(input())
Qlist = []
for i in range(Q):
    Qlist.append(list((map(str,input().split()))))
for i in range(Q):
    op = Qlist[i]
    if len(op) ==1:
        H +=1
    else:
        if op[1] =='1':
            if H%2 == 0:
                S.appendleft(op[2])
            else:
                S.append(op[2]) 
        else:
            if H%2 == 0:
                S.append(op[2])
            else:
                S.appendleft(op[2])
if H%2 == 1:
    S.reverse()
A = S[0]
for i in range(1,len(S)):
    A += S[i]
print(A)

### FIXED CODE ###

from collections import deque
S= deque(input())
Q = int(input())
ba = 1
for i in range(Q):
    Query =list(map(str,input().split()))
    Query0 = Query[0]
    if Query[0] == '1':
        ba *= -1
    else:
        if Query[1] == '1' and ba ==1:
            S.appendleft(Query[2])
        elif Query[1] == '1' and ba ==-1:
            S.append(Query[2])
        elif Query[1] == '2' and ba ==1:
            S.append(Query[2])
        elif Query[1] == '2' and ba ==-1:
            S.appendleft(Query[2])
if ba == -1:
    S.reverse()
mojieru = ''.join(S)
print(mojieru)
### BUGGY CODE ###

N, K = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(N)]
X, Y = zip(*XY)
X_s = sorted(X)
Y_s = sorted(Y)

r = 10**20
for xi0 in range(N):
  for xi1 in range(xi0, N):
    for yi0 in range(N):
      for yi1 in range(yi0, N):
        x0 = X_s[xi0]
        x1 = X_s[xi1]
        y0 = Y_s[yi0]
        y1 = Y_s[yi1]
        c = 0
        for x, y in XY:
          if x0 <= x <=x1 and y0 <= y <= y1:
            c += 1
        if c >= K:
          r = min(r, (x1 - x0) * (y1 - y0))
print(r)

### FIXED CODE ###

N, K = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(N)]
X, Y = zip(*XY)
X_s = sorted(X)
Y_s = sorted(Y)

r = 10**20
for xi0 in range(N):
  for xi1 in range(xi0, N):
    for yi0 in range(N):
      for yi1 in range(yi0, N):
        x0 = X_s[xi0]
        x1 = X_s[xi1]
        y0 = Y_s[yi0]
        y1 = Y_s[yi1]
        c = 0
        for x, y in XY:
          if x0 <= x <=x1 and y0 <= y <= y1:
            c += 1
        if c >= K:
          r = min(r, (x1 - x0) * (y1 - y0))
print(r)
### BUGGY CODE ###

from math import factorial
n,m,K=map(int,input().split())
ans=0
t=0
def comb(n,r):
    return factorial(n)//factorial(n-r)//factorial(r)
for i in range(3,n+m+1):
    for j in range(max(1,i-n),i):
        if(j>m):
            break
        k=i-j
        if(j==1 or k==1):
            ans+=(i-2)*(m-j+1)*(n-k+1)
        else:
            ans+=(i-2)*(m-j+1)*(n-k+1)*2
print((ans*comb(n*m-2,K-2))%(10**9+7))

### FIXED CODE ###

n,m,k=map(int,input().split())
mod=10**9+7
x=1
y=1
for i in range(1,k-1):
    y*=i
    y%=mod
for i in range(k-2):
    x*=n*m-2-i
    x%=mod
x*=pow(y,mod-2,mod)
x%=mod
def f(n,m):
    s=0
    for i in range(1,n):
        s+=i*(n-i)
        s%=mod
    return s*m*m%mod
print((f(n,m)+f(m,n))*x%mod)
### BUGGY CODE ###

n,m = map(int, input().split())
a = [int(input()) for i in range(m)]
mod = (10**9)+7
dp = [1] + [0]*(n)
for i in range(1,n+1):
    if i in a:
        dp[i] == 0
    else:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod
print(dp[-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int, input().split())
A = set()
for i in range(m):
    a = int(input())
    A.add(a)
mod = (10**9)+7
dp = [1] + [0]*(n)
for i in range(1,n+1):
    if i in A:
    #リストに対するinは激遅なのでset
        dp[i] == 0
    else:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod
print(dp[-1])
### BUGGY CODE ###

def DI(n):
    D = []
    for i in range(1,int(n**0.5)+1):
        if n % i == 0:
            D.append(i)
            if i != n//i:
                D.append(n//i)
    return D
X = int(input())
D = DI(X)
flag = False
for i in range(len(D)):
    for a in range(D[i]+1):
        b = -(D[i] - a)
        if a**5 - b**5 == X:
            print(str(a) + ' ' + str(b))
            flag = True
            break
    if flag:
        break

### FIXED CODE ###

X = int(input())
flag = False
for i in range(-120,120):
    for j in range(-120,120):
        if i**5 - j**5 == X:
            print(str(i) + ' ' + str(j))
            flag = True
            break
    if flag:
        break
### BUGGY CODE ###

N = int(input())
A = [0]*N
A = list(map(int, input().split()))
total = 1
for i in range(N):
  total = total * A[i]
if total > 10**18:
  total = -1
print(total)

### FIXED CODE ###

N = int(input())
A = [0]*N
A = list(map(int, input().split()))
total = 1
if 0 in A:
  total = 0
else:
  for i in range(N):
    total = total * A[i]
    if total > 10**18:
      total = -1
      break
print(total)
### BUGGY CODE ###

import numpy as np

N = int(input())
# P = np.array(input().split(' '), dtype = int)
P = list(map(int, input().split(' ')))

double = np.array([P for i in range(N)])
ar_P = np.array(P).reshape(-1,1)
ar_bool = (double < ar_P)
for i in range(N):
    N -= np.any(ar_bool[i][:i+1])
print(N)

### FIXED CODE ###

N = int(input())
# P = np.array(input().split(' '), dtype = int)
P = list(map(int, input().split(' ')))

p_min = P[0]
ans = 0
for p in P:
    if p <= p_min:
        p_min = p
        ans += 1
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
c=[n for i in range(n)]
for i in range(k):
    b=[0 for i in range(n)]
    for j in range(n):
        for k in range(max(j-a[j],0),min(j+a[j]+1,n)):
            b[k]+=1
    #print(b)
    a=b
    if b==c:
        break
print(*a)


### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
c=[n for i in range(n)]
for j in range(k):
    d=[0 for i in range(n+1)]
    for i in range(n):
        d[max(i-a[i],0)]+=1
        d[min(i+a[i]+1,n)]-=1
    e=[d[0]]
    for i in range(n-1):#ちょっと特殊な累積和 普通のものの[1:-1]
        e.append(e[i]+d[i+1])
    #print(d,e,sep='\n')
    #print(e)
    a=e
    if e==c:
        break
print(*a)
### BUGGY CODE ###

from itertools import permutations
N = int(input())
S = input()
res = N**3

for i in range(N):
  for j in range(N):
    for k in range(N):
      if not i<j<k: 
        res -= 1
        continue
      
      if j-i == k-j:
        res -= 1
        continue

      if S[i]==S[j] or S[i]==S[k] or S[j]==S[k]:
        res -= 1
        continue

print(res)

### FIXED CODE ###

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

r, g, b = 0, 0, 0
for c in S:
  if c == "R": r += 1
  if c == "G": g += 1
  if c == "B": b += 1

total = r*g*b

for i in range(N):
  for j in range(i+1, N):
    if S[i] == S[j]: continue

    k = 2*j - i
    if k >= N: continue
    if S[i] == S[k] or S[j] == S[k]: continue
    total -= 1

print(total)
### BUGGY CODE ###

l = input()
m = l.split(" ")
n = int(m[0])
k = int(m[1])
a = abs(n-k)
while a < n:
  n = a
  a = abs(n-k)
print(n)


### FIXED CODE ###

NK = input().split(' ')
N = int(NK[0])
K = int(NK[1])

while N>K:
  N = N%K
  
print(min([N,K-N]))
### BUGGY CODE ###

N = int(input())
I = [x for x in range(1,N+1)]
P = [x+1 for x in range(1,N)]
P.append(1)
M = [x % y for (x,y) in zip(I,P)]
print(sum(M))

### FIXED CODE ###

N = int(input())
ans = N*(N-1)//2
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    f = list(map(int, input().split()))
    a = sorted(a)
    f = sorted(f)
    f = f[::-1]
    mi = -1  # Impossible
    ma = 10 ** 12  # Possible
    for i in range(100):
        md = mi + (ma - mi) // 2
        if can_achieve(md, a, f, k, n):
            ma = md
        else:
            mi = md
        if ma - mi <= 1:
            break
    print(ma)

def can_achieve(score, a, f, k, n):
    sumb = 0
    for i in range(n):
        b = a[i] - score // f[i]
        b = max(b, 0)
        sumb += b
    return k >= sumb

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    f = list(map(int, input().split()))
    a = sorted(a)
    f = sorted(f)
    f = f[::-1]
    mi = -1  # Impossible
    ma = 10 ** 12  # Possible
    for i in range(100):
        md = mi + (ma - mi) // 2
        if can_achieve(md, a, f, k, n):
            ma = md
        else:
            mi = md
        if ma - mi <= 1:
            break
    print(ma)

def can_achieve(score, a, f, k, n):
    sumb = 0
    for i in range(n):
        b = a[i] - score // f[i]
        b = max(b, 0)
        sumb += b
    return k >= sumb

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

from sys import stdin

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

n = int(stdin.readline().rstrip())
an = list(map(int, input().split()))


max = 0
for i in range(n):
  before = -1
  for j in range(n):
    if( j==i ):
      continue
    if( before == -1 ):
      before = an[j]
    else:
      before = gcd(before, an[j])
  if(max < before ):
    max = before
print(max)


### FIXED CODE ###

from sys import stdin

def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

n = int(stdin.readline().rstrip())
an = list(map(int, input().split()))

left = []
right = []

for i in range(n):
  if(i==0):
    before = an[i]
  else:
    before = gcd(before, an[i])
  left.append(before)

for i in range(n):
  if(i==0):
    before = an[n-1-i]
  else:
    before = gcd(before, an[n-1-i])
  right.append(before)

max = 0
for i in range(n):
  if(i==0):
    before = right[n-2];
  elif(i==(n-1)):
    before = left[n-2];
  else:
    before = gcd(left[i-1],right[n-2-i])
  if(max < before ):
    max = before

print(max)
### BUGGY CODE ###

n,k = [int(s) for s in input().split()]
#n,k = [int(s) for s in data.pop().split()]
w_org = []
[w_org.append(int(input())) for i in range(n)]
#[w_org.append(int(data.pop())) for i in range(n)]

def can(p_org,k):
	p = p_org
	w = w_org[:]
	while k and w:
		ww = w[0]
		if ww <= p:
			p -= ww
			w.pop(0)
		else:
			p = p_org
			k -= 1
		if p == 0:
			p = p_org
			k -= 1
		#print(ww,k,p)
	return not(w)


left,right = 0,sum(w_org)+1
while left+1 < right:
	middle = (left+right) // 2
	if can(middle,k):
		right = middle
	else:
		left = middle
print(right)

### FIXED CODE ###

n,k = [int(s) for s in input().split()]
#n,k = [int(s) for s in data.pop().split()]
#n,k = 100000,100000
w_org = []
[w_org.append(int(input())) for i in range(n)]
#[w_org.append(int(data.pop())) for i in range(n)]
#w_org = [1 for i in range(n)]


def can(p_org,k):
	p = p_org
	w = w_org[::-1]
	while k and w:
		ww = w[-1]
		if ww <= p:
			p -= ww
			w.pop()
		else:
			p = p_org
			k -= 1
		if p == 0:
			p = p_org
			k -= 1
		#print(ww,k,p)
	return not(w)


left,right = max(w_org)-1,sum(w_org)+1
roop = 0
while left+1 < right:
	roop += 1
	middle = (left+right) // 2
	if can(middle,k):
		right = middle
	else:
		left = middle
print(right)
### BUGGY CODE ###

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

memo = [-1]*K

for memo_i in range(K):
    memo[memo_i] = P[memo_i]

ans = sum(memo)

for i in range(K, N):
    memo.pop(0)
    memo.append(P[i])
    sum_ = sum(memo)
    ans = max(ans, sum_)

tmp = ans - K + 1
print(K-1+(tmp - 0.5*(tmp-1)))

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
memo = sum(P[:K])
ans = memo

for i in range(K, N):
    memo = memo - P[i-K] + P[i]
    ans = max(ans, memo)

print(K-1+((ans-K+1) - 0.5*((ans-K+1)-1)))
### BUGGY CODE ###

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

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

b = [0] * m
c = [0] * m

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

for i in range(m):
    lists = [c[i]]*b[i]
    a = a+lists
a.sort(reverse = True)

print(sum(a[:n]))


### FIXED CODE ###

n,m = map(int,input().split())
from collections import defaultdict
d = defaultdict(int)
for a in input().split():
    d[int(a)]+=1

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

d = sorted(d.items(),key=lambda x:x[0],reverse=True)
i=0
ans=0
while n>0:
    if d[i][1]<=n:
        ans += d[i][0]*d[i][1]
        n -= d[i][1]
        i +=1
    else:
        ans += d[i][0]*n
        n=0
print(ans)
### BUGGY CODE ###

n, m = list(map(int, input().split()))
card = list(map(int, input().split()))
data = []
for i in range(m):
    data.append(list(map(int, input().split())))
for i in range(m):
    count = 0
    while min(card) < data[i][1] and count < data[i][0]:
        card[card.index(min(card))] = data[i][1]
        count += 1
print(sum(card))

### FIXED CODE ###

import bisect
n,m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()

data = [None] * m
for i in range(m):
    data[i] = list(map(int, input().split()))
data.sort(key = lambda x : x[1])
data.reverse()


ans = 0
count = 0
pre_index = 0
#print(data)
#print(a)
#data[][1] = value, data[][0] = card_num
for i in range(m):
    insert_index = bisect.bisect_left(a, data[i][1])
    count = min(data[i][0], insert_index - pre_index)
    for j in range(pre_index, pre_index + count):
        if j >= n:
            break
        a[j] = 0
    ans += count * data[i][1]
    pre_index = pre_index + count
print(ans + sum(a))
### BUGGY CODE ###

n,x,y=map(int,input().split())
l=[]
for i in range(n-1):
  for k in range (i+1,n):
    if k<x-1 or i>y-1:
      l.append(k-i)
    else:
      l.append(min(abs(x-1-i)+abs(y-1-k)+1,k-i))
for i in range(1,n):
  print(l.count(i))
      

### FIXED CODE ###

from collections import Counter
n,x,y=map(int,input().split())
l=[]
for i in range(n-1):
  for k in range (i+1,n):
      l.append(min(abs(x-1-i)+abs(y-1-k)+1,k-i))
S=Counter(l)
for i in range(1,n):
  print(S[i])
### BUGGY CODE ###

n=int(input())
t,a=map(int,input().split())
for i in range(1,n):
  c,d=map(int,input().split())
  times=min(t//c,a//d)
  e,f=c*times,d*times
  while(e<t or f<a):
    #print(e,f)
    times+=1
    e,f=c*times,d*times
    #print(e,f)
  t,a=e,f
print(t+a)


### FIXED CODE ###

n=int(input())
t,a=map(int,input().split())
for i in range(1,n):
  c,d=map(int,input().split())
  if(t/c>a/d):
    if(t%c==0):times=t//c
    else:times=t//c+1
  else:
    if(a%d==0):times=a//d
    else:times=a//d+1
  #print(times)
  t,a=c*times,d*times
  #print(t,a)
print(t+a)
### BUGGY CODE ###

import math
import sys
import itertools
import queue
from fractions import gcd
import time


def lcm(a, b):
    return a * b // gcd(a, b)

mod = 1000000007

if __name__ == "__main__":
    N= int(sys.stdin.readline())
    A = list(map(int,sys.stdin.readlines()))
    k=A.pop(0)
    m = max(A)
    A.insert(0,k)
    print(m)
    if k>m:
        m=k
    for i in range(1,len(A)):
        if m == A[i]:
            k=A.pop(i)
            m = max(A)
            A.insert(i,k)
            print(m)
            m=k
        else:
            print(m)

### FIXED CODE ###

"""
# 標準入力取得
## 文字列
 = sys.stdin.readline().rstrip()
 = list(sys.stdin.readline().rstrip())

## 数値
 = int(sys.stdin.readline())
 = map(int, sys.stdin.readline().split())
 = list(map(int, sys.stdin.readline().split()))
 = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]
"""

import math
import sys
import itertools
import queue
from fractions import gcd
import time


def lcm(a, b):
    return a * b // gcd(a, b)

mod = 1000000007

if __name__ == "__main__":
    N= int(sys.stdin.readline())
    A = list(map(int,sys.stdin.readlines()))
    l = sorted(A)
    m1 = l[-1]
    m2 = l[-2]
    for i in range(N):
        if A[i] == m1:
            print(m2)
        else:
            print(m1)
### BUGGY CODE ###

x = int(input())
ans = 2

p = [2]
i = 3
while i < x:
    for j in p:
        if i%j == 0:
            break
        elif j == p[-1]:
            p.append(i)
    i += 2

if x > 2:
    flag = True
    while flag:
        for j in p:
            if i%j == 0:
                break
            elif j == p[-1]:
                ans = i
                flag = False
                break
        i += 2
print(ans)


### FIXED CODE ###

x = int(input())
ans = 2

p = [2]
i = 1
Flag = True
while i**2 < 100001:
    i += 2
    for j in p:
        if i%j == 0:
            break
        elif j == p[-1]:
            p.append(i)
for i in range(100000):
    if x+i in p:
        ans = x+i
        break
    elif x+i > p[-1]:
        for j in p:
            if (x+i)%j == 0:
                break
            elif j == p[-1]:
                ans = x+i
                break
        if ans == x+i:
            break

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

import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)

    s, t = ns()
    s, t = s - 1, t - 1

    visited = [False for _ in range(n)]

    e3 = [[] for _ in range(n)]
    for i in range(n):
        que = collections.deque(e[i])
        for _ in range(2):
            for __ in range(len(que)):
                tmp = que.popleft()
                for ei in e[tmp]:
                    que.append(ei)
        tmp = set(que)
        tmp -= {i}
        e3[i] = list(tmp)

    ans = -1
    cnt = 1
    que = collections.deque(e3[s])

    visited[s] = True
    for ei in e3[s]:
        visited[ei] = True

    finflg = True

    while len(que) and finflg:
        cnt += 1
        for _ in range(len(que)):
            q = que.popleft()
            for ei in e3[q]:
                if not visited[ei]:
                    visited[ei] = True
                    que.append(ei)
                    if ei == t:
                        finflg = False
                        ans = cnt

    print(ans if ans != -1 else -1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)

    s, t = ns()
    s, t = s - 1, t - 1

    visited = [[True] * 3 for _ in range(n)]

    que = collections.deque()
    que.append([0, s])
    visited[s][0] = False
    cnt = 0
    ans = -1
    flg = True

    while que and flg:
        cnt += 1
        for _ in range(len(que)):
            i, q = que.popleft()
            for ei in e[q]:
                tmp = (i + 1) % 3
                if tmp == 0 and ei == t:
                    ans = cnt // 3
                    flg = False
                    break
                elif visited[ei][tmp]:
                    visited[ei][tmp] = False
                    que.append([tmp, ei])

    print(ans)


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

#!/usr/bin/env python3
import sys


def solve(N: int, Q: int, S: str, l: "List[int]", r: "List[int]"):
    aclist = [] 
    end = N - 1
    for i in range(end):
        if S[i] == 'A' and S[i+1] == 'C':
            aclist.append(i)

    for i in range(Q):
        res = 0
        begin = l[i] - 1
        end   = r[i] - 2

        for ac in aclist:
            if ac >= begin:
                if ac <= end:
                    res += 1
                else:
                    break

        print(res)

            


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    l = [int()] * (Q)  # type: "List[int]" 
    r = [int()] * (Q)  # type: "List[int]" 
    for i in range(Q):
        l[i] = int(next(tokens))
        r[i] = int(next(tokens))
    solve(N, Q, S, l, r)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from bisect import bisect_left
from bisect import bisect_right


def solve(N: int, Q: int, S: str, l: "List[int]", r: "List[int]"):
    aclist = [] 
    end = N - 1
    for i in range(end):
        if S[i] == 'A' and S[i+1] == 'C':
            aclist.append(i)

    len_ac = len(aclist)

    for i in range(Q):
        res = 0
        begin = l[i] - 1
        end   = r[i] - 2

        s_start = bisect_left(aclist,begin)
        s_end   = bisect_right(aclist,end)

        print(s_end-s_start)
            


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    l = [int()] * (Q)  # type: "List[int]" 
    r = [int()] * (Q)  # type: "List[int]" 
    for i in range(Q):
        l[i] = int(next(tokens))
        r[i] = int(next(tokens))
    solve(N, Q, S, l, r)

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

N,K = map(int,input().split())
h = list(map(int,input().split()))

dp = [0]*N

#iは知りたいdp
for i in range(1,N):
    #for j in range(max(i-K,0),i)はジャンプできる段数
    dp[i] = min(dp[j]+abs(h[j]-h[i]) for j in range(max(i-K,0),i))
print(dp[-1])

### FIXED CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))

dp = [0]*N

#iは知りたいdp[i]
for i in range(1,N):
    #for j in range(max(i-K,0),i)はジャンプできる段数
    dp[i] = min(dp[j]+abs(h[j]-h[i]) for j in range(max(i-K,0),i))
print(dp[N-1])
### BUGGY CODE ###

#codinng:utf-8

N = int(input())
count = 0

while N > 0:
    count += N % 10
    N = N // 10

if count % 9 == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

#codinng:utf-8

N = int(input())
count = 0

while N > 0:
    count += (N % (10 ** 100)) % 9
    N = N // (10 ** 100)

if count % 9 == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import sys
from bisect import *

input = sys.stdin.readline

def f(n, q, ss):
    xst = []
    for ssk in ss[:n]:
        s, t, x = map(int, ssk.split())
        xst.append([x, s - x, t - x])
    xst.sort()

    ds = list(map(int, ss[n:]))
    ans = [-1] * q

    for x, s, t in xst:
        i = bisect_left(ds, s)
        while i < q:
            if ds[i] < t:
                if ans[i] == -1:
                    ans[i] = x
                i += 1
            else:
                break

    print(*ans, sep="\n")

n, q = map(int, input().split())
ss = sys.stdin.readlines()
f(n, q, ss)


### FIXED CODE ###

import sys
from bisect import *

input = sys.stdin.readline

def f(n, q):
    xst = []
    for i in range(n):
        s, t, x = map(int, input().split())
        xst.append([x, s - x, t - x])
    xst.sort()

    ds = []
    for i in range(q):
        d = int(input())
        ds.append(d)

    ans = [-1] * q
    jump = [-1] * q

    for x, s, t in xst:
        i = bisect_left(ds, s)
        fi = bisect_left(ds, t)
        while i < fi:
            if jump[i] != -1:
                i = jump[i]
            else:
                ans[i] = x
                jump[i] = fi
                i += 1

    print(*ans, sep="\n")

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