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

for _ in range(int(input())):
    X, Y = input(), input()
    X_len = len(X)
    Y_len = len(Y)
    dp = [[0] * (Y_len+1) for x in range(X_len+1)]
    for x in range(1, X_len + 1):
        pre = dp[x-1]
        tmp = dp[x]
        for y in range(1, Y_len + 1):
            if X[x-1] == Y[y-1]:
                tmp[y] = pre[y-1] + 1
            else:
                tmp[y] = max(tmp[y-1], pre[y])
    print(dp[-1][-1])


### FIXED CODE ###

def ser(X, Y):
    dp = [[0] * (len(Y)+1) for x in range(len(X)+1)]
    for i, x in enumerate(X, 1):
        tmp = dp[i]
        pre = dp[i-1]
        for j, y in enumerate(Y, 1):
            if x == y:
                tmp[j] = pre[j-1] + 1
            elif pre[j] < tmp[j-1]:
                tmp[j] = tmp[j-1]
            else:
                tmp[j] = pre[j]
    return(dp[-1][-1])

for _ in range(int(input())):
    X, Y = input(), input()
    print(ser(X, Y))
### BUGGY CODE ###

import sys
def check(S):
    stop = True
    if len(S) < 2:
        print(base_S_length - len(S))
        sys.exit()
    S_length = len(S) - 1
    for i in range(S_length):
        if (S[i] + S[i + 1]) == 1:
            S[i] = S[i + 1] = 2
            stop = False    
    if stop:
        print(base_S_length - len(S))
        sys.exit()
    S = [i for i in S if i != 2]
    check(S)

S = list(map(int, list(input())))
base_S_length = len(S)
check(S)

### FIXED CODE ###

def main():
    S = list(map(int, list(input())))

    cnt1 = sum(S)
    cnt0 = len(S) - cnt1
    print(2 * min(cnt0, cnt1))


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

def min_dist(i, j, X, Y):
    return min(abs(j-i), abs(X-1-i)+1+abs(Y-1-j), abs(Y-1-i)+1+abs(X-1-j))

N, X, Y = list(map(int, input().split()))
pairs = [[i, j] for i in range(N-1) for j in range(i+1, N)]
dists = [min_dist(x[0], x[1], X, Y) for x in pairs]
for K in range(1,N):
    print(len([x for x in dists if x == K]))

### FIXED CODE ###

def min_dist(i, j, X, Y):
    return min(abs(j-i), abs(X-1-i)+1+abs(Y-1-j), abs(Y-1-i)+1+abs(X-1-j))

N, X, Y = list(map(int, input().split()))
dists = [min_dist(i, j, X, Y) for i in range(N-1) for j in range(i+1, N)]
dist_dic = { i: 0 for i in range(1,N)}
for dist in dists:
    dist_dic[dist] += 1
for K in range(1,N):
    print(dist_dic[K])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
#ABC137C
import copy
import sys
import math

n = int(input())
#tmp = input().split()
#hoge = list(map(lambda a: int(a), tmp))
#k=hoge[0]
#x=hoge[1]

list = [[0 for i in range(26)] for j in range(n)]
#list[0][1]=1
#print(list)

hash=[]
for i in range(0,26):
	hash.append([])

for i in range(0,n):
	tmp=input()
	hoge=0
	for j in range(0,10):
		list[i][ord(tmp[j])-ord("a")]+=1
		hoge+=ord(tmp[j])-ord("a")
	hoge=hoge%26
	hash[hoge].append(i)
#print(hash)

sum=0

for i in range(0,26):
	for j in range(0,len(hash[i])-1):
		for k in range(j+1,len(hash[i])):
			#print(i)
			#print(hash[i][j])
			#print(hash[i][k])
			for m in range(0,26):
				if(list[hash[i][j]][m]!=list[hash[i][k]][m]):
					break
				elif(m==25):
					sum+=1


#for i in range(0,n-1):
#	for j in range(i+1,n):
#		for k in range(0,26):
#			if(list[i][k]!=list[j][k]):
#				break
#			elif(k==25):
#				sum+=1

print(sum)

#print(list)
#print(list[0][:])



### FIXED CODE ###

# -*- coding: utf-8 -*-
#ABC137C
import copy
import sys
import math

n = int(input())
fuga = [0 for i in range(10)]

wordlist={}
for i in range(0,n):
	tmp=input()
	for j in range(0,10):
		fuga[j]=tmp[j]
	fuga.sort()
	hoge=fuga[0]+fuga[1]+fuga[2]+fuga[3]+fuga[4]+fuga[5]+fuga[6]+fuga[7]+fuga[8]+fuga[9]

	if(hoge in wordlist):
		wordlist[hoge]+=1
	else:
		wordlist[hoge]=1

#print(hoge)
#print(wordlist)

total=0
for i in wordlist:
	t=wordlist[i]
	if(t>=2):
		total+=t*(t-1)//2


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

n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
cntA = 0
ans = 0
p = max(m,n)
if p == n:
  q = a
  r = b
else:
  q = b
  r = a
for i in range(p):
  if cntA+q[i] > k:
    break
  ans += 1
  cntA += q[i]
indA = ans-1
nc = indA+1
for j in range(indA+1):
  temp = 0
  add = 0
  for v in r:
    add += v
    if cntA + add > k:
      break
    temp += 1
  cntA -= q[nc-1-j]
  ans = max(ans,indA+1+temp)
  indA -= 1
print(ans)

### FIXED CODE ###

n,m,k = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

a,b = [0],[0]
for i in range(n):
  a.append(a[i]+A[i])
for i in range(m):
  b.append(b[i]+B[i])

ans,j = 0,m
for i in range(n+1):
  if a[i]>k:
    break
  while b[j]+a[i]>k:
    j -= 1
  ans = max(ans,i+j)

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

R, G, B, N = map(int, input().split())

ans = 0
for r in range(3001):
    for g in range(3001):
        tmp = N - r * R - g * G
        if tmp < 0:
            break
        if tmp % B == 0 and tmp // B >= 0:
            ans += 1

print(ans)


### FIXED CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for r in range(N // R + 1):
    for g in range((N - R * r) // G + 1):
        tmp = N - r * R - g * G
        if tmp % B == 0:
            ans += 1

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

from heapq import heappush, heappop

INF =  10000000000

def dijkstra(r, v, dic):
    dp = []
    q = []
    dp = [INF] * v
    dp[r] = 0
    heappush(q, (0, r))
    while q:
        cost, vtx = heappop(q)
        if dp[vtx] < cost:
            continue
        if vtx not in dic:
            continue
        for vtx1, cost1 in dic[vtx]:
            if cost + cost1 < dp[vtx1]:
                dp[vtx1] = cost + cost1
                heappush(q, (cost + cost1, vtx1))
    return dp

dp = []
line = input()
n = int(line)
edge = {}
for _ in range(0, n - 1):
    line = input()
    s, t, d = list(map(int, line.split()))
    if s not in edge:
        edge[s] = [[t, d]]
    else:
        edge[s] += [[t, d]]
    if t not in edge:
        edge[t] = [[s, d]]
    else:
        edge[t] += [[s, d]]
diam = 0
for s in range(0, n - 1):
    dp = dijkstra(s, n, edge)
    diam = max(max(dp[i] if dp[i] != INF else 0 for i in range(0, n)), diam)
print(diam)


### FIXED CODE ###

def solve(prev, r, dic):
    d = 0
    t = r
    stack = []
    stack += [[prev, r, d]]
    while stack:
        prev, r, d1 = stack.pop(-1)
        if r in dic:
            for vtx, cost in dic[r]:
                if vtx == prev:
                    continue
                stack += [[r, vtx, d1 + cost]]
                if d < d1 + cost:
                    d = d1 + cost
                    t = vtx
    return d, t

line = input()
n = int(line)
edge = {}
for _ in range(0, n - 1):
    line = input()
    s, t, d = list(map(int, line.split()))
    if s not in edge:
        edge[s] = [[t, d]]
    else:
        edge[s] += [[t, d]]
    if t not in edge:
        edge[t] = [[s, d]]
    else:
        edge[t] += [[s, d]]
r1, t1 = solve(-1, 0, edge)
r2, t2 = solve(-1, t1, edge)
print(r2)
### BUGGY CODE ###

import sys
from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    def find(self, x):
        if self.root[x] == x:
            return x
        else:
            y = self.find(self.root[x])
            self.root[x] = y
            return self.root[x]

    def unite(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.root[rx] = ry
        else:
            self.root[ry] = rx
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    

def main():
    input = sys.stdin.readline
    N, K, L = map(int, input().split())
    road = UnionFind(N)
    rail = UnionFind(N)

    for _ in range(K):
        p, q = map(int, input().split())
        road.unite(p-1, q-1)

    for _ in range(L):
        r, s = map(int, input().split())
        rail.unite(r-1, s-1)

    road_r = defaultdict(list)
    rail_r = defaultdict(list)
    for i in range(N):
        road_r[road.find(i)].append(i)
        rail_r[rail.find(i)].append(i)

    memo = [[-1 for _ in range(N)] for _ in range(N)]
    ans = []
    for i in range(N):
        n = road.find(i)
        m = rail.find(i)

        if memo[n][m] != -1:
            ans.append(memo[n][m])
        else:
            a = len(set(road_r[n]) & set(rail_r[m]))
            memo[n][m] = a
            ans.append(a)

    return print(*ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    def find(self, x):
        if self.root[x] == x:
            return x
        else:
            y = self.find(self.root[x])
            self.root[x] = y
            return self.root[x]

    def unite(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.root[rx] = ry
        else:
            self.root[ry] = rx
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    

def main():
    input = sys.stdin.readline
    N, K, L = map(int, input().split())
    road = UnionFind(N)
    rail = UnionFind(N)

    for _ in range(K):
        p, q = map(int, input().split())
        road.unite(p-1, q-1)

    for _ in range(L):
        r, s = map(int, input().split())
        rail.unite(r-1, s-1)

    d = defaultdict(lambda: 0)
    for i in range(N):
        n = road.find(i)
        m = rail.find(i)
        d[(n, m)] += 1

    ans = []
    for i in range(N):
        n = road.find(i)
        m = rail.find(i)
        ans.append(d[(n, m)])

    return print(*ans)


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

N, K = map(int, input().split())
h = [0] + list(map(int, input().split()))

dp = [-1] * (N + 1)
dp[N] = 0
dp[N - 1] = abs(h[N] - h[N - 1])

for i in reversed(range(1, N - 1)):
    candidates = [10 ** 5] * K
    for k in range(1, K + 1):
        if i + k > N:
            continue
        candidates[k - 1] = dp[i + k] + abs(h[i + k] - h[i])
    dp[i] = min(candidates)
print(dp[1])


### FIXED CODE ###

N, K = map(int, input().split())
h = [0] + list(map(int, input().split()))

dp = [-1] * (N + 1)
dp[N] = 0
dp[N - 1] = abs(h[N] - h[N - 1])

for i in reversed(range(1, N - 1)):
    candidates = [10 ** 5] * K
    for k in range(1, K + 1):
        if i + k > N:
            continue
        candidates[k - 1] = dp[i + k] + abs(h[i + k] - h[i])
    dp[i] = min(candidates)
print(dp[1])
### BUGGY CODE ###

# AtCoder DP Task D - Knapsack 1
def knapsack(target, W, V): # target=knapsack weight
    P = [[0] * (target + 1) for _ in range(len(V))]
    for vi in range(len(V)):
        row, prev = P[vi], P[vi - 1]
        for w in range(target + 1):
            if vi > 0:
                row[w] = prev[w] # same value without vi-th item
                if w >= W[vi]:
                    new = P[vi - 1][w - W[vi]] + V[vi]
                    if new > P[vi][w]: # most value
                        row[w] = new
            else:
                if w >= W[vi]:
                    row[w] = V[vi]
    return P[len(V) - 1][target]

def knapsack_rec(target, W, V): # target=knapsack weight
    P = [[-1] * (target + 1) for _ in range(len(V))]

    def rec(w, index):
        if index == 0 and w >= W[index]:
            return V[index]
        elif index > 0:
            if P[index][w] != -1:
                return P[index][w]
            r = rec(w, index - 1)
            if w >= W[index]:
                y = rec(w - W[index], index - 1) + V[index]
                r = r if r > y else y
            P[index][w] = r
            return r
        return 0

    ret = rec(target, len(V) - 1)
    return ret

assert knapsack_rec(15, [6, 5, 6, 6, 3, 7], [5, 6, 4, 6, 5, 2]) == 17

n, w = map(int, input().split())
W, V = [], []
for _ in range(n):
    weight, value = map(int, input().split())
    W.append(weight)
    V.append(value)
ans = knapsack(w, W, V)
print(ans)


### FIXED CODE ###

# AtCoder DP Task D - Knapsack 1
def knapsack(target, W, V): # target=knapsack weight
    P = [[0] * (target + 1) for _ in range(len(V))]
    for vi in range(len(V)):
        row, prev = P[vi], P[vi - 1]
        for w in range(target + 1):
            if vi > 0:
                row[w] = prev[w] # same value without vi-th item
                if w >= W[vi]:
                    new = P[vi - 1][w - W[vi]] + V[vi]
                    if new > P[vi][w]: # most value
                        row[w] = new
            else:
                if w >= W[vi]:
                    row[w] = V[vi]
    return P[len(V) - 1][target]

def knapsack_rec(target, W, V): # target=knapsack weight
    P = [-1] * (target + 1)
    P[target] = 0 # default + max

    for vi in range(len(V)):
        we = W[vi]
        va = V[vi]
        for i in range(we, target + 1):
            if P[i] != -1 and P[i - we] < P[i] + va:
                P[i - we] = P[i] + va

    return max(P)

assert knapsack_rec(15, [6, 5, 6, 6, 3, 7], [5, 6, 4, 6, 5, 2]) == 17

if __name__ == "__main__":
    import sys
    n, w, *r = map(int, sys.stdin.read().split())
    W, V = r[::2], r[1::2]
    ans = knapsack_rec(w, W, V)
    print(ans)
### BUGGY CODE ###

#https://atcoder.jp/contests/dp/tasks/dp_e
#2019-01-13
import numpy as np
N, W = map(int, input().split())
w, v = [], []
for i in range(N):
    a, b = map(int, input().split())
    w += [a]
    v += [b]

DP = np.ones(N*1000+1,dtype = int) *(W+1)
DP[0] = 0
#総価値 i 円を得るために最低限必要な重量
for i in range(N):
    for j in range(N*1000,-1,-1):
        DP[j] = min(DP[j- v[i]] + w[i], DP[j])
ans = 0
for k in range(N*1000+1):
    if DP[k] <= W:
        
        ans = k
print(ans)

### FIXED CODE ###

#https://atcoder.jp/contests/dp/tasks/dp_e
#2019-01-13
N, W = map(int, input().split())
w, v = [], []
for i in range(N):
    a, b = map(int, input().split())
    w += [a]
    v += [b]

DP = [float("inf")] * (N*1000+1)
DP[0] = 0
#総価値 i 円を得るために最低限必要な重量
for i in range(N):
    for j in range(N*1000,-1,-1):
        DP[j] = min(DP[j- v[i]] + w[i], DP[j])
ans = 0
for k in range(N*1000+1):
    if DP[k] <= W:
        
        ans = k
print(ans)
### BUGGY CODE ###

n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
light_position =1
light_position = a[light_position-1]
count = 1
while True:
    if light_position == 2:
        break
    elif light_position == 1:
        count = -1
        break        
    light_position = a[light_position-1]
    count += 1
print(count)

### FIXED CODE ###

n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
light_position =1
light_position = a[light_position-1]
count = 1
while True:
    if light_position == 2:
        break
    elif light_position == 1 or count > n:
        count = -1
        break        
    light_position = a[light_position-1]
    count += 1
print(count)
### BUGGY CODE ###

n , m = map(int,input().split())
kagi = []
for i in range(m):
    a , b = map(int,input().split())
    c = list(map(int,input().split()))
    k = 0
    for j in c:
        k += 1 << (j-1)
    kagi.append((a,k))
INF = 10 ** 9
dp = [[INF for i in range(m+1)] for i in range(2**n)]
dp[0] = [0 for i in range(m+1)]
for i in range(2**n):
    for j in range(1,m+1):
        dp[i][j] = min(dp[i][j],dp[i][j-1])
        t = i | kagi[j-1][1]
        dp[t][j] = min(dp[t][j],dp[i][j]+kagi[j-1][0])
print(dp[2**n-1][m] if dp[2**n-1][m] != INF else -1)

### FIXED CODE ###

n , m = map(int,input().split())
kagi = []
for i in range(m):
    a , b = map(int,input().split())
    c = list(map(int,input().split()))
    k = 0
    for j in c:
        k += 1 << (j-1)
    kagi.append((a,k))
INF = 10 ** 9
dp = [[INF for i in range(m+1)] for i in range(2**n)]
dp[0] = [0 for i in range(m+1)]
for i in range(2**n):
    for j in range(1,m+1):
        dp[i][j] = min(dp[i][j],dp[i][j-1])
        t = i | kagi[j-1][1]
        dp[t][j] = min(dp[t][j],dp[i][j]+kagi[j-1][0])
print(dp[2**n-1][m] if dp[2**n-1][m] != INF else -1)
### BUGGY CODE ###

N,M = map(int,input().split())
AC = 0
WA = 0
lis_ac = []
dic_wa ={}
if M == 0:
  print(0,0)
else:
  A = [list(input().split()) for i in range(M)]
  A.sort(key = lambda x: int(x[0]))
  for i in range(M):
    if A[i][0] not in lis_ac:
      if A[i][1] == 'AC':
        lis_ac.append(A[i][0])
        if A[i][0] in dic_wa.keys():
          WA += dic_wa[A[i][0]]
      elif A[i][0] in dic_wa.keys():
        dic_wa[A[i][0]] += 1
      else:
        dic_wa[A[i][0]] = 1
  print(len(lis_ac), WA)


### FIXED CODE ###

N,M = map(int,input().split())
AC = 0
WA = 0
lis = [0] * N
for i in range(M):
  a,b = input().split()
  if lis[int(a)-1] < 0:
    pass
  elif b == 'AC':
    WA += lis[int(a)-1]
    AC += 1
    lis[int(a)-1] = -1
  else:
    lis[int(a)-1] += 1
print(AC, WA)
### BUGGY CODE ###

sum=0
K=int(input())+1
r=1
for a in range(1,K):
  for b in range(1,K):
    p=a
    q=b
    if p%q==0:
      r=q
    while p%q!=0:
      r=p%q
      p=q
      q=r
    ab=r
    for c in range(1,K):
      p=c
      q=ab
      if p%q==0:
        r=q
      while p%q!=0:
        r=p%q
        p=q
        q=r
      sum+=r
print(sum)

### FIXED CODE ###

import math
sum=0
K=int(input())+1
for a in range(1,K):
  for b in range(1,K):
    ab=math.gcd(a,b)
    for c in range(1,K):
      sum+=math.gcd(ab,c)
print(sum)
### BUGGY CODE ###

def main():
    n,a,b = map(int,input().split())
    MOD = (10**9)+7
    s = pow(2,n,MOD)-1
    u = 1
    bb = 1


    for i in range(1,(max(a,b) + 1)):
        u*=(n-i+1)%MOD
        bb*= i % MOD
        if i == a or i == b:
            s-=u*pow(bb,MOD-2,MOD)



    print(s%MOD)
#


if __name__=='__main__':
    main()


### FIXED CODE ###

def main():
    n,a,b = map(int,input().split())
    MOD = 10**9 +7
    s = pow(2,n,MOD)-1
    P_ni = 1
    F_i = 1


    for i in range(1,b + 1):
        P_ni=P_ni*(n-i+1)%MOD
        F_i=F_i* i % MOD
        if i == a or i == b:
            s-=P_ni*pow(F_i,MOD-2,MOD)



    print(s%MOD)

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

n = int(input())
answer = 1
for i in range(1,n+1):
	answer *= i
print(answer%(10**9+7))

### FIXED CODE ###

n = int(input())
answer = 1
for i in range(1,n+1):
	answer = (answer*i)%(10**9+7)
print(answer)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/abc082/editorial.pdf
　　　https://atcoder.jp/contests/abc082/submissions/3930644
・計算量改善。-8000～8000全部回してたループを値があるkeyだけ回るようにした。
・それに合わせて、貰うDPを送るDPにした。(自分的にはこっちのが分かりやすいし)
"""

from collections import defaultdict

S = input()
X, Y = map(int, input().split())

S2 = []
tmp = 0
# 連続するF毎にまとまるように文字列Sを変形させる
for i in range(len(S)):
    if S[i] == 'F':
        tmp += 1
    # T毎に区切る
    else:
        S2.append(tmp)
        tmp = 0
S2.append(tmp)

# 文字列がFのみだとこの後のDPできないので別処理
if len(S2) == 1:
    if X == S2[0] and Y == 0:
        print('Yes')
    else:
        print('No')
    exit()

# dictならマイナスの添字もそのまま使える
dpx = [defaultdict(int) for _ in range(len(S2))]
dpy = [defaultdict(int) for _ in range(len(S2))]
# xの初期化：step0は右移動、step1ではそのまま
dpx[0][S2[0]] = dpx[1][S2[0]] = 1
# yの初期化：step0は何もなし、step1で上下どちらかに移動
dpy[1][S2[1]] = dpy[1][-S2[1]] = 1
for i in range(2, len(S2)):
    # 左右に移動する
    for k, v in dpx[i-1].items():
        if i % 2 == 0:
            # 到達可能な位置から+-した位置に送る
            dpx[i][k-S2[i]] = 1
            dpx[i][k+S2[i]] = 1
        else:
            # yをやる時はxはそのまま
            dpx[i][k] = dpx[i-1][k]
    # 上下に移動する
    for k, v in dpy[i-1].items():
        if i % 2 == 1:
            dpy[i][k-S2[i]] = 1
            dpy[i][k+S2[i]] = 1
        else:
            dpy[i][k] = dpy[i-1][k]
# 最後のstepでXとYが到達可能ならOK
if dpx[len(S2)-1][X] and dpy[len(S2)-1][Y]:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/abc082/editorial.pdf
　　　https://atcoder.jp/contests/abc082/submissions/3930644
・メモリ節約のため、dictをsetにした。
・さらに使い終わった1つ前はもういらないので消すことにした。
"""

S = input()
X, Y = map(int, input().split())

S2 = []
tmp = 0
# 連続するF毎にまとまるように文字列Sを変形させる
for i in range(len(S)):
    if S[i] == 'F':
        tmp += 1
    # T毎に区切る
    else:
        S2.append(tmp)
        tmp = 0
S2.append(tmp)

# 文字列がFのみだとこの後のDPできないので別処理
if len(S2) == 1:
    if X == S2[0] and Y == 0:
        print('Yes')
    else:
        print('No')
    exit()

# あるかないか分かればいいので、dictじゃなくてsetにする
dpx = [set() for _ in range(len(S2))]
dpy = [set() for _ in range(len(S2))]
# xの初期化：step0は右移動、step1ではそのまま
dpx[0].add(S2[0])
dpx[1].add(S2[0])
# yの初期化：step0は何もなし、step1で上下どちらかに移動
dpy[0].add(0)
dpy[1].add(S2[1])
dpy[1].add(-S2[1])
for i in range(2, len(S2)):
    # 左右に移動する
    for v in dpx[i-1]:
        if i % 2 == 0:
            # 到達可能な位置から+-した位置に送る
            dpx[i].add(v-S2[i])
            dpx[i].add(v+S2[i])
        else:
            # yをやる時はxはそのまま
            dpx[i].add(v)
    # 1つ前は使い終わったので削除
    dpx[i-1] = set()
    # 上下に移動する
    for v in dpy[i-1]:
        if i % 2 == 1:
            dpy[i].add(v-S2[i])
            dpy[i].add(v+S2[i])
        else:
            dpy[i].add(v)
    dpy[i-1] = set()
# 最後のstepでXとYが到達可能ならOK
if X in dpx[len(S2)-1] and Y in dpy[len(S2)-1]:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys
from collections import Counter, defaultdict

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, Q = MAP()
X = set()
A = defaultdict(list)
for i in range(N):
    s, t, x = MAP()
    # 全ての工事を同じ時系列に持ってくる
    X.add(s-x)
    X.add(t-x)
    A[s-x].append((x, 0))
    A[t-x].append((x, 1))
D = LIST(Q)

Dset = set(D)
S = sorted(X|Dset)
B = {}
C = Counter()
for key in S:
    if key in A:
        for x, flag in A[key]:
            if flag == 0:
                C[x] += 1
            else:
                C[x] -= 1
            if C[x] == 0:
                del C[x]
    if key in Dset:
        mn = min(C) if len(C) else -1
        B[key] = mn
[print(B[x]) for x in D]


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, Q = MAP()
# 3種類の状態変化をイベントとして一括管理する
# 0: 工事終了, 1: 工事開始, 2: 人の出発
events = []
for i in range(N):
    s, t, x = MAP()
    # (開始座標に合わせた状態の工事開始時間, フラグ, 実際の座標)
    events.append((s-x, 1, x))
    # (開始座標に合わせた状態の工事終了時間, フラグ, 実際の座標)
    events.append((t-x, 0, x))
for i in range(Q):
    d = INT()
    # (人の出発時間, フラグ, index)
    events.append((d, 2, i))
# 時系列に沿ってソート、フラグも同時刻な時先に処理して欲しいものから番号を振ってある
events.sort()

# setとheapqを合わせて、時刻に合わせた処理と最小値取得を行う
S = set()
hp = []
ans = [0] * Q
for t, flag, x in events:
    # 工事終了
    if flag == 0:
        S.remove(x)
    # 工事開始
    elif flag == 1:
        S.add(x)
        heappush(hp, x)
    # 人の移動
    elif flag == 2:
        # heapqの先頭要素ついて、setと状態を合わせる
        while len(hp) and hp[0] not in S:
            heappop(hp)
        if len(hp):
            ans[x] = hp[0]
        else:
            ans[x] = -1
[print(a) for a in ans]