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

def solve():
	n, m = map(int, raw_input().split())
	to1 = []
	toN = []

	for i in range(m):
		x, y = map(int, raw_input().split())
		if x == 1:
			to1.append(y)
		if x == n:
			toN.append(y)
		if y == 1:
			to1.append(x)
		if y == n:
			toN.append(x)

	for i in range(n):
		if i in to1 and i in toN:
			print "POSSIBLE"
			return
			
	print "IMPOSSIBLE"

solve()

### FIXED CODE ###

from sets import Set

def solve():
	n, m = map(int, raw_input().split())
	to1 = Set()
	toN = Set()

	for i in range(m):
		x, y = map(int, raw_input().split())
		if x == 1:
			to1.add(y)
		if x == n:
			toN.add(y)
		if y == 1:
			to1.add(x)
		if y == n:
			toN.add(x)

	for i in range(n):
		if i in to1 and i in toN:
			print "POSSIBLE"
			return
			
	print "IMPOSSIBLE"

solve()
### BUGGY CODE ###

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

tmp = 0
MAX = 100000
prime = primes(MAX)
a = [0 for _ in range(MAX+1)]
for i in range(MAX+1):
    if i%2 == 0:
        continue
    elif i in prime and int((i+1)/2) in prime:
        a[i] = 1
#累積和
s = [0 for _ in range(MAX+2)]
for i in range(MAX+1):
    s[i+1] = s[i] + a[i]


Q = int(input())
for i in range(Q):
    l,r = map(int, input().split())
    print(s[r+1]-s[l])

### FIXED CODE ###

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

tmp = 0
MAX = 100000
prime = primes(MAX)
a = [0 for _ in range(MAX+1)]
for i in range(MAX+1):
    if i%2 == 0:
        continue
    elif i in prime and int((i+1)/2) in prime:
        a[i] = 1
#累積和
s = [0 for _ in range(MAX+2)]
for i in range(MAX+1):
    s[i+1] = s[i] + a[i]


Q = int(input())
for i in range(Q):
    l,r = map(int, input().split())
    print(s[r+1]-s[l])
### BUGGY CODE ###

import itertools
import sys
input = sys.stdin.readline

def main():
    D, G = map(int, input().split())
    spc_list = [[(i+1) * 100] + [int(v) for v in input().split()] for i in range(D)]
    max_scores = [spc[0] * spc[1] + spc[2] for spc in spc_list]
    min_q = float("inf")
    for q_list in itertools.permutations(list(range(D))):
        score = 0
        q_num = 0
        for q_idx in q_list:
            if score + max_scores[q_idx] < G:
                score += max_scores[q_idx]
                q_num += spc_list[q_idx][1]
            else:
                for _ in range(spc_list[q_idx][1]):
                    score += spc_list[q_idx][0]
                    q_num += 1
                    if score >= G:
                        break
                score += spc_list[q_idx][2]
            if score >= G:# or q_num > min_q:
                break
        if q_num < min_q:
            min_q = q_num
    print(min_q)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
import itertools
import sys
input = sys.stdin.readline

def main():
    D, G = map(int, input().split())
    spc_list = [[(i+1) * 100] + [int(v) for v in input().split()] for i in range(D)]
    max_scores = [spc[0] * spc[1] + spc[2] for spc in spc_list]
    min_q = float("inf")
    for q_list in itertools.permutations(list(range(D))):
        score = 0
        q_num = 0
        for q_idx in q_list:
            if score + max_scores[q_idx] < G:
                score += max_scores[q_idx]
                q_num += spc_list[q_idx][1]
            else:
                q_num += min(math.ceil((G-score) / spc_list[q_idx][0]), spc_list[q_idx][1])
                score = G
                """
                for _ in range(spc_list[q_idx][1]):
                    score += spc_list[q_idx][0]
                    q_num += 1
                    if score >= G:
                        break
                score += spc_list[q_idx][2]
"""
            if score >= G:
                break
        if q_num < min_q:
            min_q = q_num
    print(min_q)


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

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

A.sort()
B.sort()
C.sort()

def is_ok(arg, target, abc):
    if abc[arg] > target:
        return True
    else:
        return False

def bict(left, right, target, abc):

    while(right - left > 1):
        mid = (right + left)//2

        if is_ok(mid, target, abc):
            right = mid
        else:
            left = mid

    return right

cnt = 0
for a in A:
    b_min_index = bict(-1, N, a, B)
    for b_index in range(b_min_index,N):
        c_min_index = bict(-1, N ,B[b_index],C)
        c_num = N - c_min_index
        cnt += c_num

print(cnt)


### FIXED CODE ###


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

A.sort()
B.sort()
C.sort()

def is_ok(arg, target, abc):
    if abc[arg] >= target:
        return True
    else:
        return False

def is_ok2(arg, target, abc):
    if abc[arg] > target:
        return True
    else:
        return False


def bict(left, right, target, abc, jug):

    while(right - left > 1):
        mid = (right + left)//2

        if jug(mid, target, abc):
            right = mid
        else:
            left = mid

    return right

cnt = 0
for b in B:
    a_min_index = bict(-1, N, b, A, is_ok)
    c_min_index = bict(-1, N, b, C, is_ok2)
    temp = (a_min_index - 1 + 1) * (N - c_min_index)
    cnt += temp

print(cnt)
### BUGGY CODE ###

# ABC141 C - Attack Survival

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

P = []

for i in range(N):
    P.append(K)

for i in range(Q):
    A = int(input())
    for j in range(len(P)):
        if j != (A - 1):
            P[j] -= 1


for i in range(len(P)):
    if P[i] <= 0:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

# ABC141 C - Attack Survival

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

P = []

for i in range(N):
    P.append(K - Q)

for i in range(Q):
    P[int(input()) - 1] += 1

for i in range(len(P)):
    if P[i] <= 0:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

n = int(input())
cnt = 0
a = []
for i in range(n):
    a.append(int(input()))
set_ = set(a)
for j in set_:
    if a.count(j) % 2 == 1:
        cnt+=1
print(cnt)

### FIXED CODE ###

n = int(input())
a = set()
for i in range(n):
    tmp = int(input())
    if tmp in a:
        a.remove(tmp)
    else:
        a.add(tmp)
print(len(a))
### BUGGY CODE ###

import sys

input = sys.stdin.readline

N, W = map(int, input().split())
L = [list(map(int,input().split())) for i in range(N)]
dp = [[0] * (W + 1) for i in range(N + 1)]

for i in range(N):
  weight = L[i][0]
  value = L[i][1]
  for w in range(W + 1):
    if w >= weight:
      dp[i + 1][w] = max(dp[i][w],dp[i][w - weight] + value)
    else:
      dp[i + 1][w] = dp[i][w]
      
print(dp[-1][W])

### FIXED CODE ###

N, W = map(int, input().split())
L = sorted( [ [int(i) for i in input().split()] for _ in range(N) ] )

dp = [0] * (W + 1)
cnt = 0

for w, v in L:
    #重さを足し合わせていき合計を求める
    cnt = cnt + w
    #W=重さの制約とこれまでの重さの合計のうち、
    #小さい方から品物iの重さまで、逆順にfor文を回す
    ##3,8-5,...15-7
    for i in range(min(cnt, W), w - 1, -1):
        #同じ重さでより価値が高い組み合わせがあれば価値を更新する
        ## w < Wの制約があり、i - wとその値を参照してから更新しているため、
        ## Wの制約を満たさない値を持つことはない
        ### 方法上、持ち得ない重さに持ち得ない値がつくことがあるが、
        ### それらが解 = 最大値になることはない
        ### (解を求める過程でついでに足されたり足されなかったりするだけなので)
        if dp[i] < dp[i - w] + v:
            dp[i] = dp[i - w] + v

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

n=int(input())
a=(input().split())
a1=[]
for i in range(n):
    a1.append(int(a[i]))
    
str1=""
for i in range(n):
    for ii in range(n):
        if i+1 == int(a[ii]):
            str1=str1 + " " +str(ii+1)
            break
print(str1)

### FIXED CODE ###

n=int(input())
a=(input().split())
a1={}
for i in range(n):
    a1[(a[i])]=i+1
str1=""
for i in range(n):
    print(str(a1[str(i+1)]),end=" ")
print()
### BUGGY CODE ###

k=input()
n=len(k)
cnt=9
def lunlun(x):
    flag=True
    x=str(x)
    for num in range(len(x)-1):
        a=x[num]
        b=x[num+1]
        if abs(int(a)-int(b))>1:
            flag=False
            break
    return flag
i=9
if n==1:
    print(k)
else:
    while cnt!=k:
        i+=1
        if lunlun(i):
            cnt+=1
    print(i)


### FIXED CODE ###

#abc161 d 
k=int(input())

lunlun=[1,2,3,4,5,6,7,8,9]

def lunlun_generate(p):
    last=p%10
    if last-1>=0:
        yield p*10+last-1
    yield p*10+last
    if last+1<=9:
        yield p*10+last+1


p=0
while len(lunlun)<k:
    for new_lunlun in lunlun_generate(lunlun[p]):#３つ目のyieldが判定されるとfor文を抜ける
        lunlun.append(new_lunlun)
    p+=1
    
print(lunlun[k-1])
### BUGGY CODE ###

import copy
import sys
input=sys.stdin.readline

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

new_a = [0 for i in range(n)]
for i in range(k):
    for j in range(n):
        new_a[max(j-a[j], 0)] += 1
        if j+a[j]+1 < n:
            new_a[j+a[j]+1] += -1
    for j in range(n):
        if j > 0:
            new_a[j] += new_a[j-1]
    if new_a == [n for i in range(n)]:
        a = copy.copy(new_a)
        break
    a = copy.copy(new_a)
    new_a = [0 for i in range(n)]

print(" ".join(list(map(str, a))))

### FIXED CODE ###

import copy
import sys
input = sys.stdin.readline

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

new_a = [0 for i in range(n)]
for i in range(k):
    for j in range(n):
        new_a[max(j-a[j], 0)] += 1
        if j+a[j]+1 < n:
            new_a[j+a[j]+1] += -1
    for j in range(n):
        if j > 0:
            new_a[j] += new_a[j-1]
    if new_a == [n for i in range(n)]:
        a = copy.copy(new_a)
        break
    a = copy.copy(new_a)
    new_a = [0 for i in range(n)]

print(" ".join(list(map(str, a))))
### BUGGY CODE ###

import collections
from collections import defaultdict
import math
import numpy as np
import re
import itertools


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

x = 1

num = math.floor(n/b)

if num == 0:
    x = n
    print(math.floor(a*x/b)-a*math.floor(x/b))
    exit()
else:
    ans = 0
    for i in range(1,num+1):
        x = b*i-1
        ans = max(ans,math.floor(a*x/b)-a*math.floor(x/b))
print(ans)


### FIXED CODE ###


import math



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

x = 1

num = math.floor(n/b)

if num == 0:
    x = n
    print(math.floor(a*x/b)-a*math.floor(x/b))
    exit()
if num >= 100000:
    print(b-1)
    exit()
else:
    ans = 0
    for i in range(1,num+1):
        x = b*i-1
        ans = max(ans,math.floor(a*x/b)-a*math.floor(x/b))
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    a = tuple(map(int,input().split()))
    b = tuple(map(int,input().split()))

    dg = 10**10

    dp = [[10**5]*n for i in range(2**n)]

    new = set([])
    for i in range(n):
        s = (1<<i)
        dp[s][i] = i
        new.add(s*dg+i)
    

    for k in range(n-1):
        tank = set([])
        if len(new) == 0:
            break
        for popelt in new:
            s,idx = popelt//dg,popelt%dg
            if (k-idx)%2 == 0:
                fr = a[idx]
            else:
                fr = b[idx]
            cnt = 0
            for j in range(n):
                if (s>>j)&1 == 0:
                    if (j-k)%2 == 1:
                        val = a[j]
                    else:
                        val = b[j]
                    if val >= fr:
                        dp[s+(1<<j)][j] = min(dp[s+(1<<j)][j],dp[s][idx]+j-cnt)
                        tank.add((s+(1<<j))*dg + j)
                else:
                    cnt += 1
            
        new = tank
    
    res = min(dp[2**n-1])

    if res == 10**5:
        print(-1)
    else:
        print(res)





if __name__ == '__main__':
    main()

### FIXED CODE ###



def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = tuple(map(int,input().split()))
    b = tuple(map(int,input().split()))

    dg = 20

    pp = 20

    dp = [10**5]*(10**7)

    new = set([])
    for i in range(n):
        s = (1<<i)
        dp[s*pp+i] = i
        new.add(s*dg+i)

    for k in range(n-1):
        tank = set([])
        if len(new) == 0:
            break
        for popelt in new:
            s,idx = popelt//dg,popelt%dg
            if (k-idx)%2 == 0:
                fr = a[idx]
            else:
                fr = b[idx]
            cnt = 0
            for j in range(n):
                if (s>>j)&1 == 0:
                    if (j-k)%2 == 1:
                        val = a[j]
                    else:
                        val = b[j]
                    if val >= fr and dp[(s+(1<<j))*pp+j] > dp[s*pp+idx]+j-cnt:
                        dp[(s+(1<<j))*pp+j] = dp[s*pp+idx]+j-cnt
                        tank.add((s+(1<<j))*dg + j)
                else:
                    cnt += 1
        new = tank
    
    res = 10**5
    s = (2**n-1)*pp
    for i in range(n):
        if res > dp[s+i]:
            res = dp[s+i]
    if res == 10**5:
        print(-1)
    else:
        print(res)


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

n = int(input())
a = list(map(int, input().split()))
i = 0
ans = 0
while(i < n - 1):
    j = 1
    while(i + j < n):
        ans += (a[i] * a[i+j]) % (10**9 + 7)
        j+=1
    i+=1
ans = ans % (10**9 + 7)
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
i = 0
tmp = 0
tmpura = 0
while(i < n):
    tmp += a[i]
    i+=1
tmp=tmp **2
i = 0
while (i < n):
    tmpura += a[i]**2
    i+=1
tmpura=tmpura
ans = ((tmp - tmpura)//2)%(10**9+7)
print(ans)
### BUGGY CODE ###

from bisect import bisect, bisect_left

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

def search_1(start):
	return bisect(x, x[start] + l) - 1

route = [[] for _ in range(n)]

i = 0 # 親の位置
for i in range(n - 1):
	if route[i] == []:
		j = search_1(i) # カーソルの位置
		num = 1 # 何日目の場所か
		route[i].append(j)
		if route[j] == []:
			route[j] = (i, num)
		else: # 既に他の親が通っている
			route[i] += route[route[j][0]][route[j][1]:]
			continue
		while j < n - 1:
			j = search_1(j)
			num += 1
			route[i].append(j)
			if route[j] == []:
				route[j] = (i, num)
			else: # 既に他の親が通っている
				route[i] += route[route[j][0]][route[j][1]:]
				break
	else:
		continue

# print(route)

def search_2(start, goal):
	if type(route[start]) == type([]):
		return bisect_left(route[start], goal) + 1
	else:
		return bisect_left(route[route[start][0]][route[start][1]:], goal) + 1



q = int(input())
for _ in range(q):
	a, b = map(int, input().split())
	if a > b:
		a, b = b, a
	print(search_2(a - 1, b - 1))


### FIXED CODE ###

from bisect import bisect

n = int(input())
x = list(map(int, input().split()))
l = int(input())
q = int(input())

#r[i][j]: jから(2**i)日で行ける右端
r = [[i for i in range(n)] for _ in range(18)]
for j in range(n):
	r[0][j] = bisect(x, x[j]+l) - 1
for i in range(1, 18):
	for j in range(n):
		r[i][j] = r[i-1][r[i-1][j]]

def search(x, y):
	res = 0
	cur = x
	while True:
		for i in range(18):
			if r[i][cur] >= y:
				if i == 0:
					return res+1
				cur = r[i-1][cur]
				res += 1 << (i-1) 
				break

for _ in range(q):
	a, b = map(int, input().split())
	print(search(min(a, b)-1, max(a, b)-1))
### BUGGY CODE ###

import numpy as np

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

D = np.zeros((C,C), dtype=int)

for i in range(C):
    D[i] = np.array(input().split())

c = np.zeros((N,N), dtype=int)

for i in range(N):
    c[i] = np.array(input().split())

c -= 1

res = 1000*N*N

for c1 in range(C):
    for c2 in range(C):
        for c3 in range(C):
            if c1 == c2 or c2 == c3 or c3 == c1:
                continue
            score = 0
            for i in range(N):
                for j in range(N):
                    if (i + j)%3 == 0:
                        cc = c1
                    if (i + j)%3 == 1:
                        cc = c2
                    if (i + j)%3 == 2:
                        cc = c3

                    score += D[c[i][j]][cc]

            if res > score:
                res = score

print(res)



### FIXED CODE ###

from itertools  import product, permutations

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

D = [list(map(int, input().split())) for _ in range(C)]

c = [list(map(lambda x: int(x)-1, input().split())) for _ in range(N)]

res = 1000*N*N

cnt = [[0]*C for _ in range(3)]


for i,j in product(range(N), range(N)):
    cnt[(i + j)%3][c[i][j]] += 1

for c1, c2, c3 in permutations(range(C), 3):
    score = 0
    for cc, cn in enumerate(cnt[0]):
        score += cn*D[cc][c1]
    for cc, cn in enumerate(cnt[1]):
        score += cn*D[cc][c2]
    for cc, cn in enumerate(cnt[2]):
        score += cn*D[cc][c3]
    if res > score:
        res = score

print(res)
### BUGGY CODE ###

S = input()


MOD = 10**9 + 7

# time complexity: O(|S|)
def dp(S):
    dp = [[0] * 4 for _ in range(len(S) + 1)]
    dp[len(S)][3] = 1
    for i in range(len(S))[::-1]:
        dp[i][3] = 3 * dp[i + 1][3] if S[i] == "?" else dp[i + 1][3]
        dp[i][3] %= MOD
        if S[i] == "?":
            dp[i][0] = (3 * dp[i + 1][0] + dp[i + 1][1]) % MOD
            dp[i][1] = (3 * dp[i + 1][1] + dp[i + 1][2]) % MOD
            dp[i][2] = (3 * dp[i + 1][2] + dp[i + 1][3]) % MOD
        else:
            dp[i][0] = (dp[i + 1][0] + int(S[i] == "A") * dp[i + 1][1]) % MOD
            dp[i][1] = (dp[i + 1][1] + int(S[i] == "B") * dp[i + 1][2]) % MOD
            dp[i][2] = (dp[i + 1][2] + int(S[i] == "C") * dp[i + 1][3]) % MOD
    print(dp[0][0])


# time complexity: O(|S|)
def focus_on_B(S):
    cuml = {"A": [], 
            "C": [],
            "?": []}
    current_nums = {"A": 0,
                    "C": 0,
                    "?": 0}
    for char in S:
        if char in cuml.keys():
            current_nums[char] += 1
        for key in cuml.keys():
            cuml[key].append(current_nums[key])
    assert len(cuml['A']) == len(S)

    # num_combinations[i]: i番目をBとした時に、可能な組み合わせの数
    num_combinations = [0] * len(S)
    for i in range(1, len(S) - 1):
        if S[i] in {"B", "?"}:
            A_L = cuml["A"][i-1]
            Q_L = cuml["?"][i-1]
            C_R = cuml["C"][-1] - cuml["C"][i]
            Q_R = cuml["?"][-1] - cuml["?"][i]
            num_combinations[i] = (A_L * 3**Q_L + Q_L * int(3**(Q_L - 1)))\
                                * (C_R * 3**Q_R + Q_R * int(3**(Q_R - 1)))
            num_combinations[i] %= MOD
        else:
            continue
    print(sum(num_combinations) % MOD)

focus_on_B(S)


### FIXED CODE ###

S = input()

MOD = 10**9 + 7
dp = [[0] * 4 for _ in range(len(S) + 1)]
dp[len(S)][3] = 1
for i in range(len(S))[::-1]:
    dp[i][3] = 3 * dp[i + 1][3] if S[i] == "?" else dp[i + 1][3]
    dp[i][3] %= MOD
    if S[i] == "?":
        dp[i][0] = (3 * dp[i + 1][0] + dp[i + 1][1]) % MOD
        dp[i][1] = (3 * dp[i + 1][1] + dp[i + 1][2]) % MOD
        dp[i][2] = (3 * dp[i + 1][2] + dp[i + 1][3]) % MOD
    else:
        dp[i][0] = (dp[i + 1][0] + int(S[i] == "A") * dp[i + 1][1]) % MOD
        dp[i][1] = (dp[i + 1][1] + int(S[i] == "B") * dp[i + 1][2]) % MOD
        dp[i][2] = (dp[i + 1][2] + int(S[i] == "C") * dp[i + 1][3]) % MOD
print(dp[0][0])
### BUGGY CODE ###

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

l = []
for i in range(n-2):
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      t = s[i]+s[j]+s[k]
      if t not in l: l.append(t)
print(len(l))

### FIXED CODE ###

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

# 3桁の番号を作るにあたり、文字列から抽出して作るのではなく、000〜999までの組み合わせが存在するかを確認する。
ans = 0
for i in range(10):
  a = s.find(str(i))
  for j in range(10):
    b = s.find(str(j), a+1) # aの取得位置の次から検索を行う
    for k in range(10):
      c = s.find(str(k), b+1) # bの取得位置の次から検索を行う
      if a == -1 or b == -1 or c == -1: continue
      else: ans += 1
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
X = [input() for _ in range(Q)]

ans = S
r = 0  # r=0: order, r=1: reverse
for i in range(Q):
    q, *x = X[i].split()
    if q == "1":
        r = abs(r - 1)
    else:
        f, c = x
        if (r == 0 and f == "1") or (r == 1 and f == "2"):
            ans = c + ans
        else:
            ans += c
            
print(ans if r == 0 else ans[::-1])


### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())
X = [input() for _ in range(Q)]

ans = deque(S)
r = 0  # r=0: order, r=1: reverse
for i in range(Q):
    q, *x = X[i].split()
    if q == "1":
        r = abs(r - 1)
    else:
        f, c = x
        if (r == 0 and f == "1") or (r == 1 and f == "2"):
            ans.appendleft(c)
        else:
            ans.append(c)
            
print("".join(ans) if r == 0 else "".join(ans)[::-1])
### BUGGY CODE ###

import math
n = int(input())
res = 0
for i in range(1,n+1):
  for j in range(1,n+1):
    for k in range(1,n+1):
      res += math.gcd(math.gcd(i,j),k)
print(res)


### FIXED CODE ###

import math
n = int(input())
res = 0
for i in range(1,n+1):
  for j in range(1,n+1):
    for k in range(1,n+1):
      res += math.gcd(math.gcd(i,j),k)
print(res)
### BUGGY CODE ###

n = int(input())
nn = 0

if n >= 357:
    for i in range(357,n+1):
        s = str(i)
        if '3' in s and '5' in s and '7' in s:
            if ('0' in s or '1' in s or '2' in s or '4' in s or '6' in s or '8' in s or '9' in s) is False:
                #print(i)
                nn += 1
print(nn)

### FIXED CODE ###

def nextn(n):
    if n == 0:
        return 3
    elif n % 10 == 3:
        return n+2
    elif n % 10== 5:
        return n+2
    elif n % 10 ==7:
        return nextn(n//10)*10 + 3

N = int(input())
n = 357
ans = 0
while n <= N:
    s = str(n)
    a = [False,False,False]
    for c in s:
        if c == '3':
            a[0] = True
        elif c == '5':
            a[1] = True
        elif c == '7':
            a[2] = True
        else:
            print(s)
    if all(a):
        ans += 1
    n = nextn(n) 
print(ans)
### BUGGY CODE ###

import heapq
N,Q = list(map(int, input().split()))

S,T,X = [],[],[]

Ev = []
for _ in range(N):
  s,t,x = list(map(int, input().split())) 
  Ev.append((s-x,True,x))
  Ev.append((t-x,False,x))
"""
2 5 6
5 -1
4 2
3 3
2 4
1 5
0 -1
"""
Ev.sort()
#print(Ev)
# C++のSetはminもO(logN)で取れるが、Pythonは無理。
# setとheapqを併用すると計算量が実現できる。
h = []
closed = set()
eidx = 0
for i in range(Q):
  # dはsortedでinputされる。
  d = int(input())
  #Query.append(d)
  while eidx < 2*N and Ev[eidx][0] <= d:
    #pop
    t,e,x = Ev[eidx]
    eidx += 1
    if e:
      heapq.heappush(h, x)
      closed.add(x)
    else:
      closed.remove(x)
      
  # heqpqの最小値がsetに含まれている間、捨て続ければ、setの要素とheapqの要素が一致する
  while h and h[0] not in closed:
    heapq.heappop(h)
    
  # assert( len(h) == len(set) )
  if h:
    print(h[0])
  else:
    print(-1)


### FIXED CODE ###

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

S,T,X = [],[],[]

Ev = []
for _ in range(N):
  s,t,x = map(int, input().split())
  Ev.append((s-x,True,x))
  Ev.append((t-x,False,x))
"""
2 5 6
5 -1
4 2
3 3
2 4
1 5
0 -1
"""
Ev.sort()
#print(Ev)
# C++のSetはminもO(logN)で取れるが、Pythonは無理。
# setとheapqを併用すると計算量が実現できる。
h = []
closed = set()
eidx = 0
for i in range(Q):
  # dはsortedでinputされる。
  d = int(input())
  #Query.append(d)
  while eidx < 2*N and Ev[eidx][0] <= d:
    #pop
    t,e,x = Ev[eidx]
    eidx += 1
    if e:
      heapq.heappush(h, x)
      closed.add(x)
    else:
      closed.remove(x)
      
  # heqpqの最小値がsetに含まれている間、捨て続ければ、setの要素とheapqの要素が一致する
  while h and h[0] not in closed:
    heapq.heappop(h)
    
  # assert( len(h) == len(set) )
  if h:
    print(h[0])
  else:
    print(-1)