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

import sys
def main():
    input = sys.stdin.readline
    s = input()[:-1]
    t = input()[:-1]
#    S = "abcdefghijklmnopqrstuvwxyz"
    A = [[] for k in range(26)]
    for k in range(len(s)):
        A[ord(s[k])-97] += [k+1]
    ans = 0
    now = 0
    for k in range(len(t)):
        a = ord(t[k]) - 97
        if len(A[a]) == 0:
            print(-1)
            exit(0)
        if A[a][-1] <= now:
            ans += len(s)
            now = A[a][0]
        else:
            for l in range(len(A[a])):
    #            print(A[S.index(t[k])][l]>now)
                if A[a][l] > now:
                    now = A[a][l]
                    break
    print(ans+now)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from bisect import bisect_right as bisect
def main():
    input = sys.stdin.readline
    s = input()[:-1]
    t = input()[:-1]
#    S = "abcdefghijklmnopqrstuvwxyz"
    A = [[] for k in range(26)]
    for k in range(len(s)):
        A[ord(s[k])-97] += [k+1]
    ans = 0
    now = 0
    for k in range(len(t)):
        a = ord(t[k]) - 97
        if len(A[a]) == 0:
            print(-1)
            exit(0)
        if A[a][-1] <= now:
            ans += len(s)
            now = A[a][0]
        else:
            now = A[a][bisect(A[a],now)]
    print(ans+now)

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

import sys, collections
n = int(input())
uq = []
chk = {}
for x in sys.stdin.readlines():
    x = x.rstrip()
    tmp = collections.Counter(sorted(x))
    h = ''
    for i in tmp:
        h += i + str(tmp[i])
    if h not in uq:
        uq.append(h)
    else:
        if h not in chk:
            chk.setdefault(h, 1)
        chk[h] += 1
ans = 0
for x in chk:
    ans += chk[x]*(chk[x]-1)//2
print(ans)


### FIXED CODE ###

import sys, collections
n = int(input())
uq = ["".join(sorted(x.rstrip())) for x in sys.stdin.readlines()]
chk = collections.Counter(uq)
ans = 0
for x in chk:
    if chk[x] != 1:
        ans += chk[x]*(chk[x]-1)//2
print(ans)
### BUGGY CODE ###

import bisect
import sys
input = sys.stdin.readline
n = int(input())
l = sorted([int(i) for i in input().split()])
ans = 0
for i in range(1,n-1):
    for j in range(i+1,n):
        if l[j] - l[i] >= l[i-1]:
            break
        elif i - bisect.bisect_right(l,(l[j]-l[i])) > 0:
            ans += i - bisect.bisect_right(l,(l[j]-l[i]))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
l = sorted([int(i) for i in input().split()])
ans = 0
for i in range(1,n-1):
    tmp=0
    for j in range(i+1,n):
        if l[j] - l[i] >= l[i-1]:
            break
        else:
            for k in range(tmp,i):
                if l[tmp] > l[j]-l[i]:
                    ans += i-tmp
                    break
                elif l[k] > l[j]-l[i]:
                    tmp = k
                    ans += i-tmp
                    break
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
g=[0]*60
mod=10**9+7
for i in range(n):
    for j in range(60):
        if (a[i]>>j)&1==1:
            g[j]+=1

cnt=0
for i in range(60):
    now=g[i]
    cnt+=now*(n-now)*(2**i)
    cnt%=mod

print(cnt)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
g=[0]*60
mod=10**9+7
for i in range(n):
    for j in range(60):
        if (a[i]>>j)&1==1:
            g[j]+=1

cnt=0
for i in range(60):
    now=g[i]
    cnt+=now*(n-now)*(2**i)
    cnt%=mod

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

n = int(input())
c = input()
#from collections import Counter
#print(min([i for i in Counter(list(c)).values()]))

cnt = 0
loc = 0
while True:
	if c[loc] == 'W':
		rloc = c.rfind('R')
		if rloc < loc:
			break
		else:
			cnt += 1
			lc = list(c)
			lc[rloc] = 'W'
			c = ''.join(lc)
	loc += 1
	if loc == n:
		break
	#print(c,cnt)
print(cnt)

### FIXED CODE ###

n = int(input())
c = input()
rl = [ i for i,_ in enumerate(c) if _ == 'R' ]

cnt = 0
loc = 0
rid = -1
while True:
	try:
		if c[loc] == 'W':
			rloc = rl[rid]
			rid -= 1
			if rloc < loc:
				break
			else:
				cnt += 1
		loc += 1
		if loc == n:
			break
		#print(c,cnt)
	except:
		break
print(cnt)
### BUGGY CODE ###

import bisect
s = input()
s_li = list(s)
ma = {}
for i,each_s in enumerate(s_li):
    if each_s not in ma:
        ma[each_s] = [i]
    else:
        ma[each_s].append(i)
t = input()
t_li = list(t)
#print(ma,s_li,t_li)

repeat_count = 1
last_index = -1
for tt in t_li:
    if tt not in ma:
        print(-1)
        exit()
    tmp_li = ma[tt]
    #print(tmp_li)

    lee = len(s_li)
    add_li = [ii+lee for ii in tmp_li]
    new_li = tmp_li + add_li
    bi = bisect.bisect_left(new_li, last_index+1)
    min_index = new_li[bi]
    #print(new_li,last_index+1,min_index,'min')
    if min_index>= lee:
        repeat_count += 1
        min_index -= lee
    last_index = min_index
    #print(last_index,'last')
print(lee*(repeat_count-1)+last_index+1)

### FIXED CODE ###

import bisect
s = input()
s_li = list(s)
ma = {}
for i,each_s in enumerate(s_li):
    if each_s not in ma:
        ma[each_s] = [i]
    else:
        ma[each_s].append(i)
t = input()
t_li = list(t)
#print(ma,s_li,t_li)

repeat_count = 0
last_index = -1
for tt in t_li:
    if tt not in ma:
        print(-1)
        exit()
    tmp_li = ma[tt]
    #print(tmp_li)

    lee = len(s_li)
    #add_li = [ii+lee for ii in tmp_li]
    #new_li = tmp_li + add_li
    #bi = bisect.bisect_left(new_li, last_index+1)
    bi = bisect.bisect_left(tmp_li, last_index+1)
    #print(bi,len(tmp_li),'bi',tmp_li,last_index,'last_index')
    if bi>= len(tmp_li):
        repeat_count += 1
        min_index = tmp_li[0]
    else:
        min_index = tmp_li[bi]
    #print(new_li,last_index+1,min_index,'min')
    #if min_index>= lee:
    #    repeat_count += 1
    #    min_index -= lee
    last_index = min_index
    #print(repeat_count,'repeat')
    #print(last_index,'last')
print(lee*(repeat_count)+last_index+1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)


def main():
    n, q = map(int, input().split())

    edges = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)

    operations = [0] * n
    for i in range(q):
        p, x = map(int, input().split())
        operations[p-1] += x

    counter = [-1] * n

    def calculate(p, i, v):
        total = operations[i] + v
        for c in edges[i]:
            if c != p:
                calculate(i, c, total)
        counter[i] = total

    calculate(-1, 0, 0)
    print(*counter)


main()

### FIXED CODE ###

from collections import deque


def main():
    n, q = map(int, input().split())

    edges = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)

    operations = [0] * n
    for i in range(q):
        p, x = map(int, input().split())
        operations[p-1] += x

    counter = [-1] * n
    d = deque([(-1, 0, 0)])
    while len(d) > 0:
        p, i, v = d.pop()
        total = operations[i] + v
        for c in edges[i]:
            if c != p:
                d.append((i, c, total))
        counter[i] = total

    print(*counter)


main()
### BUGGY CODE ###

import sys
INF = 1e9 + 5
def solve(n, k, arr):
    dp = [INF] * n
    dp[0] = 0
    for i, _ in enumerate(arr):
        for j in range(i+1, i+k+1):
            if j < n:
                dp[j] = min(dp[j], dp[i] + abs(arr[j]-arr[i]))
    return dp[-1]

if __name__ == "__main__":
    f = sys.stdin
    fo = sys.stdout
    n, k = map(int, f.readline().split())
    arr = list(map(int, f.readline().split()))
    result = solve(n, k, arr)
    print(result)


### FIXED CODE ###

import sys
INF = 1e9 + 5
def solve(n, k, ls):
    dp = [0] * n
    dp[1] = abs(ls[0]-ls[1])
    for i in range (2,n):
        dp[i] = min(abs(ls[i] - ls[j]) + dp[j] for j in range(max(0,i-k),i))
    return dp[-1]

if __name__ == "__main__":
    f = sys.stdin
    fo = sys.stdout
    n, k = map(int, f.readline().split())
    arr = list(map(int, f.readline().split()))
    result = solve(n, k, arr)
    print(result)
### BUGGY CODE ###

"""
def gcd(a, b ):
    if a < b:
        a, b = b, a
    while a % b != 0:
        a, b = b, a % b
    return b
"""
import math as f


K = int(input())
result = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            result += f.gcd(f.gcd(i, j), k)
print(result)

### FIXED CODE ###

"""
def gcd(a, b ):
    if a < b:
        a, b = b, a
    while a % b != 0:
        a, b = b, a % b
    return b
"""
import math as f


K = int(input())
result = 0
for i in range(1,K+1):
    for j in range(1,i+1):
        for k in range(1,j+1):
            if i == j == k:
                result += f.gcd(f.gcd(i, j), k)
            elif i == j or j == k or k == i:
                result += 3 * f.gcd(f.gcd(i, j), k)
            else:
                result += 6 * f.gcd(f.gcd(i, j), k)

print(result)
### BUGGY CODE ###

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

import fractions
math = fractions
table = {}  ## (start, end) => gcd

for i in range(0, n):
    if i > 0:
        gcd = aa[0]
        for j in range(0, i):
            gcd = math.gcd(gcd, aa[j])
        table[(0, i)] = gcd

    if i < n - 1:
        gcd = aa[i + 1]
        for j in range(i + 1, n):
            gcd = fractions.gcd(gcd, aa[j])

        table[(i + 1, n)] = gcd

candidate = 1
for i in range(0, n):
    if i == 0:
        gcd2 = table[(i + 1, n)]
        candidate = max(gcd2, candidate)
    elif i == n - 1:
        gcd1 = table[(0, i)]
        candidate = max(gcd1, candidate)
    else:
        gcd1 = table[(0, i)]
        gcd2 = table[(i + 1, n)]
        candidate = max(math.gcd(gcd1, gcd2), candidate)

print(candidate)


### FIXED CODE ###

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

import fractions

head = {}
head[0] = aa[0]
for i in range(1, n):
    head[i] = fractions.gcd(head[i - 1], aa[i])

tail = {}
tail[n - 1] = aa[-1]
for i in range(n - 2, -1, -1):
    tail[i] = fractions.gcd(tail[i + 1], aa[i])

candidate = 1
for i in range(0, n):
    if i == 0:
        gcd2 = tail[i + 1]
        candidate = max(gcd2, candidate)
    elif i == n - 1:
        gcd1 = head[i - 1]
        candidate = max(gcd1, candidate)
    else:
        gcd1 = head[i - 1]
        gcd2 = tail[i + 1]
        candidate = max(fractions.gcd(gcd1, gcd2), candidate)

print(candidate)
### BUGGY CODE ###

N = int(input())
TA = [list(map(int, input().split(" "))) for _ in range(N)]

# print("-")

s_t, s_a = 1, 1 
for t, a in TA:
    v_t, v_a = 0, 0
    while v_t < s_t or v_a < s_a:
        v_t += t
        v_a += a
    s_t, s_a = v_t, v_a
    # print(s_t, s_a)

print(s_t+s_a)


### FIXED CODE ###

N = int(input())
TA = [list(map(int, input().split(" "))) for _ in range(N)]

n_t, n_a = 1, 1
for t, a in TA:
    # print(n_t/t, n_a/a)
    v = max(-(-n_t//t), -(-n_a//a))
    n_t, n_a = t*v, a*v

print(n_t+n_a)
### BUGGY CODE ###

N=int(input())
cnt=N-1
for i in range(1,N):
    if N%i== 0:
        cnt=min(cnt,N//i+i-2)
print(cnt)

### FIXED CODE ###

N=int(input())
cnt=N-1
for i in range(1,int(N**0.5)+1):
    if N%i== 0:
        cnt=min(cnt,N//i+i-2)
print(cnt)
### BUGGY CODE ###

import sys
from statistics import *
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

a, b, k = na()
ct = 0
for i in range(a, b+1):
    if i <= a + k - 1 or i >= b - k + 1:
        print(i)

### FIXED CODE ###

import sys
from statistics import *
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

a, b, k = na()
ct = 0
li = []
for i in range(a, a + k):
    if i <= b:
        li.append(i)
for i in range(b - k + 1, b+1):
    if i >= a:
        li.append(i)
print(*(sorted(list(set(li)))))
### BUGGY CODE ###

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

ans = 0
for i in range(n):
  cnt = 0
  for j in range(i):
    if p[i] > p[j]:
      cnt += 1
  if cnt == 0:
    ans += 1
  
print(ans)  

### FIXED CODE ###

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

tmp_min = p[0]
cnt = 0

for i in range(n):
    if p[i] <= tmp_min:
        tmp_min = p[i] #i番目までの最小値を更新
        cnt += 1

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

nm = list(map(int, input().split()))
n = nm[0]
m = nm[1]

gates = [list(map(lambda x: int(x), input().split())) for i in range(m)]

key = [0 for i in range(n)]

for gate in gates:
  for i in range(len(key)):
    if (i+1 >= gate[0] and i+1 <= gate[1]):
      key[i] += 1

print(key.count(m))

### FIXED CODE ###

nm = list(map(int, input().split()))
n = nm[0]
m = nm[1]

gates = [list(map(lambda x: int(x), input().split())) for i in range(m)]

first_max = 0
second_min = 100001
for gate in gates:
  first_max = max(first_max, gate[0])
  second_min = min(second_min, gate[1])

answer = second_min - first_max + 1
if (answer <= 0):
  print(0)
else:
  print(answer)
### BUGGY CODE ###

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


import functools
import operator

for i in range(N-K):
  target_1 = LIST_A[i:i+K]
  target_2 = LIST_A[i+1:i+K+1]
  #print(target_1,target_2)
  result_1 = functools.reduce(operator.mul, target_1)
  result_2 = functools.reduce(operator.mul, target_2)
    
  if result_1 < result_2:
    print("Yes")
  else:
    print("No")

	



### FIXED CODE ###

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

for i in range(N-K):
  target_1 = LIST_A[i+K]-LIST_A[i]  
  if target_1 > 0:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

from collections import Counter

n = int(input())
s = []

for i in range(n):
    s.append((input()))

c = Counter(s)

max_count = c.most_common()[0][1]

a = []

for i in range(len(c)):
    if max_count == c.most_common()[i][1]:
        a.append(c.most_common()[i][0])
    else:
        break

b = sorted(a)

for i in range(len(b)):
    print(b[i])

### FIXED CODE ###

from collections import Counter

n = int(input())
s = [input() for _ in range(n)]

c = Counter(s)

max_count = c.most_common()[0][1]

c = sorted(c.items())

for i in range(len(c)):
    if max_count == c[i][1]:
        print(c[i][0])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)

def m():
    n, q = map(int, input().split())
    tree = [[] for _ in range(n + 1)]
    for i in range(1, n):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    counter = [0 for _ in range(n + 1)]
    for _ in range(q):
        p, x = map(int, input().split())
        counter[p] += x

    ans = [0] * (n + 1)
    visited = []

    def dfs(root, point):
        point += counter[root]
        ans[root] = point
        visited.append(root)
        for j in tree[root]:
            if j in visited:
                continue
            dfs(j, point)
        return

    dfs(1, 0)
    for i in range(1, n + 1):
        print(ans[i], '', end='')
    return ans


m()


### FIXED CODE ###

import queue
import sys
def input(): return sys.stdin.readline().rstrip()

def m():
    n, q = map(int, input().split())
    tree = [[] for _ in range(n + 1)]
    for i in range(1, n):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    counter = [0] * (n + 1)
    for _ in range(q):
        p, x = map(int, input().split())
        counter[p] += x

    que = queue.Queue()
    visited = [False] * (n+1)

    def bfs(root, base):
        base += counter[root]
        visited[root] = True
        for e in tree[root]:
            if visited[e]:
                continue
            que.put(e)
            counter[e] += base

        while not que.empty():
            x = que.get()
            point = counter[x]
            visited[x] = True
            for e in tree[x]:
                if visited[e]:
                    continue
                que.put(e)
                counter[e] += point

    bfs(1, 0)
    print(*counter[1:])
    return


m()
### BUGGY CODE ###

def solve(v, w):
    while v != w:
        if v > w:
            v, w = w, v
        w = (w + n - 2) // n
    return v


n, q = map(int, input().split())
print('\n'.join(map(str, (solve(*map(int, input().split())) for _ in range(q)))))


### FIXED CODE ###

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

if n == 1:
    def solve(v, w):
        return min(v, w)
else:
    def solve(v, w):
        while v != w:
            if v > w:
                v, w = w, v
            w = (w + n - 2) // n
        return v

print('\n'.join(map(str, (solve(*map(int, input().split())) for _ in range(q)))))
### BUGGY CODE ###

import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W, n = map(int, input().split())
    AB = set(tuple(tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(n)))

    d = ((1, 1), (1, 0), (1, -1), (0, 1), (0, 0), (0, -1), (-1, 1), (-1, 0), (-1, -1))
    total = (H - 2) * (W - 2)
    res = [0] * 10
    used = set()
    for a, b in AB:
        if (a, b) in used:
            continue
        que = deque([(a, b)])
        while que:
            h, w = que.popleft()
            if (h, w) in used:
                continue
            used.add((h, w))
            cnt = 0
            flg = True
            tmp = []
            for dh, dw in d:
                next_h, next_w = h + dh, w + dw
                if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                    flg = False
                else:
                    if (next_h, next_w) in AB:
                        cnt += 1
                    if (next_h, next_w) not in used:
                        tmp.append((next_h, next_w))
            if flg and cnt:
                res[cnt] += 1
            if cnt:
                for next_h, next_w in tmp:
                    que.append((next_h, next_w))
    res[0] = total - sum(res)
    print(*res, sep="\n")


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W, n = map(int, input().split())
    AB = set(tuple(tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(n)))

    d = ((1, 1), (1, 0), (1, -1), (0, 1), (0, 0), (0, -1), (-1, 1), (-1, 0), (-1, -1))
    target = set()
    res = [0] * 10
    for h, w in AB:
        cnt = 0
        flg = True
        for dh, dw in d:
            next_h, next_w = h + dh, w + dw
            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                flg = False
            if (next_h, next_w) in AB:
                cnt += 1
            else:
                target.add((next_h, next_w))
        if flg:
            res[cnt] += 1

    for h, w in target:
        cnt = 0
        for dh, dw in d:
            next_h, next_w = h + dh, w + dw
            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                break
            if (next_h, next_w) in AB:
                cnt += 1
        else:
            res[cnt] += 1

    total = (H - 2) * (W - 2)
    res[0] = total - sum(res)
    print(*res, sep="\n")


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

# input
N, K, C = map(int, input().split())
S = input()

# process
# daysL = [0]*(N+1)
# daysR = [0]*(N+1)
daysL = [0]
daysR = [0]
tL = 1
tR = K
for i in range(N):
    if S[i] == 'o' and sum(daysL[max(0,i-C+1):]) == 0:
        daysL.append(tL)
        tL += 1
    else:
        daysL.append(0)

    if S[N-i-1] == 'o' and sum(daysR[max(0,i-C+1):]) == 0:
        daysR.append(tR)
        tR -= 1
    else:
        daysR.append(0)

# output
# print(daysL)
# print(daysR)
if tL == K+1:    
    for i in range(N):
        if daysL[i+1] > 0 and daysL[i+1] == daysR[N-i]:
            print(i+1)


### FIXED CODE ###

# input
N, K, C = map(int, input().split())
S = input()

# process
l = [i+1 for i in range(N) if S[i] == 'o']
left = [l[0]]
right = [l[-1]]
for i in range(1, len(l)):
    if l[i] > left[-1]+C:
        left.append(l[i])
    if l[-i-1] < right[-1]-C:
        right.append(l[-i-1])

# output
# print(l)
# print(left)
# print(right)
if len(left) == K:
    for i in range(len(left)):
        if left[i] == right[-i-1]:
            print(left[i])
### BUGGY CODE ###

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

h = 0
for i in range(n):
    qq = list(input().split())
    if qq[0] == '1':
        h += 1
    else:
        if h % 2 ==1:
            s = s[::-1]
            h = 0
        if qq[1] == '1':
            s = qq[2] + s
        else:
            s = s + qq[2]

if h % 2 ==1:
    s = s[::-1]
print(s)

### FIXED CODE ###

s = input()
n = int(input())
b = ''
a = ''
h = 0
for i in range(n):
    qq = list(input().split())
    if qq[0] == '1':
        h += 1
    else:
        if qq[1] == '1':
            if h % 2 ==1:
                a = a + qq[2]
            else:
                b = qq[2] + b
        else:
            if h % 2 ==1:
                b = qq[2] + b
            else:
                a = a + qq[2]

s = b + s + a
if h % 2 ==1:
    s = s[::-1]
print(s)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline # 入出力高速化

class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.depth = N.bit_length()

    def _bitsum(self, i):
        ret = 0
        while i:
            ret += self.tree[i]
            i ^= i & -i
        return ret

    def bitsum(self, l, r=None):
        if r is None:
            return self._bitsum(l)
        else:
            return self._bitsum(r) - self._bitsum(l)

    def bitadd(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        return

    def lower_bound(self, x):
        sum_ = 0
        pos = 0
        v = 1 << self.depth
        for i in range(self.depth, -1, -1):
            k = pos + v
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += v
            v >>= 1
        return pos

def main():
    N, Q = map(int, input().split())
    tl = list() # イベントタイムライン
    points = list()
    for _ in range(N):
        S, T, X = map(int, input().split())
        tl.append((S-X, 1, X)) # insert
        tl.append((T-X, 0, X)) # erase
        points.append(X)
        
    for _ in range(Q):
        D = int(input())
        tl.append((D, 2, 0)) # min
    
    tl.sort()
    points.sort()
    M = len(points)
    comp = {e:i for i, e in enumerate(points)} # 座標圧縮
    B = BIT(M + 20)
 
    for t, c, x in tl:
        if c == 0: # erase
            B.bitadd(comp[x], -1)
        elif c == 1: # insert
            B.bitadd(comp[x], 1)
        else: # min
            idx = B.lower_bound(1)
            print(-1 if idx > M + 10 else points[idx])
    return
    
if __name__ == "__main__":
    main()


### FIXED CODE ###


# 二部探索で決めていく。dpですでに見られたかどうかは把握
"""
工事 finish  1 eve削除
工事 start   2 eve追加
di start     3
この時間を混ぜてソート。上から順番に捌く
（区間がxi,xjで重なっていたらsetに入れられないのか。）

同じ時刻だった場合
工事finish -> 工事start -> di通過
の順番
"""
import sys
from operator import itemgetter
input = sys.stdin.readline
n,q  = map(int, input().split())
events = []
E = 10**10
for i in range(n):
    s,t,x = map(int, input().split())
    # st
    events.append((s-x,1,x))
    # gl
    events.append((t-x,0,x))
ds = [(int(input()),2,i) for i in range(q)]
events.extend(ds)
ans = [-1] * q
events.sort()
works = set()
upd = True
mn = 10**10
for t, e, x in events:
    if e == 1:
        works.add(x)
        if mn > x:
            mn = x
            upd = False
    elif e == 0:
        works.remove(x)
        if x == mn:
            upd = True
    else:
        if len(works) == 0:
            ans[x] = -1
        else:
            if upd:
                mn = min(works)
                upd = False
            ans[x] = mn
print(*ans)