Harryxun/stf_run huggingface dataset:
from collections import deque

def isCLKWISE(ph):
    a = [ph[-1][0]-ph[-3][0],ph[-1][1]-ph[-3][1]]
    b = [ph[-2][0]-ph[-3][0],ph[-2][1]-ph[-3][1]]
    crs = a[0]*b[1] - a[1]*b[0]
    if crs < 0 :
        return False
    else :
        return True
    
def ConvexHullScan(P):
    P = sorted(P)
    phU = deque([])
    phU.append(P[0])
    phU.append(P[1])
    for p in P[2:]:
        phU.append(p)
        while(True):
            if isCLKWISE(phU) :
                break
            else :
                del phU[-2]
                if len(phU) == 2 :
                    break
    phL = deque([])
    phL.append(P[-1])
    phL.append(P[-2])
    for p in P[-3::-1]:
        phL.append(p)
        while(True):
            if isCLKWISE(phL) :
                break
            else :
                del phL[-2]
                if len(phL) == 2 :
                    break
    phL.pop()
    phL.popleft()
    ph = phU + phL
    return ph

n = int(input())
P = deque([])
for i in range(n):
    P.append([int(x) for x in input().split()])
Q = ConvexHullScan(P)
print(len(Q))
Q.reverse()
idx = min([[x[1][1],x[1][0],x[0]] for x in enumerate(Q)])[2]
Q.rotate(-idx)
for q in Q:
    print(q[0],q[1])

### FIXED CODE ###

def isCLKWISE(ph) : return not ((ph[-1][0] - ph[-3][0])*(- ph[-3][1] + ph[-2][1]) - (ph[-2][0] - ph[-3][0])*(- ph[-3][1] + ph[-1][1] ) < 0)
      
def ConvexHullScan(P):
    P = sorted(P)
    phU = [P[0],P[1]]
    for p in P[2:]:
        phU.append(p)
        while(True):
            try :
                if isCLKWISE(phU) : break
                else : del phU[-2]
            except IndexError : break
    phL = [P[-1],P[-2]]
    for p in P[-3::-1]:
        phL.append(p)
        while(True):
            try :
                if isCLKWISE(phL) : break
                else : del phL[-2]
            except IndexError : break
    ph = phU + phL[1:-1]
    return ph
  
P = [[int(x) for x in input().split()] for _ in range(int(input()))]
P = ConvexHullScan(P)
P.reverse()
print(len(P))
idx = min([[x[1][1],x[1][0],x[0]] for x in enumerate(P)])[2]
for p in P[idx:] + P[:idx] : print(p[0],p[1])
n=int(input())
d=list(map(int,input().split()))
m=n/2
d=sorted(d)
print(d[m+1]-d[m])


### FIXED CODE ###

n=int(input())
d=list(map(int,input().split()))
m=int(n/2)
d=sorted(d)
print(d[m]-d[m-1])
ls = {"A":0, "B":1, "C":2}
cup = [1,0,0]
while 1:
    try:
	x, y = map(str,	raw_input().split(","))
	tmp = cup[ls[x]]
	cup[ls[x]] = cup[ls[y]]
	cup[ls[y]] = cup[ls[x]]
    except:
        break
p = cup.index(1)
if c == 0:
    print "A"
else:
    print "B" if c == 1	else "C"

### FIXED CODE ###

ls = {"A":0, "B":1, "C":2}
cup = [1,0,0]
while 1:
    try:
        x, y = map(str, raw_input().split(","))
        tmp = cup[ls[x]]
        cup[ls[x]] = cup[ls[y]]
        cup[ls[y]] = tmp
    except:
        break
p = cup.index(1)
if p == 0:
    print "A"
else:
    print "B" if p == 1 else "C"
from collections import deque
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

h,w,k = inm()
a = []
for i in range(h):
    t = ins()
    a.append(t)
    v = t.find('S')
    if v>=0:
        s = (i,v)
if h==w==k==3:
    3/0
q = deque([(s[0],s[1],0)])
b = [[BIG]*w for i in range(h)]
b[s[0]][s[1]] = 0
mn = BIG
while len(q)>0:
    x,y,d = q.popleft()
    mn = min([ \
      mn,(x+k-1)//k,(h-1-x+k-1)//k,(y+k-1)//k,(w-1-y+k-1)//k])
    if d>=k:
        continue
    for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
        xx = x+dx
        yy = y+dy
        if 0<=xx<h and 0<=yy<w and a[xx][yy]!='#' and \
           b[xx][yy]==BIG:
            b[xx][yy] = d+1
            q.append((xx,yy,d+1))
print(mn+1)


### FIXED CODE ###

from collections import deque
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

h,w,k = inm()
a = []
for i in range(h):
    t = ins()
    a.append(t)
    v = t.find('S')
    if v>=0:
        s = (i,v)
if h==w==k==-3:
    3/0
q = deque([(s[0],s[1],0)])
b = [[BIG]*w for i in range(h)]
b[s[0]][s[1]] = 0
mn = BIG
while len(q)>0:
    x,y,d = q.popleft()
    mn = min([ \
      mn,(x+k-1)//k,(h-1-x+k-1)//k,(y+k-1)//k,(w-1-y+k-1)//k])
    if d>=k:
        continue
    for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
        xx = x+dx
        yy = y+dy
        if 0<=xx<h and 0<=yy<w and a[xx][yy]!='#' and \
           b[xx][yy]==BIG:
            b[xx][yy] = d+1
            q.append((xx,yy,d+1))
print(mn+1)
n = int(raw_input())
A = map(int, raw_input().split())
q = int(raw_input())
m = map(int, raw_input().split())
 
def solve(i, m):
    if m == 0:
        return 1
    if i > n or m > sum(A):
        return 0
    res = solve(i + 1, m) or solve(i + 1, m - A[i])
    return res
         
for j in range(0, q):
    if solve(0, m[j]):
        print "yes"
    else:
        print "no"

### FIXED CODE ###

n = int(raw_input())
A = map(int, raw_input().split())
q = int(raw_input())
m = map(int, raw_input().split())
 
def solve(i, m):
    if m == 0:
        return 1
    if i  >= n or m > sum(A):
        return 0
    res = solve(i + 1, m) or solve(i + 1, m - A[i])
    return res
         
for j in range(0, q):
    if solve(0, m[j]):
        print "yes"
    else:
        print "no"
n, k = map(int, input().split())
A = []
for _ in range(n):
    t, d = map(int, input().split())
    A.append((d, t))
A.sort(reverse=True)
X = []
Y = []
st = set()
for d, t in A:
    if t in st:
        X.append(d)
    else:
        Y.append(d)
    st.add(t)
ans = 0
len_y = len(Y)
if len_y >= k:
    a = 0
    b = len_y - 1
    x = 0
    y = sum(Y[:k])
else:
    a = k - len_y
    b = len_y - 1
    x = sum(X[:k - len_y])
    y = sum(Y)
ans = x + y + len_y ** 2
t = ans
for i in range(min(len(X), len_y, k - len_y + 1, k - 1)):
    x += X[a]
    a += 1
    y -= Y[b]
    b -= 1
    len_y -= 1
    t = x + y + len_y ** 2
    ans = max(ans, t)
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
A = []
for _ in range(n):
    t, d = map(int, input().split())
    A.append((d, t))
A.sort(reverse=True)
X = []
Y = []
st = set()
for i in range(k):
    d, t = A[i]
    if t in st:
        X.append(d)
    else:
        Y.append(d)
        st.add(t)
x = sum(X)
y = sum(Y)
v = len(Y)
ans = x + y + v ** 2
for i in range(k, n):
    if not X:
        break
    d, t = A[i]
    if t in st:
        continue
    st.add(t)
    x -= X.pop()
    y += d
    v += 1
    ans = max(ans, x + y + v ** 2)
print(ans)
import bisect

A, B, Q = map(int,input().split())
s_list = [-inf] +  [int(input()) for i in range(A)] + [inf]
t_list = [-inf] + [int(input()) for i in range(B)] + [inf]
x_list = [int(input()) for i in range(Q)]

for x in x_list:
    
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
    a = b - 1
    c = d - 1 
    ans = inf
    for s in s_list[a], s_list[b]:
        for t in t_list[c], t_list[d]:
            dist1 = abs(s-x) + abs(t-s)
            dist2 = abs(t-x) + abs(t-s)
            ans = min(ans, dist1,dist2)
    print(ans)


### FIXED CODE ###

import bisect

A, B, Q = map(int,input().split())
INF = 10**18
s_list = [-INF] +  [int(input()) for i in range(A)] + [INF]
t_list = [-INF] + [int(input()) for i in range(B)] + [INF]
x_list = [int(input()) for i in range(Q)]

for x in x_list:
    
    b, d = bisect.bisect_right(s_list, x), bisect.bisect_right(t_list, x)
    a = b - 1
    c = d - 1 
    ans = INF
    for s in [s_list[a], s_list[b]]:
        for t in [t_list[c], t_list[d]]:
            dist1 = abs(s-x) + abs(t-s)
            dist2 = abs(t-x) + abs(t-s)
            ans = min(ans, dist1,dist2)
    print(ans)
N,K,M = map(int,input().split())
A = list(map(int,input().split()))

L = N * M
S = sum(A)

if L - S > K or S >= L:
    print(-1)
else:
    print(L - S)

### FIXED CODE ###

c = input()
c = ord(c) + 1
print(chr(c))
s=list(input())
res="None"
s.sort()
str="abcdefghijklmnopqrstuvwxyz"
for i in range (len(s)):
    if not(str[i] in s):
        res=str[i]
        break
 
print(res)

### FIXED CODE ###

s=list(input())
res="None"
s.sort()
str="abcdefghijklmnopqrstuvwxyz"

for i in range (26):
    if not(str[i] in s):
        res=str[i]
        break
 
print(res)
import math

def nlcm(t):
    res = 1
    for a in t:
        res *= a // math.gcd(a,res)
    return res

n = int(input())
T = [int(input()) for i in range(n)]

print(nlcm(T))

### FIXED CODE ###

from fractions import gcd

def nlcm(t):
    res = 1
    for a in t:
        res *= a // gcd(a,res)
    return res

n = int(input())
T = [int(input()) for i in range(n)]

print(nlcm(T))
import numpy as np

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

def main():
    ans = 0
    for i, ai in enumerate(A):
        ans += ((ai % np.delete(A, i)).min() != 0)
    print(ans)

main()


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
maxA = max(A)
counter = [0]*(maxA+1)
for ai in A:
    for m in range(ai, maxA+1, ai):
        counter[m] += 1
ans = 0
for ai in A:
    ans += (counter[ai] == 1)
print(ans)
def main():
  import bisect
  import sys
  from itertools import accumulate
  input = sys.stdin.readline
  def hsnum(ls,x):
    num = 0
    for i in range(n):
      y = x-ls[i]
      num += n-bisect.bisect_left(ls,y)
    return num
  n,m = map(int, input().split())
  a = list(map(int, input().split()))
  a.sort()
  suma = [0]+list(accumulate(a))
  lx = 0
  rx = 2*10**5+2
  error = 0
  while lx < rx:
    mx = (lx+rx)//2
    if hsnum(a,mx) < m:
      rx = mx
    elif hsnum(a,mx) > m:
      if hsnum(a,mx+1) < m:
        error = hsnum(a,mx)-m
        lx = mx
        break
      lx = mx + 1
    else:
      lx = mx
      break
  ans = 0
  for i in a:
    rema = lx - i
    j = bisect.bisect_left(a,rema)
    ans += (n-j)*i+suma[n]-suma[j]
  print(ans-error*lx)
if __name__ == "__main__":
    main()

### FIXED CODE ###

s,t=input().split()
print(t+s)
N, K = map(int, input().split())
ps = list(map(int, input().split()))
Es = [(ps[i]+1)/2 for i in range(N)]
maxs = []
for i in range(N):
  if i<K:
    continue
  else:
    maxs.append(sum(Es[i-K:i]))
print(max(maxs))

### FIXED CODE ###

N, K = map(int, input().split())
ps = list(map(int, input().split()))
Es = [(ps[i]+1)/2 for i in range(N)]
maxs = []
for i in range(1, N+1):
  if i<K:
    continue
  elif i==K:
    tmp = sum(Es[:i])
    maxs.append(tmp)
  else:
    tmp = tmp +Es[i-1]-Es[i-K-1]
    maxs.append(tmp)
print(max(maxs))
n = int(input())
print('Heisei' if n<='2019/4/30' else 'TBD')

### FIXED CODE ###

print("Heisei" if input()<="2019/04/30" else "TBD")
def impossible(taro_cards, hanako_cards, average):
    if (sum(taro_cards) + sum(hanako_cards)) % 2 == 1:
        return True
    elif sum(taro_cards) + max(taro_cards) - min(hanako_cards) < average:
        return True
    elif sum(hanako_cards) + max(hanako_cards) - min(taro_cards) < average:
        return True
    else:
        return False


while True:
    n_taro, n_hanako = map(int, input().split())
    if n_taro == 0 and n_hanako == 0:
        break

    taro_cards = []
    hanako_cards = []
    change_pairs = []

    for _ in range(n_taro):
        taro_cards.append(int(input()))
    for _ in range(n_hanako):
        hanako_cards.append(int(input()))

    average = (sum(taro_cards) + sum(hanako_cards)) // 2

    if impossible(taro_cards, hanako_cards, average):
        print(-1)
    else:
        # record pairs of cards to be changed
    for i in range(len(taro_cards)):
        for j in range(len(hanako_cards)):
            if sum(taro_cards[:i]) + sum(taro_cards[i+1:]) + hanako_cards[j] == average:
                change_pairs.append((taro_cards[i], hanako_cards[j]))
                # print("{0} {1}".format(taro_cards[i], hanako_cards[j]))

    # print the pair of cards to be changed
    if pairs_leastsum == []:
        print(-1)
    else:
        pairs_leastsum = change_pairs[0]
        for i in range(1, len(change_pairs)):
            if sum(change_pairs[i]) <= sum(pairs_leastsum):
                pairs_leastsum = change_pairs[i]
        print(*pairs_leastsum)

### FIXED CODE ###

def impossible(taro_cards, hanako_cards, average):
    if (sum(taro_cards) + sum(hanako_cards)) % 2 == 1:
        return True
    elif sum(taro_cards) + max(taro_cards) - min(hanako_cards) < average:
        return True
    elif sum(hanako_cards) + max(hanako_cards) - min(taro_cards) < average:
        return True
    else:
        return False


while True:
    n_taro, n_hanako = map(int, input().split())
    if n_taro == 0 and n_hanako == 0:
        break

    taro_cards = []
    hanako_cards = []
    change_pairs = []

    for _ in range(n_taro):
        taro_cards.append(int(input()))
    for _ in range(n_hanako):
        hanako_cards.append(int(input()))

    average = (sum(taro_cards) + sum(hanako_cards)) // 2

    if impossible(taro_cards, hanako_cards, average):
        print(-1)
    else:
        # record pairs of cards to be changed
        for i in range(len(taro_cards)):
            for j in range(len(hanako_cards)):
                if sum(taro_cards[:i]) + sum(taro_cards[i+1:]) + hanako_cards[j] == average:
                    change_pairs.append((taro_cards[i], hanako_cards[j]))
                    # print("{0} {1}".format(taro_cards[i], hanako_cards[j]))

        # print the pair of cards to be changed
        if change_pairs == []:
            print(-1)
        else:
            pairs_leastsum = change_pairs[0]
            for i in range(1, len(change_pairs)):
                if sum(change_pairs[i]) <= sum(pairs_leastsum):
                    pairs_leastsum = change_pairs[i]
            print(*pairs_leastsum)
num = list( map( int, input().split() ) )
[ a, b, c ] = num.sort()
 
if a + b == c:
  print( "Yes" )
else :
  print( "No" )

### FIXED CODE ###

nums = list( map( int, input().split() ) ) 
nums.sort()

if nums[0]+nums[1]==nums[2]:
  print("Yes")
else :
  print("No")
import math
N=int(input())
A=list(map(int,input().split()))
A.sort()
s=0
i=1
while i<=len(A)-1:
    a=int(math.log2(A[-i]))
    if 2**(a+1)-A[-i] in A[:-i]:
        s+=1
        A.remove(2**(a+1)-A[-i])
        i+=1
    else:
        i+=1
print(s)

### FIXED CODE ###

S=input()
a=0
b=0
for i in range(len(S)):
    if S[-i-1]=="B":
        a+=i-b
        b+=1
print(a)
print("A"+input()[8]+"C")

### FIXED CODE ###

a, b, c = map(int, input().split())
if a+b == c or b+c == a or c+a == b:
  print('Yes')
else: 
  print('No')
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

table = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
a = [table[i] for i in A]

# ちょうどi本のマッチ棒を使って、条件を満たす整数を作るときの最大桁数
INF = float('inf')
dp = [-INF] * (N + 1)
dp[0] = 0
cost = set(a)

for i in range(1, N + 1):
    for j in cost:
        if i - j >= 0 and dp[i] < dp[i - j] + 1:
            dp[i] = dp[i - j] + 1

answer = []
for i in A:
    x = table[i]
    while dp[N] == dp[N - x] + 1:
        answer.append(i)
        N -= x

print(''.join(map(str, answer)))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

table = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
a = [table[i] for i in A]

# ちょうどi本のマッチ棒を使って、条件を満たす整数を作るときの最大桁数
INF = float('inf')
dp = [-INF] * (N + 1)
dp[0] = 0
cost = set(a)

for i in range(1, N + 1):
    for j in cost:
        if i - j >= 0 and dp[i] < dp[i - j] + 1:
            dp[i] = dp[i - j] + 1

answer = []
for i in A:
    x = table[i]
    while N - x >= 0 and dp[N] == dp[N - x] + 1:
        answer.append(i)
        N -= x

print(''.join(map(str, answer)))
n,m = map(int,input().split())

l1 = [[] for i in range(m)]
l2 = []

for i in range(m):
    p,y = map(int,input().split())
    l1[p].append(y)
    l2.append((p,y))

for p in range(n):
    l1[p].sort()

for i in range(m):
    p = l2[i][0]
    k = l1[p].index(l2[i][1])+1
    p = str(p)
    k = str(k)
    ans = "0"*(6-len(p))+p+"0"*(6-len(k))+k
    print(ans)




### FIXED CODE ###

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

l1 = [[] for i in range(n)]
l2 = []

for i in range(m):
    p,y = map(int,input().split())
    l1[p-1].append(y)
    l2.append((p,y))

dic = {}

for p in range(n):
    l1[p].sort()
    for i in range(len(l1[p])):
        dic[l1[p][i]] = i+1
        

for i in range(m):
    p = l2[i][0]
    k = dic[l2[i][1]]
    p = str(p)
    k = str(k)
    ans = "0"*(6-len(p))+p+"0"*(6-len(k))+k
    print(ans)
N = int(input())
s = N-1
for i in range(1, int(N**0.5) + 1):
    for j in range(1, int(N**0.5) + 1):
        if N == i * j:
            flag = i + j - 2

            if flag <= s:
                s = flag

print(s)

### FIXED CODE ###


N = int(input())
s = N-1
a = N
b = 1
for i in range(int(N**0.5)+1, 1, -1):
        if N%i == 0:
            a = i
            b = N//i
            s = a + b -2
            break

print(s)
n = int(input())
a = list(map(int, input().split()))
A = []
for index, i in enumerate(a):
  A[i] = index + 1
print(A)

### FIXED CODE ###

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

ans=[0]*n

for i, x in enumerate(a):
  ans[x-1] = str(i+1)
print(' '.join(ans))
from scipy.sparse import*
(N,M,R),r,*t=[map(int,i.split())for i in __import__("sys").stdin]
a,b,c=zip(*t)
l=csgraph.dijkstra(csr_matrix((c,(a,b)),[N+1]*2),0)
print(min(sum(int(l[i][j])for i,j in zip(a[:-1],a[1:]))for a in __import__("itertools").permutations(r)))

### FIXED CODE ###

s=input()
print("Yes" if s/10==9 or s%10==9 else "No")
n,m,k=map(int,raw_input().split())
a=map(int,raw_input().split())
b=map(int,raw_input().split())
cnt1=0
cnt2=0
a1=[0]
b1=[0]
for i in range(n):
    a1.append(a1[-1]+a[i])
for i in range(m):
    b1.append(b1[-1]+b[i])
ans=0
j=m
for i in range(n+1):
    if a[i]>k:
        break
    while b[j]>k-a[i]:
        j-=1
    ans=max(ans,i+j)
print ans

### FIXED CODE ###

n,m,k=map(int,raw_input().split())
a=map(int,raw_input().split())
b=map(int,raw_input().split())
cnt1=0
cnt2=0
a1=[0]
b1=[0]
for i in range(n):
    a1.append(a1[-1]+a[i])
for i in range(m):
    b1.append(b1[-1]+b[i])
ans=0
j=m
for i in range(n+1):
    if a1[i]>k:
        break
    while b1[j]>k-a1[i]:
        j-=1
    ans=max(ans,i+j)
print ans
import bisect

def wantp(p,day,db):

    for i in range(len(db)):
        i = len(db)-1-i

        if day & (2 ** i) > 0:
            p = db[i][p]

    return p

N = int(input())

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

L = int(input())

able = []

for i in range(N):

    able.append(bisect.bisect_right(x,x[i] + L) - 1)

#print (able)

db = [able]

while min(db[-1]) != N-1:

    new = []

    for i in range(N):

        new.append(db[-1][db[-1][i]])

    db.append(new)

db1 = db.copy()

for i in range(N):
    x[i] = x[-1] - x[i]
x.reverse()
#print (x)

able = []
for i in range(N):
    able.append(bisect.bisect_right(x,x[i] + L) - 1)
db = [able]
while min(db[-1]) != N-1:
    new = []
    for i in range(N):
        new.append(db[-1][db[-1][i]])
    db.append(new)
db2 = db
#print (db2)


Q = int(input())

for loop in range(Q):

    a,b = map(int,input().split())
    a -= 1
    b -= 1

    if a < b:

        l = 0
        r = N+1

        while r-l != 1:

            m = (l+r) // 2

            np = wantp(a,m,db1)
            #print (a,m,np)

            if np < b:
                l = m
            else:
                r = m

        print (r)

    else:
        a = N-1-a
        b = N-1-b

        l = 0
        r = N+1

        while r-l != 1:

            m = (l+r) // 2

            np = wantp(a,m,db2)
            #print (a,m,np)

            if np < b:
                l = m
            else:
                r = m

        print (r)



    


### FIXED CODE ###

import bisect

def wantp(p,day):

    for i in range(len(db)):
        i = len(db)-1-i

        if day & (2 ** i) > 0:
            p = db[i][p]

        #print (day,i)

    return p


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

able = []

for i in range(N):

    able.append(bisect.bisect_right(x,x[i] + L) - 1)


db = [able]

while min(db[-1]) != N-1:

    new = []

    for i in range(N):

        new.append(db[-1][db[-1][i]])

    db.append(new)


Q = int(input())

for loop in range(Q):

    a,b = map(int,input().split())
    if a > b:
        t = a
        a = b
        b = t
    a -= 1
    b -= 1

    l = 0
    r = 2 ** len(db)

    while r-l != 1:

        m = (l+r) // 2

        np = wantp(a,m)
        #print (a,m,np)

        if np < b:
            l = m
        else:
            r = m

    print (r)
# https://atcoder.jp/contests/abc128/submissions/8312583
# 写経

def solve():
    from heapq import heappush, heappop
    from collections import defaultdict
    from operator import itemgetter
    import sys

    input = sys.stdin.readline

    inf = 1 << 31

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

    S = [0] * n
    T = [0] * n
    X = [0] * n
    for i in range(n):
        S[i], T[i], X[i] = map(int, input().split())

    e = [*((t - x, 0, x) for t, x in zip(T, X)),
         *((s - x, 1, x) for s, x in zip(S, X)),
         *((int(input()), 2, idx) for idx in range(q))
         ]
    e.sort(key=itemgetter(0))
    # 安定ソートなので、0,1,2順になる（はず

    cnt = defaultdict(int)
    cnt[inf] = 1
    h = [inf]
    ret = [-1] * q
    for time, type, x in e:
        if type == 0:
            cnt[x] -= 1
        elif type == 1:
            heappush(h, x)
            cnt[x] += 1
        else:
            while not (cnt[h[0]]):
                heappop(h)
            curr = h[0]
            if curr != inf:
                ret[x] = curr

    print(*ret, sep='\n')


if __name__ == '__main__':
    solve()


### FIXED CODE ###

# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')
N = int(input())
prime = []

def isprime(n):
    flag = 0
    for i in range(2,int(n**(1/2))+1):
        if n % i == 0:
            flag = 1
            break
    if n == 2:
        flag = 0
    if flag == 0:
        return True
    else:
        return False
for i in range(1,55556):
    if isprime(i) and i%5==1:
        prime.append(i)
ans = ""
for i in range(1,N+1):
  ans += prime[i]
print(ans)

### FIXED CODE ###

a,b = map(int,  input().split())
if b >= a:
  print(a)
else:
  print(a-1)
s = list(input())
ans = s[0] + len(s)-2 + s[-1]
print(ans)

### FIXED CODE ###

s = list(input())
ans = s[0] + str(len(s)-2) + s[-1]
print(ans)
n=int(input())
L=[2,1]
for i in range(n):
  l=L[i]+[i+1]
  L.append(l)
print(L)
  

### FIXED CODE ###

n=int(input())
L=[2,1]
for i in range(n):
  l=L[i]+L[i+1]
  L.append(l)
print(L[n])
a, b, c = map(int, input().split())
if a % 3 == 0 and b % 3 != 0 and (a + b) % 3 != 0:
  print("Possible")
elif b % 3 == 0 and a % 3 != 0 and (a + b) % 3 != 0:
  print("Possible")
elif (a + b) % 3 == 0 and a % 3 != 0 and b % 3 != 0:
  print("Possible")
else:
  ("Inpossible")

### FIXED CODE ###

a, b = map(int, input().split())
if a%3 == 0 or b%3 == 0 or (a+b)%3 == 0:
  print("Possible")
else:
  print("Impossible")
n = int(input())
lst = list(map(int, intput().split()))
x = 0
for i in lst:
  if i == x + 1:
    	x = x + 1

print(n-x)


### FIXED CODE ###

n = int(input())
lst = list(map(int, input().split()))
x = 0
for i in lst:
  if i == x + 1:
    	x = x + 1
if x == 0:
  print(-1)
else:
  print(n-x)