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

import sys
import heapq
import bisect

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

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

def LCM(a,b):
    return a * b // GCD(a,b)

def Eratosthenes(N):
    r = [True]*(N+1)
    r[0] = False
    r[1] = False
    i = 2
    while i*i<=N:
        if r[i]: 
            j = i
            while i*j<=N:
                prime[i*j]=False
                j+=1
        i+=1
    return(r)

def main():
    N,M,R = LI()
    r = LI()
    D = [[10**10]*N for _ in range(N)]
    for _ in range(M):
        A,B,C = LI()
        D[A-1][B-1] = C
        D[B-1][A-1] = C
    for i in range(N):
        D[i][i] = 0

    for i in range(N):
        for j in range(N):
            for k in range(N):
                D[i][j] = min(D[i][j],D[i][k]+D[k][j])

    ans = 10**11
    for x in range(R**R):
        order = [0] * R
        i = 0
        while x>0:
            order[i] = x%R
            i += 1
            x //= R
        for j in range(1,R):
            for k in range(j):
                if order[j]==order[k]:
                    break
            else:
                continue
            break
        else:
            ans_tmp = 0
            for j in range(R-1):
                ans_tmp += D[r[order[j]]-1][r[order[j+1]]-1]
            ans = min(ans,ans_tmp)
    return(ans)

if __name__ == "__main__":
    print(main())


### FIXED CODE ###

import sys
import itertools

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

def main():
    N,M,R = LI()
    rs = [int(x) -1 for x in sys.stdin.readline().split()]
    D = [[10**10]*N for _ in range(N)]
    for _ in range(M):
        A,B,C = LI()
        D[A-1][B-1] = C
        D[B-1][A-1] = C
    for i in range(N):
        D[i][i] = 0

    for k in range(N):
        for i in range(N):
            for j in range(N):
                D[i][j] = min(D[i][j],D[i][k]+D[k][j])

    ans = 10**11
    for trs in itertools.permutations(rs):
        tans = 0
        for i in range(R-1):
            tans += D[trs[i]][trs[i+1]]
        ans = min(ans,tans)
    
    return(ans)

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

N = int(input())

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

a = set(A)

con = 0

for i in a:
  n = A.count(i)
  if i > n:
    con += n
  elif i < n:
    con += (n - i)
    
print(con)

### FIXED CODE ###

from collections import Counter

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

a = Counter(A)

con = 0

for num in a.keys():
  time = a[num]
  if time > num:
    con += (time - num)
  elif num > time:
    con += time

print(con)
### BUGGY CODE ###

def main():
    N,K = map(int,input().split())
    P_list = tuple(map(int,input().split()))
    C_list = tuple(map(int,input().split()))

    max_sum=-10**9
    for i in range(N):
        m_sum=0
        k=i
        for j in range(K):
            m_sum += C_list[k]
            if m_sum > max_sum:
                max_sum=m_sum
            k=P_list[k]-1
    print(max_sum)
if __name__ == '__main__':
    main()

### FIXED CODE ###

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

ans=-10**18
for i in range(n):
    start,count=i,1
    val=c[start]
    while p[start]-1 != i:
        start = p[start]-1
        count += 1
        val += c[start]
    start = i
    if val > 0:
        a = (k//count-1)*val
        ans=max(a,ans)
        num=count+k%count
    else:
        a=0
        num=min(k,count)
    for _ in range(num):
        a += c[start]
        start=p[start]-1
        ans=max(a,ans)
print(ans)
### BUGGY CODE ###

# TODO D - Cake 123
# https://atcoder.jp/contests/abc123/tasks/abc123_d

X, Y, Z, K = map(int, raw_input().split())

A = [int(x) for x in raw_input().split()]
B = [int(y) for y in raw_input().split()]
C = [int(z) for z in raw_input().split()]

AB = list()

for x in range(X):
    for y in range(Y):
        AB.append(A[x] + B[y])

AB.sort(reverse=True)

N = min(X*Y, K)
ABC = list()

for xy in range(N):
    for z in range(Z):
        ABC.append(AB[xy] + C[z])

top_k = sorted(ABC, reverse=True)[:K]

for i in range(K):
    print '{:d}'.format(top_k[i])

### FIXED CODE ###

#abc123d
 
x,y,z,k=map(int,raw_input().split())
a=sorted(map(int,raw_input().split()),reverse=True)
b=sorted(map(int,raw_input().split()),reverse=True)
c=sorted(map(int,raw_input().split()),reverse=True)
 
ab=sorted([i+j for i in a for j in b],reverse=True)
res=sorted([ij+l for ij in ab[:k] for l in c],reverse=True)
for i in res[:k]:
	print i
### BUGGY CODE ###

s = input()
t = input()

def z_algorithm(s):

    a = [0] * len(s)
    i = 1
    j = 0
    a[0] = len(s)
    while i < len(s):
        while i + j < len(s) and s[j] == s[i+j]:
            j += 1
        a[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < len(s) and k + a[k] < j:
            a[i+k] = a[k]
            k += 1
        i += k
        j -= k
    return a

def solve(i, li):
    ans = 0
    while True:
        if i < 0 or len(li) <= i:
            break
        if visited[i]:
            break
        if li[i] < len(t):
            visited[i] = True
            break
        if li[i] >= len(t):
            visited[i] = True
            ans += 1
            i += len(t)
    return ans

#sを伸ばす
new_s = ""
while True:
    new_s += s
    if len(new_s) > len(t):
        s = new_s
        break

s = s*3
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans1 = 0
for i in range(len(li)):
    ans1 = max(ans1, solve(i, li))

s += s
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans2 = 0
for i in range(len(li)):
    ans2 = max(ans2, solve(i, li))

if ans1 == ans2:
    print(ans1)
else:
    print(-1)

### FIXED CODE ###

s = input()
t = input()

def z_algorithm(s):
    a = [0] * len(s)
    i = 1
    j = 0
    a[0] = len(s)
    while i < len(s):
        while i + j < len(s) and s[j] == s[i+j]:
            j += 1
        a[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < len(s) and k + a[k] < j:
            a[i+k] = a[k]
            k += 1
        i += k
        j -= k
    return a

def solve(i, li):
    ans = 0
    while True:
        if i < 0 or len(li) <= i or visited[i]:
            break
        if li[i] < len(t):
            visited[i] = True
            break
        if li[i] >= len(t):
            visited[i] = True
            ans += 1
            i += len(t)
    return ans

#sを伸ばす
new_s = s
while True:
    if len(new_s) > len(t):
        s = new_s
        break
    new_s += new_s

s = s*3
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans1 = 0
for i in range(len(li)):
    ans1 = max(ans1, solve(i, li))

s += s
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans2 = 0
for i in range(len(li)):
    ans2 = max(ans2, solve(i, li))

if ans1 == ans2:
    print(ans1)
else:
    print(-1)
### BUGGY CODE ###

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


### FIXED CODE ###

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

S=str(input())
N=int(len(S))
for j in range(int(len(S)/2)):
    S=S.replace("10","",1)
    S=S.replace("01","",1)
print(N-int(len(S)))

### FIXED CODE ###

S=input()
print(min(S.count("0"),S.count("1"))*2)
### BUGGY CODE ###

N, M = map(int, input().split())
PY = []
for i in range(M):
    PY.append(list(map(int, input().split())))
    
def kansu(a, ans):
    if a in ans:
        temp = int(a[6:])
        temp += 1
        temp = str(temp).zfill(6)
        b = a[:6] + temp
        response = kansu(b, ans)
    else:
        response = a
    return response
    
    
sort_PY = sorted(PY, key=lambda x: x[1])
ans = [""] * M
for i, j in enumerate(sort_PY):
    
    for k, l in enumerate(PY):
        if sort_PY[i][1] == PY[k][1]:
            index = k
        
    a = str(sort_PY[i][0]).zfill(6) + str(1).zfill(6)
    response = kansu(a, ans)
    ans[index] = response
for i in ans:
    print(i)

### FIXED CODE ###

N, M = map(int, input().split())
PY = []
for i in range(M):
    PY.append(list(map(int, input().split())) + [i])
    
PY.sort(key = lambda x:x[1])
PY.sort(key = lambda x:x[0])
    
bef = 0
state = 0
retstr = ''
triple = []
for i in PY:
    if (i[0] != bef):
        bef = i[0]
        state = 1
        triple.append([i[0], i[1], i[2], str(i[0]).rjust(6, '0') + str(state).rjust(6, '0')])
    else:
        state += 1
        triple.append([i[0], i[1], i[2], str(i[0]).rjust(6, '0') + str(state).rjust(6, '0')])
triple.sort(key = lambda x:x[2])
for i in triple:
    print(i[3])
### BUGGY CODE ###

#input
K = int(input())
S = str(input())

#output
# (o以外) o (o以外) o (f以外) f (何でも)

#こちらもmodで割った余り。maxが決まっていて、大きくない時はこちらが早い。
mod = pow(10, 9) + 7

n_ = 4 * pow(10, 6) + 1
fun = [1] * (n_+1)
for i in range(1, n_+1):
    fun[i] = fun[i-1] * i % mod
rev = [1] * (n_+1)
rev[n_] = pow(fun[n_], mod-2, mod)
for i in range(n_-1, 0, -1):
    rev[i] = rev[i+1] * (i+1) % mod
def cmb(n,r):
    if n <= 0 or r < 0 or r > n: return 0
    return fun[n] * rev[r] % mod * rev[n-r] % mod

#重複組み合わせはH(n, r) = cmb(n+r-1, r)

N = len(S)
answer = 0
for i in range(K+1):
    answer += pow(25, i, mod) * pow(26, K-i, mod) * cmb(N-1+i, N-1) % mod
print(answer % mod)

### FIXED CODE ###

#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

#input
K = int(input())
S = str(input())

#output
# (o以外) o (o以外) o (f以外) f (何でも)

#こちらもmodで割った余り。maxが決まっていて、大きくない時はこちらが早い。
mod = pow(10, 9) + 7

n_ = 5 * pow(10, 6)
fun = [1] * (n_+1)
for i in range(1, n_+1):
    fun[i] = fun[i-1] * i % mod
rev = [1] * (n_+1)
rev[n_] = pow(fun[n_], mod-2, mod)
for i in range(n_-1, 0, -1):
    rev[i] = rev[i+1] * (i+1) % mod
def cmb(n,r):
    if n < 0 or r < 0 or r > n: return 0
    return fun[n] * rev[r] % mod * rev[n-r] % mod

#重複組み合わせはH(n, r) = cmb(n+r-1, r)

L = len(S)
answer = 0
for i in range(L, L+K+1):
    answer += pow(25, i-L, mod) * pow(26, L+K-i, mod) * cmb(i-1, L-1)
    answer %= mod
print(answer)
### BUGGY CODE ###

n=int(input())
a=sorted([int(i) for i in input().split()])
m={}
for i in range(n):
    x=m.get(a[i],0)
    m[a[i]]=x+1
q=int(input())
b=[]
c=[]
for i in range(q):
    b,c=[int(i) for i in input().split()]
    x=m.get(b,0)
    y=m.get(c,0)
    m[b]=0
    m[c]=x+y
    print(sum(map(lambda x: x*m[x],m.keys())))


### FIXED CODE ###

n=int(input())
m={}
s=0
for i in input().split():
    i=int(i)
    x=m.get(i,0)
    m[i]=x+1
    s+=i
q=int(input())
for i in range(q):
    b,c=[int(i) for i in input().split()]
    x=m.get(b,0)
    y=m.get(c,0)
    m[b]=0
    m[c]=x+y
    s=s-(b*x)+(c*x)
    print(s)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
k, q = map(int, input().split())
d = list(map(int, input().split()))

query = []
for _ in range(q):
    query.append(list(map(int, input().split())))

def answer_query(n, x, m):
    l = [i%m for i in d]
    n -= 1
    zero = l.count(0)
    count = n // k
    zero_total = zero*count
    rem = n % k
    s = sum(l)
    total = s%m * count + x%m
    for i in range(rem):
        total += l[i]
        if l[i] == 0:
            zero_total += 1

    total //= m
    total += s//m * count

    print(n-total-zero_total)
for n, x, m in query:
    answer_query(n, x, m)


### FIXED CODE ###

import sys
input = sys.stdin.readline
k, q = map(int, input().split())
d = list(map(int, input().split()))
query = [None]*q
for i in range(q):
    query[i] = list(map(int, input().split()))

def answer_query(n, x, m):
    l = [m if i%m == 0 else i%m for i in d]
    count = n // k
    rem = n % k
    s = sum(l)
    total = s%m * count + x%m
    for i in range(rem):
        total += l[i]

    total //= m
    total += s//m * count

    print(n-total)


for n, x, m in query:
    answer_query(n-1, x, m)
### BUGGY CODE ###

import numpy as np
N, M = map(int, input().split())
A = np.array(list(map(int, input().split())))
A.sort()
A = A[::-1]

# B, Cで出てくる数字全部並べて最後にsortしてAの数だけ取れば良さそう？
D = []
for _ in range(M):
    b, c = map(int, input().split())
    tmp = [c for _ in range(b)]
    D.extend(tmp)
D = np.array(D)
D.sort()

if len(D) < len(A):
    tmp = np.array([0 for _ in range(len(A) - len(D))])
    D = np.append(tmp, D)
else:
    D = D[-len(A):]
print(np.maximum(D, A).sum())


### FIXED CODE ###

import numpy as np
N, M = map(int, input().split())
A = np.array(list(map(int, input().split())))
A.sort()

# B, Cで出てくる数字全部並べて最後にsortしてAの数だけ取れば良さそう？
BC = []
for _ in range(M):
    b, c = map(int, input().split())
    BC.append((b, c))
BC = sorted(BC, key=lambda x: -x[1])

D = []
n = 0
for b, c in BC:
    if n + b >= N:
        while len(D) < N:
            D.append(c)
        break
    else:
        for i in range(b):
            D.append(c)
        n += b

while len(D) < N:
    D.append(0)

print(np.maximum(D, A).sum())
### BUGGY CODE ###

from itertools import combinations

def main():
    EPS = 1e-8

    N, K, *XYC = map(int, open(0).read().split())
    PC = [(complex(x, y), c) for x, y, c in zip(*[iter(XYC)] * 3)]


    def intersection(A, r, B, s):
        D = B - A
        d = abs(D)

        cos_t = (d * d + r * r - s * s) / (2 * d * r)
        sin_t = max(1 - cos_t * cos_t, 0.0) ** 0.5

        R = r * complex(cos_t, sin_t)
        D /= d

        return (
            A + D * R,
            A + D * R.conjugate(),
        )


    def is_ok(T):
        for (p1, c1), (p2, c2) in combinations(PC, 2):
            q1, q2 = intersection(p1, T / c1, p2, T / c2)
            if K <= sum(1 for p, c in PC if c * abs(q1 - p) < T + EPS):
                return True
            if K <= sum(1 for p, c in PC if c * abs(q2 - p) < T + EPS):
                return True

        return any(K <= sum(1 for p, c in PC if c * abs(a - p) < T + EPS) for a, _ in PC)

    ng, ok = 0, 1000000
    for _ in range(100):
        md = (ng + ok) / 2
        if is_ok(md):
            ok = md
        else:
            ng = md

    print(ok)

main()

### FIXED CODE ###

from math import hypot
from collections import deque

N, K, *XYC = map(int, open(0).read().split())
XYC = list(zip(*[iter(XYC)] * 3))

Q = deque([(0, 0, 1000.0)])

ans = float("inf")
while Q:
    X, Y, r = Q.popleft()
    if ans * 0.9999995 > sorted(c * hypot(max(abs(X - x) - r, 0), max(abs(Y - y) - r, 0)) for x, y, c in XYC)[K - 1]:
        ans = min(ans, sorted(c * hypot(X - x, Y - y) for x, y, c in XYC)[K - 1])
        for dx, dy in [(-0.5, -0.5), (-0.5, 0.5), (0.5, -0.5), (0.5, 0.5)]:
            Q.append((X + dx * r, Y + dy * r, r / 2))

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

from fractions import gcd
from functools import reduce

MOD = 10**9+7

def lcm(x, y):
    return (x * y) // gcd(x, y)

n = int(input())
a = [int(_) for _ in input().split()]
LCM = reduce(lcm, a)

arr = [0] * n
for i in range(n):
    arr[i] = LCM // a[i]
print(sum(arr) % MOD)

### FIXED CODE ###

from fractions import gcd
from functools import reduce

MOD = 1000000007

def lcm(x, y):
    return (x * y) // gcd(x, y)

n = int(input())
a = [int(_) for _ in input().split()]
LCM = reduce(lcm, a)

arr = [LCM // _ for _ in a]
print(sum(arr) % MOD)
### BUGGY CODE ###

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


for i in range(n, m + 1):
    if m / i == 1:
        print(1)
        break
    if m % i == 0:
        print(int(m / i))
        break

### FIXED CODE ###

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

if n > 100:
    for i in range(p, 0, -1):
        if m % i == 0:
            print(i)
            break
else:
    for i in range(n, m + 1):
        if m % i == 0:
            print(int(m / i))
            break
### BUGGY CODE ###

from itertools import product

n = int(input())
def calc(i):
    xs = [a for a in range(1,int(i**0.5))]
    ys = [a for a in range(1,int(i**0.5))]
    zs = [a for a in range(1,int(i**0.5))]
    cnt = 0
    for x,y,z in list(product(xs,ys,zs)):
        if x**2+y**2+z**2+x*y+y*z+z*x == i:
            cnt += 1
    print(cnt)






for i in range(1, n+1):
    calc(i)

### FIXED CODE ###

n = int(input())
ans = [0 for _ in range(10050)]
for i in range(1,105):
    for j in range(1,105):
        for k in range(1,105):
            v = i*i+j*j+k*k+i*j+j*k+k*i;
            if v<10050:
                ans[v]+=1
for i in range(n):
    print(ans[i+1])
### BUGGY CODE ###

K, S = map(int, input().split())
cnt = 0

for X in range(K+1):
    for Y in range(K+1):
        Z = S - X - Y

        if X + Y > S:
            break
        elif Z <= K:
            if X + Y + Z == S:
                cnt +=1
        else:
            continue

print(cnt)

### FIXED CODE ###

K, S = map(int, input().split())
cnt = 0

for X in range(K+1):
    for Y in range(K+1):
        Z = S - X - Y
        if 0<=Z and Z<=K:
            cnt +=1

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

s = input()
count = 0
while True:
    m = len(s)
    s = s.replace('10','')
    count += m-len(s)
    n = len(s)
    s = s.replace('01','')
    count += n-len(s)
    if m == len(s):
        break
    n = len(s)
print(count)

### FIXED CODE ###

S = input()
a = []
for s in S:
    if not a:
        a.append(s)
        continue
    if s != a[-1]:
        a.pop()
    else:
        a.append(s)
print(len(S)-len(a))
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    s = "".join(input().split())
    q = int(input())
    queries = [list(input().split()) for _ in range(q)]
    for query in queries:
        if query[0] == "1":
            lst = list(s)
            lst.reverse()
            s = "".join(lst)
            continue
        if query[1] == "1":
            s = query[2] + s
        else:
            s = s + query[2]
    print(s)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    s = input().strip()
    q = int(input())
    queries = [input().split() for _ in range(q)]
    pre = []
    post = []
    flg = True
    for query in queries:
        if query[0] == "1":
            flg = not flg
            continue
        if query[1] == "1":
            if flg:
                pre.append(query[2])
            else:
                post.append(query[2])
        else:
            if flg:
                post.append(query[2])
            else:
                pre.append(query[2])
    pre.reverse()
    pre.append(s)
    pre.extend(post)
    s = "".join(pre)
    if not flg:
        s = s[::-1]
    print(s)


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

# coding: utf-8
import sys
import numpy as np

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

MOD = 998244353
N, A, B, K = lr()
answer = 0
# A * x + B * y = K
# nCx * nCy

def perm(n,k):
    if k > n or k < 0: return 0
    return fact[n] * fact_inv[n-k] % MOD

def cmb(n, k):
    if k < 0 or k > n: return 0 
    return fact[n] * fact_inv[k] % MOD * fact_inv[n-k] % MOD

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

U = 10 ** 6 # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)

for x in range(K//A+1):
    temp = K-A*x
    if temp%B != 0:
        continue
    y = temp // B
    answer += cmb(N, x) * cmb(N, y)
    answer %= MOD

print(answer % MOD)
# 

### FIXED CODE ###

# coding: utf-8
import sys
import numpy as np

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

MOD = 998244353
N, A, B, K = lr()
answer = 0
# A * x + B * y = K
# nCx * nCy

def cmb(n, k):
    if k < 0 or k > n: return 0 
    return fact_N * fact_inv[k] % MOD * fact_inv[n-k] % MOD

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

U = N + 100 # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)
fact_N = fact[N]

for x in range(N+1):
    temp = K-A*x
    if temp%B != 0:
        continue
    y = temp // B
    if y > N:
        continue
    if y < 0:
        break
    answer += cmb(N, x) * cmb(N, y)
    answer %= MOD

print(answer % MOD)
### BUGGY CODE ###

import sys
from operator import itemgetter
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
def main():
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while(e[0] > d):
			if cont == True:
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			else:
				mini = min(kouho)
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			cont = True
			if q < Q-1:
				q = q + 1
				d = int(inputs())
			else:
				flag = True
				q = q + 1
				break
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			cont = False
	for t in [None]*(Q-q):
		print(-1)
		
def sub():
	V = [list(map(int,inputs().split())) for p in [0]*N]
	M = [int(inputs()) for p in [0]*Q]
	V.sort(key = lambda x:(x[2],x[0],x[1]))
	for v in V:
		v[0] -= v[2]
		v[1] -= v[2] + 1
	for m in M:
		for n in range(N):
			if V[n][0] <=m and m <= V[n][1]:
				print(V[n][2])
				break
		else:
			print(-1)


if Q<1000000:
	sub()
else:
	main()

### FIXED CODE ###

import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				print(mini-(mini//1000000001)*1000000002)
			else:
				mini = min(kouho)
				print(mini-(mini//1000000001)*1000000002)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			if mini == e[2]:
				cont = False
	for t in [None]*(Q-q):
		print(-1)
main()