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

from itertools import combinations

N = int(input())
S = input()
answer = 0

for i, j in combinations(range(N), 2):
    limit = j
    if S[i:i + answer] != S[j:j + answer]:
        continue
    cnt = answer
    i += answer
    j += answer
    if j > N - 1:
        break
    while S[i] == S[j]:
        cnt += 1
        i += 1
        j += 1
        if j > N - 1 or i == limit:
            break
    if answer < cnt:
        answer = cnt

print(answer)


### FIXED CODE ###

def z_algorithm(S):
    n = len(S)
    A = [0] * n
    A[0] = n
    L = 0
    R = 0
    # 過去にS[R]まで調べたとする
    for i in range(1, n):
        if R <= i:
            L = R = i
            while R < n and S[R] == S[R - L]:
                R += 1
            A[i] = R - L
        elif A[i - L] < R - i:
            A[i] = A[i - L]
        else:
            L = i
            while R < n and S[R] == S[R - L]:
                R += 1
            A[i] = R - L
    return A


def main():
    N = int(input())
    S = input()
    answer = 0
    for i in range(N):
        a = z_algorithm(S[i:])
        for j in range(1, N - i):
            cnt = min(j, a[j])
            if cnt > answer:
                answer = cnt

    print(answer)


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

N = int(input())
HPs = [tuple(map(int, input().split())) for i in range(N)]

HPs.sort(key=lambda x: x[0] + x[1])

dp = {0: 0}
for H, P in HPs:
    for num, minH in list(dp.items()):
        if H >= minH:
            if num + 1 in dp:
                dp[num + 1] = min(dp[num + 1], minH + P)
            else:
                dp[num + 1] = minH + P

print(max(dp.keys()))


### FIXED CODE ###

N = int(input())
HPs = [tuple(map(int, input().split())) for i in range(N)]

HPs.sort(key=lambda x: x[0] + x[1])

INF = float('inf')
dp = [0]
for i, (H, P) in enumerate(HPs, 1):
    if dp[-1] != INF:
        dp += [INF]

    for j in range(1, len(dp))[::-1]:
        hgt = dp[j - 1]
        if hgt <= H:
            dp[j] = min(dp[j], hgt + P)

dp += [INF]
print(dp.index(INF) - 1)
### BUGGY CODE ###

import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

ans = 0
for i in range(n):
    if i == 0:
        cmb_min = combinations_count(n-1, k-1)
        ans -= a[i] * cmb_min
    elif i <= n - k:
        cmb_min = cmb_min * (n-k-i+1) // (n-i)
        ans -= a[i] * cmb_min
    
    if i == k - 1:
        cmb_max = 1
        ans += a[i]
    elif i > k - 1:
        cmb_max = cmb_max * i // (i-k+1)
        ans += a[i] * cmb_max
    
    ans = ans % (10 ** 9 + 7)

print(ans)

### FIXED CODE ###

def prepare(n, MOD):
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs

def combinations_count(n, r, factorials, invs):
    return (factorials[n] * invs[n-r] * invs[r]) % (10 ** 9 + 7)
 
n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))

factorials, invs = prepare(n, 10 ** 9 + 7)

ans = 0
for i in range(n):
    if i <= n - k:
        ans -= a[i] * combinations_count(n-i-1, k-1, factorials, invs)
    
    if i >= k - 1:
        ans += a[i] * combinations_count(i, k-1, factorials, invs)
    
    ans = ans % (10 ** 9 + 7)
 
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
c = [0]*1000001

for i in range(n):
  c[a[i]] -= 1
  for j in range(a[i],1000001,a[i]):
    c[j] += 2

ans=c.count(1)
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
kmax = sorted(a)[-1]
c = [0]*(kmax+1)

for i in range(n):
  c[a[i]] -= 1
  for j in range(a[i],(kmax+1),a[i]):
    c[j] += 2

ans=c.count(1)
print(ans)
### BUGGY CODE ###

def main():
    S = list(input())
    count = 0
    while True:
        start_count = count
        for i, val in enumerate(S):
            try:
                if S[i] != S[i+1]:
                    S.pop(i)
                    S.pop(i)
                    count += 2
            except IndexError:
                pass

        if start_count == count:
            break

    print(count)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import Counter


def main():
    S = list(input())
    c = Counter(S)
    print(len(S) - abs(c['0'] - c['1']))


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

import copy

N = int(input())
D = [int(input()) for i in range(N)]

e = [0 for j in range(N)]

for i in range(N):
    e = copy.deepcopy(D)
    e[i] = 0
    print(max(e))

### FIXED CODE ###

N = int(input())
d = [int(input()) for i in range(N)]

M = max(d)
D = d[:]
d.remove(M)
m = max(d)

for j in range(N):
    if D[j]==M:
        print(m)
    else:
        print(M)
### BUGGY CODE ###

N,M = map(int,input().split())
es = [[] for i in range(N)]
for i in range(M):
    l,r,d = map(int,input().split())
    l,r = l-1,r-1
    es[l].append((r,d))
    es[r].append((l,-d))

checked = [0] * N
for i in range(N):
    if checked[i]: continue
    dist = [None] * N
    dist[i] = 0
    stack = [i]
    while stack:
        v = stack.pop()
        checked[v] = 1
        for to,d in es[v]:
            if dist[to] is None:
                dist[to] = dist[v] + d
                if not checked[to]:
                    stack.append(to)
            else:
                if dist[to] != dist[v] + d:
                    print('No')
                    exit()
print('Yes')


### FIXED CODE ###

N,M = map(int,input().split())
es = [[] for i in range(N)]

for i in range(M):
    l,r,d = map(int,input().split())
    l,r = l-1, r-1
    es[l].append((r,d))
    es[r].append((l,-d))

dist = [None] * N
for i in range(N):
    if dist[i] is not None: continue
    stack = [i]
    dist[i] = 0
    while stack:
        v = stack.pop()
        for to,d in es[v]:
            if dist[to] is None:
                stack.append(to)
                dist[to] = dist[v] + d
            elif dist[to] != dist[v] + d:
                print('No')
                exit()
print('Yes')
### BUGGY CODE ###


#MAX_N = 25; # nの最大値

#入力
n, W = map(int, input().split())
s = []
for i in range(n):#h:高さ
    s.append([int(m) for m in input().split()])
w = []
v = []
for i in range(n):
    w.append(s[i][0])
    v.append(s[i][1])

# i番目以降の品物から重さの和がj以下なるように選んだときの、
# 取りうる価値の総和の最大値を返す関数
def rec(i, j):
    #res = 0
    if i == n:
    # 品物がもう残っていないときは、価値の和の最大値は0で確定
        res = 0
    elif j < w[i]:
    # 残りの容量が足りず品物iを入れられないので、入れないパターンだけ処理
    # i+1 以降の品物のみを使ったときの最大値をそのままこの場合の最大値にする
        res = rec(i + 1, j)
    else:
    # 品物iを入れるか入れないか選べるので、両方試して価値の和が大きい方を選ぶ
        res = max(rec(i + 1, j),rec(i + 1, j - w[i]) + v[i])
    return res

print(rec(0, W))

### FIXED CODE ###

#入力
n, W = map(int, input().split())
s = []
for i in range(n):#h:高さ
    s.append([int(m) for m in input().split()])
s.sort(key=lambda x:(x[0], x[1]))
s0 = []
s1 = []
s2 = []
s3 = []
for i in range(n):
    if i == 0:
        w0 = s[i][0]
        s0.append(s[i])
    elif s[i][0] == w0:
        s0.append(s[i])
    elif s[i][0] == w0 + 1:
        s1.append(s[i])
    elif s[i][0] == w0 + 2:
        s2.append(s[i])
    elif s[i][0] == w0 + 3:
        s3.append(s[i])
s0.sort(key=lambda x: x[1], reverse=True)
s1.sort(key=lambda x: x[1], reverse=True)
s2.sort(key=lambda x: x[1], reverse=True)
s3.sort(key=lambda x: x[1], reverse=True)
w = []
v = []
t0 = 0
t1 = 0
t2 = 0
t3 = 0
u0 = 0
u1 = 0
u2 = 0
u3 = 0
u = []
for h in range(-1, len(s0)):
    if h == -1:
        t0 = 0
        u0 = 0
    else:
        t0 += s0[h][0]
        u0 += s0[h][1]
    for i in range(-1, len(s1)):
        if i == -1:
            t1 = 0
            u1 = 0
        else:
            t1 += s1[i][0]
            u1 += s1[i][1]
        for j in range(-1, len(s2)):
            if j == -1:
                t2 = 0
                u2 = 0
            else:
                t2 += s2[j][0]
                u2 += s2[j][1]
            for k in range(-1, len(s3)):
                if k == -1:
                    t3 = 0
                    u3 = 0
                else:
                    t3 += s3[k][0]
                    u3 += s3[k][1]
                if t0 + t1 + t2 + t3 <= W:
                    u.append(u0 + u1 + u2 + u3)
print(max(u))
### BUGGY CODE ###

import numpy as np
def isP(x):
    for i in range(2,int(np.sqrt(x))+1):
        if x % i == 0:
            return False
    return True

#クエリにO(1)で返すためのテーブルを用意
MAX = int(10e5+1)
P = [isP(x) for x in range(MAX)]
Ans = [0] * MAX
cnt = 0
for i in range(1,MAX):
    if P[i] and P[(i+1)//2]:
        cnt += 1
    Ans[i] = cnt

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

### FIXED CODE ###

#クエリにO(1)で返すためのテーブルを用意
import numpy as np
MAX = int(10e5+1)
List = list(range(2,MAX))
P = []
while len(List) > 0:
    p = List[0]
    if p >= np.sqrt(MAX): break
    P.append(p)
    List = [x for x in List if x % p != 0]
P = set(P+List)

Ans = [0] * MAX
cnt = 0
for i in range(1,MAX):
    if i in P and (i+1)//2 in P:
        cnt += 1
    Ans[i] = cnt

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

N = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
max = l[N-1]
for i in range(N-2):
    if l[i]+l[i+1] > max:
        k = N-i-1
        ans += ((k-1)*k*(k+1))//6
        break
    for j in range(i+1,N-1):
        s = l[i]+l[j]
        if s <= l[j+1]:
            continue
        if s > max:
            ans += (N-j-1) * (N-j) //2
            break
        start = j+1
        end = N
        while start != end:
            center = (start + end)//2
            if s <= l[center]:
                end = center
            else:
                start = center + 1
        ans += end-j-1
print(ans)

### FIXED CODE ###

N = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
max = l[N-1]
tc = N
st = [j+1 for j in range(N-1)]
for i in range(N-2):
    if l[i]+l[i+1] > max:
        k = N-i-1
        ans += ((k-1)*k*(k+1))//6
        break
    for j in range(i+1,N-1):
        if j == tc:
            ans += tp
            break
        s = l[i]+l[j]
        if s <= l[j+1]:
            continue
        if s > max:
            tc = j 
            tp = (N-j-1) * (N-j) //2 #これをiの中でできないか
            ans += tp
            break
        start = st[j]
        if s <= l[start]:
            ans += start-j-1
            continue
        end = N
        while start != end:
            center = (start + end)//2
            if s <= l[center]:
                end = center
            else:
                start = center + 1
        st[j] = end
        ans += end-j-1
print(ans)
### BUGGY CODE ###

a,b,k = map(int, input().split())
for i in range(a,b+1):
  if i < a+k or i > b-k:
    print(i)

### FIXED CODE ###

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

for i in range(a,a+k):
  if i > b:
    break
  print(i)
for i in range(max(b-k+1,a+k),b+1):
  print(i)
### BUGGY CODE ###

d = input()
s = input()
 
r = s.count('R')
g = s.count('G')
b = s.count('B')
 
res = r*g*b
for i in range(len(s)-2):
    for j in range(i,len(s)-1):
        for k in range(j, len(s)):
            if (j - i) == (k - j):
                if s[i] != s[k] and s[i] != s[j] and s[j] != s[k]:
                    res -= 1
print(res)

### FIXED CODE ###

d = input()
s = input()

r = s.count('R')
g = s.count('G')
b = s.count('B')

res = r*g*b
for i in range(len(s)-2):
    for j in range(i,len(s)-1):
        k = 2 * j - i
        if k < len(s) and s[i] != s[k] and s[i] != s[j] and s[j] != s[k]:
            res -= 1
print(res)
### BUGGY CODE ###

List = []
N, K = map(int, input().split())
for i in range(N):
    a, b = map(int, input().split())
    for j in range(b):
        List.append(a)
List.sort()
print(List[K-1])

### FIXED CODE ###

n, k = map(int, input().split())
l = [0] * (10**5 + 1)
for i in range(n):
    a, b = map(int, input().split())
    l[a] += b
s = 0
for i, v in enumerate(l):
    s += v
    if s >= k:
        print(i)
        break
### BUGGY CODE ###

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

print(sum((j-i)!=(k-j) and s[i]!=s[j] and s[i]!=s[k] and s[j]!=s[k] for i in range(n) for j in range(i,n) for k in range(j,n)))


### FIXED CODE ###

n = int(input())
s = input()
r_count = s.count('R')
g_count = s.count('G')
b_count = s.count('B')

count=0
for i in range(n):
    a = s[i]
    for j in range(i+1,n):
        if (2*j-i)>(n-1):
            continue
        b=s[j]
        c=s[2*j-i]
        if a!=b and b!=c and a!=c:
            count+=1
print(r_count*g_count*b_count-count)
### BUGGY CODE ###

import sys
from collections import namedtuple
from heapq import heappush, heappop

input = sys.stdin.readline

INF = sys.maxsize

P = namedtuple('P', 'cost v')
Edge = namedtuple('Edge', 'cost to')
X = namedtuple('X', 'x i')
Y = namedtuple('Y', 'y i')

N = int(input())

G = [[] for _ in range(N)]
xg = []
yg = []

for i in range(N):
  x, y = map(int, input().split())
  xg.append(X(x, i))
  yg.append(Y(y, i))

xg.sort()
yg.sort()

for i in range(N - 1):
  x1, a = xg[i]
  x2, b = xg[i + 1]
  y1, c = yg[i]
  y2, d = yg[i + 1]
  G[a].append(Edge(abs(x1 - x2), b))
  G[b].append(Edge(abs(x1 - x2), a))
  G[c].append(Edge(abs(y1 - y2), d))
  G[d].append(Edge(abs(y1 - y2), c))

total = 0
costs = [INF] * N
costs[0] = 0  # 集合Xからの最短距離
used = set()

q = [P(0, 0)]

while q: 
  p = heappop(q)

  if len(used) >= N:
    break

  if p.v in used and p.cost >= costs[p.v]:
    continue

  costs[p.v] = 0
  total += p.cost
  used.add(p.v)

  for cost, to in G[p.v]:
    if costs[to] > costs[p.v] + cost:
      costs[to] = costs[p.v] + cost
      heappush(q, P(costs[to], to))

print(total)


### FIXED CODE ###

from collections import namedtuple


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

  def is_same(self, a, b):
    return self.find(a) == self.find(b)

  def unite(self, a, b):
    a = self.find(a)
    b = self.find(b)  
    if self.size[a] < self.size[b]:
      a, b = b, a
    self.par[b] = a
    self.size[a] += self.size[b]

  def size_of(self, a):
    return self.size[self.find(a)]

  def find(self, a):
    if a == self.par[a]:
      return a
    self.par[a] = self.find(self.par[a])
    return self.par[a]

Edge = namedtuple('Edge', 'w s t')
X = namedtuple('X', 'x i')
Y = namedtuple('Y', 'y i')

N = int(input())

edges = []
xg = []
yg = []

for i in range(N):
  x, y = map(int, input().split())
  xg.append(X(x, i))
  yg.append(Y(y, i))

xg.sort()
yg.sort()

for i in range(N - 1):
  x1, a = xg[i]
  x2, b = xg[i + 1]
  edges.append(Edge(abs(x1 - x2), a, b))

for i in range(N - 1):
  y1, a = yg[i]
  y2, b = yg[i + 1]
  edges.append(Edge(abs(y1 - y2), a, b))

edges.sort()

u = UnionFind(N)
cost = 0

for w, s, t in edges:
  if u.is_same(s, t):
    continue
  u.unite(s, t)
  cost += w

print(cost)
### BUGGY CODE ###

from collections import deque
S = input()
Q = int(input())

for _ in range(Q):
    query = deque(input().split())
    if query[0] == "1":
        S = list(S)
        S.reverse()
        S = "".join(map(str, S))
    elif query[1] == "1":
        S = query[2] + S
    elif query[1] == "2":
        S = S + query[2]

print(S)

### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
is_reversed = 1
for _ in range(Q):
    query = list(input().split())
    if query[0] == "1":
        is_reversed *= -1
    
    else:
        if is_reversed == 1:
            if query[1] == "1":
                S.appendleft(query[2])
            else:
                S.append(query[2])
        else:
            if query[1] == "2":
                S.appendleft(query[2])
            else:
                S.append(query[2])

S = "".join(S)
print(S[::is_reversed])
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]

for i in range(N):
    print(max(A[:i]+A[i+1:]))


### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
max_a = max(A)
max_count = A.count(max_a)
if max_count == 1:
    ind = A.index(max_a)
    max_b = max(A[:ind]+A[ind+1:])

for i in range(N):
    if max_count > 1:
        print(max_a)
    else:
        if A[i] == max_a:
            print(max_b)
        else:
            print(max_a)
### BUGGY CODE ###

from collections import defaultdict
n = int(input())
tree = dict()
graph = defaultdict(list)

for i in range(n-1):
    a,b,c = (int(x) for x in input().split())
    tree[a,b] = c
    tree[b,a] = c
    graph[a].append(b)
    graph[b].append(a)

q, k = (int(x) for x in input().split())

dist = dict()
stack = [k,]
visited = set()
dist[k] = 0
visited.add(k)
while stack:
    new_stack = []
    for node in stack:
        for next_node in graph[node]:
            if next_node not in visited:
                visited.add(next_node)
                dist[next_node] = dist[node] + tree[node, next_node]
                new_stack.extend(graph[node])
    stack = new_stack
for _ in range(q):
    x, y = (int(x) for x in input().split())
    print(dist[x] + dist[y])


### FIXED CODE ###

from collections import defaultdict
n = int(input())
tree = dict()
graph = defaultdict(list)

for i in range(n-1):
    a,b,c = (int(x) for x in input().split())
    tree[a,b] = c
    tree[b,a] = c
    graph[a].append(b)
    graph[b].append(a)

q, k = (int(x) for x in input().split())

dist = dict()
stack = [k,]
visited = [False for _ in range(n+1)]
dist[k] = 0
visited[k] = True

while stack:
    new_stack = []
    for node in stack:
        for next_node in graph[node]:
            if not visited[next_node]:
                visited[next_node]  = True
                dist[next_node] = dist[node] + tree[node, next_node]
                new_stack.append(next_node)
    stack = new_stack

for _ in range(q):
    x, y = (int(x) for x in input().split())
    print(dist[x] + dist[y])
### BUGGY CODE ###

N = int(input())
S = str(input())
cnt = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                if (j - i) != (k - j):
                    cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
S = str(input())
ans = S.count('R') * S.count('G') * S.count('B')
for i in range(N-1):
    for j in range(i+1,N):
        k = j + (j - i)
        if k < N and S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            ans -= 1
print(ans)
### BUGGY CODE ###

from itertools import product
import numpy as np
N, M = map(int, input().split())
original_M = M
# 素因数分解して N より大きい数になるまで積をかけた時、残りの数の積が答え
# M = N * a -> gcm : a
# M = 2 * b

U = 10**5 * 1
is_prime = np.full(U, True, dtype='bool')
is_prime[0:2] = False
for i in range(2, U):
    if i * i > U:
        break
    if is_prime[i]:
        is_prime[i * 2::i] = False

primes = np.arange(U)[is_prime]
v = []
while M not in primes:
    for prime in primes:
        if M % prime == 0:
            v.append(prime)
            M //= prime
            break
v.append(M)
v = np.array(v)
# print('v', v)
v_prod = [
    v[np.array(list(i), dtype='bool')].prod()
    for i in product([True, False], repeat=len(v))
]
v_prod = sorted(v_prod)
# print(v_prod)
idx = np.searchsorted(v_prod, N, side='left')
# print(v_prod[idx])
ans = original_M // v_prod[idx]
print(ans)


### FIXED CODE ###

# 1 <= N <= 10**5
# N <= M <= 10**9
import sys
input = sys.stdin.buffer.readline
N, M = map(int, input().split())

V = M // N

ans = 1
for i in range(1, V + 1):
    if i * i > M:
        break
    if M % i == 0:
        j = M // i
        if j <= V:
            ans = max(ans, j)
        else:
            ans = max(ans, i)
print(ans)
### BUGGY CODE ###

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

import sys
import os

N = int(input())

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

max_score = float("-inf")
for cut_i in range(N, 2 * N + 1):
    B = A[:cut_i]
    B.sort(reverse=True)
    C = A[cut_i:]
    C.sort()

    score = sum(B[:N]) - sum(C[:N])
    if score > max_score:
        max_score = score
        
print(max_score)


### FIXED CODE ###

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

import sys
import os
import heapq

N = int(input())

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

B = A[:N]
B_sum = sum(B)
heapq.heapify(B)
dict_b = {}

for i in range(N, 2 * N):
    a = A[i]
    min_val = heapq.heappop(B)
    greater = max(a, min_val)
    heapq.heappush(B, greater)

    if greater != min_val:
        B_sum += (a - min_val)
    dict_b[i] = B_sum


C = A[-N:]
C = [-c for c in C]
C_sum = -1 * sum(C)
heapq.heapify(C)
dict_c = {}

for i in range(2 * N - 1, N - 1, -1):
    a = A[i]
    max_val = -1 * heapq.heappop(C)
    fewer = min(a, max_val)
    heapq.heappush(C, -fewer)

    if fewer != max_val:
        C_sum -= (max_val - a)
    dict_c[i] = C_sum

max_score = max(sum(A[:N]) - dict_c[N], dict_b[2*N-1] - sum(A[-N:]))
for i in range(N, 2 * N - 1):
    score = dict_b[i] - dict_c[i+1]
    if score > max_score:
        max_score = score

print(max_score)
### BUGGY CODE ###


import sys
input = sys.stdin.readline

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

road = []
x_list = []
for i in range(N):
    s,t,x = list(map(int,input().split()))
    road.append(("s",s-x,x,0))
    road.append(("t",t-x,x,0))
    x_list.append(x)

for i in range(Q):
    d = int(input())
    road.append(("m",d,i,1))

road.sort(lambda x:x[3])
road.sort(lambda x:x[1])

x_list = list(set(x_list))
x_list.sort()

x2i_dict = {}
for i,x in enumerate(x_list):
    x2i_dict[x]=i


class BIT:
            
    def __init__(self, L):
        self.N = len(L)
        self.bit = [0]*self.N
        for i,l in enumerate(L):
            self.add(i,l)

    def add(self, a, w):
        x = a + 1
        for i in range(1000):
            self.bit[x-1] += w
            x += x & -x
            if x > self.N:
                break

    def sum(self, a):
        x = a+1
        ret = 0
        for i in range(1000):
            ret += self.bit[x-1]
            x -= x & -x
            if x <= 0:
                break        
        return ret

def bisectR(l,r,bit):
    while r-l>1:
        if bit.sum((l+r)//2)>0:
            r = (l+r)//2
        else:
            l = (l+r)//2
    return r


bit = BIT([0]*len(x_list))
ans = [0]*Q
for r in road:
    if r[0]=="s":
        bit.add(x2i_dict[r[2]],1)
    elif r[0]=="t":
        bit.add(x2i_dict[r[2]],-1)
    else:
        if bit.sum(len(x_list)-1)==0:
            ans[r[2]]=-1
        elif bit.sum(0)>0:
            ans[r[2]]=x_list[0]
        else:
            i = bisectR(0,len(x_list)-1,bit)
            ans[r[2]] = x_list[i]

for a in ans:
    print(a)

### FIXED CODE ###

import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

def main():
    N,Q = list(map(int,input().split()))

    road = []
    x_list = []

    for i in range(N):
        s,t,x = list(map(int,input().split()))
        road.append([0,s-x,x])
        road.append([1,t-x,x])

    for i in range(Q):
        road.append([2,int(input()),i])

    from collections import defaultdict

    counter = defaultdict(int)
    counter[10**27] = 1
    ans = [0]*Q

    road.sort(key=lambda x:x[0])
    road.sort(key=lambda x:x[1])

    q = [10**27]

    from heapq import heappop,heappush

    for id,_,x in road:
        if id==0:
            heappush(q,x)
            counter[x]+=1
        elif id==1:
            counter[x]-=1
        else:
            while counter[q[0]]==0:
                heappop(q)
            #print(q)
            if q[0]<10**27:
                ans[x] = q[0]
            else:
                ans[x] = -1
    print("\n".join(map(str,ans)))

if __name__ == '__main__':
    main()