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

h, w = map(int, input().split())
lst = [[0] for _ in range(h)]
for i in range(h):
    tmp = list(input())
    lst[i] = tmp

L = [[0] * w for _ in range(h)]
R = [[0] * w for _ in range(h)]
U = [[0] * w for _ in range(h)]
D = [[0] * w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if lst[i][j] == '#':
            continue
        if j == 0:
            L[i][j] = 1
        else:
            if lst[i][j] == '.':
                L[i][j] = L[i][j-1] + 1
            else:
                continue

for i in range(h):
    for j in range(w)[::-1]:
        if lst[i][j] == '#':
            continue
        if j == w-1:
            R[i][j] = 1
        else:
            if lst[i][j] == '.':
                R[i][j] = R[i][j+1] + 1
            else:
                continue

for i in range(h)[::-1]:
    for j in range(w):
        if lst[i][j] == '#':
            continue
        if i == h-1:
            D[i][j] = 1
        else:
            if lst[i][j] == '.':
                D[i][j] = D[i+1][j] + 1
            else:
                continue

for i in range(h):
    for j in range(w):
        if lst[i][j] == '#':
            continue
        if i == 0:
            U[i][j] = 1
        else:
            if lst[i][j] == '.':
                U[i][j] = U[i-1][j] + 1
            else:
                continue

ans = 0
for i in range(h):
    for j in range(w):
        if lst[i][j] != '#':
            tmp = L[i][j] + R[i][j] + D[i][j] + U[i][j] - 3
            ans = max(ans, tmp)

print(ans)

### FIXED CODE ###

h, w = map(int, input().split())
lst = [[0] for _ in range(h)]
for i in range(h):
    tmp = list(input())
    lst[i] = tmp

H = [[0] * w for _ in range(h)]
W = [[0] * w for _ in range(h)]

for i in range(h):
    done = [0] * w
    for j in range(w):
        if lst[i][j] == '#':
            continue
        if done[j]:
            continue
        k = 0
        while lst[i][j+k] != '#':
            done[j+k] = 1
            k += 1  # kが照らせるマスの長さ
            if j+k > w-1:
                break
        for l in range(k):
            H[i][j+l] = k


for j in range(w):
    done = [0] * h
    for i in range(h):
        if lst[i][j] == '#':
            continue
        if done[i]:
            continue
        k = 0
        while lst[i+k][j] != '#':
            done[i+k] = 1
            k += 1  # kが照らせるマスの長さ
            if i+k > h-1:
                break
        for l in range(k):
            W[i+l][j] = k

ans = 0
for i in range(h):
    for j in range(w):
        if lst[i][j] != '#':
            ans = max(ans, H[i][j] + W[i][j] - 1)

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

import bisect

n = int(input())
a = list(map(int, input().split()))
a.sort()
k = len(a)
ok = [0] * k
for i in range(k):
    if i < k - 1 and a[i] == a[i + 1]:
        ok[i] = 1
        ok[i+1] = 1;

    if a[i] < 2 * 100:
        for j in range(i + 1, k):
            if a[j] % a[i] == 0:
                ok[j] = 1
    else:   
        times = 2
        while a[i] * times <= a[-1]:
            r = bisect.bisect_left(a, a[i] * times + 1)
            l = bisect.bisect_left(a, a[i] * times)
            if r != l:
                for idx in range(l, r):
                    ok[idx] = 1
            times += 1
print(len([i for i in ok if i == 0]))
# print(ok) WAはどこ？


### FIXED CODE ###

import bisect

n = int(input())
a = list(map(int, input().split()))
a.sort()
k = len(a)
ok = [0] * k
for i in range(k):
    if i < k - 1 and a[i] == a[i + 1]:
        ok[i] = 1
        ok[i+1] = 1;
        continue

    if a[i] < 2 * 100:
        for j in range(i + 1, k):
            if a[j] % a[i] == 0:
                ok[j] = 1
    else:   
        times = 2
        while a[i] * times <= a[-1]:
            r = bisect.bisect_left(a, a[i] * times + 1)
            l = bisect.bisect_left(a, a[i] * times)
            if r != l:
                for idx in range(l, r):
                    ok[idx] = 1
            times += 1
print(len([i for i in ok if i == 0]))
# print(ok) WAはどこ？
### BUGGY CODE ###

def prob_d():
    n = int(input())
    a_list = [int(a) for a in input().split()]
    sum_list = sum(a_list)
    ans_list = [sum_list - sum(a_list[1::2]) * 2] + [sum_list - sum(a_list[2::2]) * 2] + \
               [sum_list - sum(a_list[(i+1)::2]) * 2 -
                sum(a_list[i % 2:i-1:2]) * 2 for i in range(2, n-1)] + \
               [sum_list - sum(a_list[0:(n-2):2]) * 2]
    print(" ".join([str(a) for a in ans_list]))

prob_d()

### FIXED CODE ###

def prob_d():
    n = int(input())
    a_list = [int(a) for a in input().split()]
    even_sum = sum(a_list[2::2])
    odd_sum = sum(a_list[1::2])
    sum_list = even_sum + odd_sum + a_list[0]
    ans = ""
    for i in range(n):
        if i % 2 == 0:
            ans += str(sum_list - odd_sum * 2)
            if i != n-1:
                odd_sum -= a_list[i+1]
                odd_sum += a_list[i]
        else:
            ans += str(sum_list - even_sum * 2)
            if i != n-1:
                even_sum -= a_list[i+1]
                even_sum += a_list[i]
        if i != n-1:
            ans += " "
    print(ans)

prob_d()
### BUGGY CODE ###

s=input()
kk=int(input())

dic={}
for i in range(len(s)):
    dic[s[i]]=1
    
dic=sorted(dic,key=lambda x:x[0])
check=0
se=set()
for i in dic:
    for j in range(len(s)):
        if s[j]!=i:
            continue
        k=j+1
        se.add(i)
        sss=i
        while k<len(s):
            sss+=s[k]
            se.add(sss)
            k+=1
    if len(se)>=kk:
        break
se=sorted(list(se))
print(se[kk-1])
    

### FIXED CODE ###

s=input()
kk=int(input())

dic={}
for i in range(len(s)):
    dic[s[i]]=1
    
dic=sorted(dic,key=lambda x:x[0])
check=0
se=set()
for i in dic:
    for j in range(len(s)):
        if s[j]!=i:
            continue
        k=j+1
        se.add(i)
        sss=i
        while k<len(s):
            sss+=s[k]
            se.add(sss)
            k+=1
            if k-j>kk:
                break
    if len(se)>=kk:
        break
se=sorted(list(se))
print(se[kk-1])
### BUGGY CODE ###

s = input()
q = int(input())

rv = False
for i in range(q):
    line = input()
    if line[0] == '1':
        rv = ~rv
    else:
        ti, fi, ci = line.split()
        if (fi == '1' and rv) or (fi == '2' and not rv):
            s = s + ci
        else:
            s = ci + s
if rv:
    print(s[::-1])
else:
    print(s)

### FIXED CODE ###

import sys
s = sys.stdin.readline()
s = s[:-1]
q = int(input())

front = ''
back = ''
rv = False
for i in range(q):
    line = input()
    if line[0] == '1':
        rv = not rv
    else:
        ti, fi, ci = line.split()
        if (fi == '1' and rv) or (fi == '2' and not rv):
            back += ci
        else:
            front += ci

if rv:
    s = back[::-1] + s[::-1] + front
else:
    s = front[::-1] + s + back
print(s)
### BUGGY CODE ###

import re

N = int(input().strip())
# C = [c for c in input().strip()]
C = input().strip()

G = re.compile(r"^R*W*$")
cnt = 0


def rep(i, c, r, w):
    if i == r:
        return "W"
    elif i == w:
        return "R"
    else:
        return c

while not G.match(C):
    cnt += 1
    r = C.rfind("R")
    w = C.find("W")
    C = "".join([
        rep(i, c, r, w)
        for i, c in enumerate(C)
    ])
    # break

print(cnt)

### FIXED CODE ###

N = int(input().strip())
C = [c for c in input().strip()]

if "W" not in C or "R" not in C:
    print(0)
    import sys; sys.exit(0)

cnt = 0

i = 0
j = len(C) - 1
while i < j:
    while C[i] == "R":
        i += 1
    while C[j] == "W":
        j -= 1
    if i > j:
        break
    cnt += 1
    C[i] = "R"
    C[j] = "W"
    i += 1
    j -= 1

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

N,M=map(int, input().split())
a=[int(input()) for _ in range(M)]
D=1000000007

DP=[0 for _ in range(N+10)]
DP[0]=1
for i in range(N):
  for j in [1,2]:
    if i+j not in a:
      DP[i+j]+=DP[i]
      
print(DP[N]%D)

### FIXED CODE ###

N,M=map(int, input().split())
a=[True for _ in range(N+10)]
for _ in range(M):
  a[int(input())]=False
D=1000000007

DP=[0 for _ in range(N+10)]
DP[0]=1
for i in range(N):
  for j in [1,2]:
    if a[i+j]:
      DP[i+j]+=DP[i]
      
print(DP[N]%D)
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
s = [0] * 30
t = [1] * 30
for i in range(29):
    t[i + 1] = t[i] * 2
for i in range(N):
    aa = a[i]
    for j in range(30):
        s[j] = (s[j] + aa)%2
        aa = aa//2
for i in range(N):
    ans = a[i]
    for j in range(30):
        ans1 = a[i]%2
        a[i] = a[i]//2
        if s[j] == 1:
            if ans1 == 1:
                ans -= t[j] 
            else:
                ans += t[j]
    print(ans,end = " ")
print()

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
s = [0] * 30
t = [1] * 30
for i in range(29):
    t[i + 1] = t[i] * 2
ss = a[0]
for j in range(N - 1):
    ss = ss ^ a[j + 1]
for j in range(N):
    print(a[j] ^ ss,end = " ")
print()
### BUGGY CODE ###

import sys
N, M = map(int,input().split())
edge = [[] for i in range(N+1)]
for _ in range(M):
    a, b = map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
for i in range(2, N):
    if i in edge[1] and N in edge[i]:
        print('POSSIBLE')
        sys.exit()
print('IMPOSSIBLE')

### FIXED CODE ###

from collections import defaultdict
N, M = map(int,input().split())
d = defaultdict(int)
for _ in range(M):
    a, b = map(int,input().split())
    if a == 1:
        d[b] += 1
    if b == N:
        d[a] += 1
if 2 in d.values():
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

A, B, M = [int(x) for x in input().split()]
A_price_list = [int(x) for x in input().split()]
B_price_list = [int(x) for x in input().split()]

discount_list = [[0 for j in range(B)] for i in range(A)]

for i in range(M):
    x, y, c = ([int(x) for x in input().split()])
    discount_list[x-1][y-1] = max(discount_list[x-1][y-1], c)


amount = 9999999999999999999999999
for i in range(A):
    for j in range(B):
        tmp_amount = A_price_list[i] + B_price_list[j] - discount_list[i][j]
        amount = min(amount, tmp_amount)

print(amount)

### FIXED CODE ###

A, B, M = [int(x) for x in input().split()]
A_price_list = [int(x) for x in input().split()]
B_price_list = [int(x) for x in input().split()]

discount_list = []

for i in range(M):
    x, y, c = [int(x) for x in input().split()]
    discount_list.append([x-1, y-1, c])


amount = min(A_price_list) + min(B_price_list)

for x, y, c in discount_list:
    tmp_price = A_price_list[x] + B_price_list[y] - c
    amount = min(tmp_price, amount)

print(amount)
### BUGGY CODE ###

#!/usr/bin/env python3

import heapq

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input()+'#') for _ in range(h)]+[['#']*(w+2)]
costs=[[10**18]*(w+1) for _ in range(h+1)]
costs[sy][sx]=0
q=[]
heapq.heappush(q,(0,sy,sx))
while len(q)!=0:
  cost,y,x=heapq.heappop(q)
  if y==gy and x==gx:
    print(cost)
    exit()
  for dy,dx in [[-1,0],[1,0],[0,-1],[0,1]]:
    if 1<=y+dy<=h and 1<=x+dx<=w and board[y+dy][x+dx]=='.' and costs[y+dy][x+dx]>costs[y][x]:
      costs[y+dy][x+dx]=costs[y][x]
      heapq.heappush(q,(cost,y+dy,x+dx))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dy==0 and dx==0:
        continue
      if 1<=y+dy<=h and 1<=x+dx<=w and board[y+dy][x+dx]=='.' and costs[y+dy][x+dx]>costs[y][x]+1:
        costs[y+dy][x+dx]=costs[y][x]+1
        heapq.heappush(q,(cost+1,y+dy,x+dx))
print(-1)

### FIXED CODE ###

#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input().replace('\n','')+'#') for _ in range(h)]+[['#']*(w+2)]
scores=[[10**18]*(w+2) for _ in range(h+2)]
scores[sy][sx]=0
q=collections.deque()
q.append((sy,sx))
count=0
while len(q)!=0:
  y,x=q.popleft()
  for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
    if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]:
      scores[y+dy][x+dx]=scores[y][x]
      q.appendleft((y+dy,x+dx))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dx==0 and dy==0:
        continue
      if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]+1:
        scores[y+dy][x+dx]=scores[y][x]+1
        q.append((y+dy,x+dx))
if scores[gy][gx]==10**18:
    print(-1)
else:
    print(scores[gy][gx])
### BUGGY CODE ###

N,M,Q=map(int, input().split())
matrix=[]
for _ in range(Q):
    c=list(map(int, input().split()))
    matrix.append(c)
import itertools
scorelist=[]
for i in itertools.product(range(1,M+1), repeat=N):
    i = list(i)
    i.sort()
    score=0
    for l in matrix:
        a=l[0]
        b=l[1]
        c=l[2]
        d=l[3]
        if i[b-1]-i[a-1]==c:
            score+=d
    scorelist.append(score)
print(max(scorelist))

### FIXED CODE ###

#import numpy as np
N,M,Q=map(int, input().split())
matrix=[]
for _ in range(Q):
    c=list(map(int, input().split()))
    matrix.append(c)
#matrix = np.array(matrix)
import itertools
ansscore = 0
combi = list(itertools.combinations_with_replacement(range(1,M+1),N))
for i in combi:
    i = list(i)
    i.sort()
    score=0
    for l in matrix:
        a=l[0]
        b=l[1]
        c=l[2]
        d=l[3]
        if i[b-1]-i[a-1]==c:
            score+=d
    ansscore = score if score>ansscore else ansscore

print(ansscore)
### BUGGY CODE ###

L, R = map(int, input().split())
min = 2019
modulo = 2019
for i in range(L, R + 1):
  for j in range(i + 1, R + 1):
    if (i == 2019 or j == 2019):
      min = 0
      break
    else:
      modulo = (i * j) % 2019
      if (modulo < min ):
        min = modulo
print(min)

### FIXED CODE ###

lr = input().split()
l = int(lr[0])
r = int(lr[1])
 
mini = 2018
 
for i in range(l, r+1):
  for j in range(i+1, r+1):
    mini = min(mini, (i*j)%2019)
 
    if mini==0:
      break
  if mini==0:
    break
print(mini)
### BUGGY CODE ###

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

for s in range(1, n+1):
    print(a.index(s) + 1, end=" ")


### FIXED CODE ###

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

out = sorted(range(1, len(a)+1 ), key=lambda i: a[i-1])
print(" ".join(map(str, out)))
### BUGGY CODE ###

inf = 10**9 + 7
n, k = map(int, input().split())

nodes = list(map(int, input().split()))
dp = [inf] * n

dp[0] = 0

# for i in range(n):
#     for j in range(i+1, min(i+k+1, n)):
#         dp[j] = min(dp[j], dp[i] + abs(nodes[i] - nodes[j]))
for i in range(n):
    for j in range(1, min(k+1, n-i)):
        dp[i+j] = min(dp[i+j], dp[i]+abs(nodes[i]-nodes[i+j]))
print(dp[n-1])


### FIXED CODE ###

inf = 10**9 + 7
n, k = map(int, input().split())

nodes = list(map(int, input().split()))
dp = [inf] * n

dp[0] = 0

for i in range(n):
    for j in range(i+1, min(i+k+1, n)):
        dp[j] = min(dp[j], dp[i] + abs(nodes[i] - nodes[j]))
# for i in range(n):
#     for j in range(1, min(k+1, n-i)):
#         dp[i+j] = min(dp[i+j], dp[i]+abs(nodes[i]-nodes[i+j]))
print(dp[n-1])
### BUGGY CODE ###

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

R = 0

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

print(R)


### FIXED CODE ###

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

R = 0

for X in range(max(0, S-2*K), K+1):
    for Y in range(max(0, S-X-K), K+1):
        if X + Y <= S:
            R += 1

print(R)
### BUGGY CODE ###

import copy

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

list_tmp = []
list_A = []
dict_AB = {}
for i in range(N):
    A, B = map(int, input().split())
    if dict_AB.get(A) is None:
        dict_AB[A] = B
    else:
        list_tmp.append((A, B))
    list_A.append(A)

list_A.sort()

ct = 0
money = 0
for i in list_A:
    A = i
    tmp = copy.deepcopy(list_tmp)
    if tmp:
        for j in list_tmp:
            if j[0] == A:
                B = j[1]
                list_tmp.remove((A, B))
                break
            else:
                B = dict_AB[A]
    else:
        B = dict_AB[A]

    money += A*B
    ct += B
    if ct >= M:
        money -= (ct - M)*A
        break

print(money)


### FIXED CODE ###

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

AB = []
for i in range(N):
    AB.append(list(map(int, input().split())))

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

ct = 0
money = 0
for i in AB:
    A, B = i[0], i[1]
    for i in range(B):
        money += A
        ct += 1
        if ct == M:
            break
    if ct == M:
        break

print(money)
### BUGGY CODE ###

nb=int(input())
liste = [int(x) for x in input().split()]
liste2= [0]*((10**5)+1)
for loop in range(len(liste)):
  liste2[liste[loop]] +=1
nba = int(input())
somme = sum(liste)
for loop in range(nba):
  n,r = map(int,input().split())
  roger = liste2[n]
  for loop in range(len(liste)):
    if liste[loop]==n:
      liste[loop] = r
  diff = r-n
  somme += diff * roger
  liste2[r] += liste2[n]
  liste2[n] = 0
  print(somme)

### FIXED CODE ###

nb=int(input())
liste = [int(x) for x in input().split()]
liste2= [0]*((10**5)+1)
for loop in range(len(liste)):
  liste2[liste[loop]] +=1
nba = int(input())
somme = sum(liste)
for loop in range(nba):
  n,r = map(int,input().split())
  roger = liste2[n]
  diff = r-n
  somme += diff * roger
  liste2[r] += liste2[n]
  liste2[n] = 0
  print(somme)
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
ans = 0

for i in range(N):
  if min(list(P[0:i+1])) == P[i]:
    ans += 1
    
print(ans)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
ans = 0
min_number = 2*10**5+1

for i in range(N):
  min_number = min(min_number, P[i])
  if min_number == P[i]:
    ans += 1
  
print(ans)
### BUGGY CODE ###

n = input()
a = list(map(int,input().split()))
ans = 1
for i in range(int(n)):
  ans *= a[i]
if ans>1000000000000000000: print(-1)
else: print(ans) 

### FIXED CODE ###

n = input()
a = list(map(int,input().split()))
ans = 1
for i in range(int(n)):
  ans *= a[i]
  if ans>1000000000000000000:
    ans = -1
    break
for i in range(int(n)):
  if a[i] == 0:
    ans = 0
print(ans)
### BUGGY CODE ###

from collections import Counter
 
N = int(input())
A = list(map(int,input().split()))
a = list(set(A))
cc = Counter(A)
dup = [x for x in a if cc[x] > 1]
c_l = [(cc[i]-1)*(cc[i])/2 for i in a]
al = sum(c_l)
 

[print(int(al-cc[k]+1)) if k in dup else print(int(al)) for k in A]

### FIXED CODE ###

from collections import Counter

N = int(input())
A = list(map(int,input().split()))
a = list(set(A))
cc = Counter(A)
dup = set([x for x in a if cc[x] > 1])
c_l = [(cc[i]-1)*(cc[i])/2 for i in a]
al = sum(c_l)

# for k in A:
#     if k in dup:
#         print(int(al-cc[k]+1))
#     else :
#         print(int(al))
[print(int(al-cc[k]+1)) if k in dup else print(int(al)) for k in A]
### BUGGY CODE ###

S=input()
x,y=map(int,input().split())
Xmove=[]
Ymove=[]
xdist=True
cnt=0
for i in range(len(S)):
  if S[i]=="T":
    if xdist:
      Xmove.append(cnt)
    else:
      Ymove.append(cnt)
    cnt=0
    xdist^=True
  else:
    cnt+=1
if S[-1]=="F":
  if xdist:
    Xmove.append(cnt)
  else:
    Ymove.append(cnt)

Xmax=sum(Xmove)
Ymax=sum(Ymove)
dpX=[[False for j in range(Xmax*2+10)] for i in range(len(Xmove)+1)]
dpY=[[False for j in range(Ymax*2+10)] for i in range(len(Ymove)+1)]

indX=0
if S[0]=="F":
  dpX[1][Xmax+Xmove[0]]=True
  indX=1
else:
  dpX[0][Xmax]=True
dpY[0][Ymax]=True

for i in range(indX,len(Xmove)):
  for j in range(len(dpX[i])):
    if dpX[i][j]:
      dpX[i+1][j-Xmove[i]]=True
      dpX[i+1][j+Xmove[i]]=True

if not dpX[-1][x+Xmax]:
  print("No")
  exit(0)

for i in range(len(Ymove)):
  for j in range(len(dpY[i])):
    if dpY[i][j]:
      dpY[i+1][j+Ymove[i]]=True
      dpY[i+1][j-Ymove[i]]=True

print(("No","Yes")[dpY[-1][y+Ymax]])

### FIXED CODE ###

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

# [文字,その文字が連続する数]
from collections import deque
sumS = deque()
import itertools
for key,g in itertools.groupby(S):
  sumS.append([key,len(list(g))])
  
startx = 0 # Fで始まる場合はX軸の正の方向にあらかじめ進めて置く
# 最初のTが出るまではX軸正の方向に進む
if sumS[0][0] == "F":
  startx = sumS[0][1]
  sumS.popleft()

xdir = True # X軸方向を向いている
dpXcur = set()
dpXcur.add(startx)
dpYcur = set()
dpYcur.add(0) # Y軸は必ず0から始まる
dpXnex = set()
dpYnex = set()
for i in range(len(sumS)):
  if sumS[i][0] == "F":
    steps = sumS[i][1] # 進む数
    if xdir: # X軸方向を向いている場合
      for x in dpXcur:
        dpXnex.add(x + steps)
        dpXnex.add(x - steps)
      dpXcur = dpXnex
      dpXnex = set()
    else:
      for y in dpYcur:
        dpYnex.add(y + steps)
        dpYnex.add(y - steps)
      dpYcur = dpYnex
      dpYnex = set()
  elif sumS[i][0] == "T":
    turns = sumS[i][1] # 方向転換する数
    if turns % 2 == 1:
      # 奇数回の場合はX/Y軸の切り替え (偶数回の場合は何も起こらない)
      xdir ^= True
      
if X in dpXcur and Y in dpYcur:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    G[L].append((R, D))
    G[R].append((L, -D))

visited = [False] * N
for i in range(N):
    if not visited[i]:
        dist = [float('inf')] * N
        dist[i] = 0
        stack = [i]
        while stack:
            v = stack.pop()
            visited[v] = True
            for u, d in G[v]:
                if dist[u] == float('inf'):
                    dist[u] = dist[v] + d
                elif dist[u] != dist[v] + d:
                    print('No')
                    exit()
                if not visited[u]:
                    stack.append(u)
print('Yes')


### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    G[L].append((R, D))
    G[R].append((L, -D))

visited = [False] * N
dist = [float('inf')] * N
for i in range(N):
    if not visited[i]:
        dist[i] = 0
        stack = [i]
        while stack:
            v = stack.pop()
            visited[v] = True
            for u, d in G[v]:
                if dist[u] == float('inf'):
                    dist[u] = dist[v] + d
                elif dist[u] != dist[v] + d:
                    print('No')
                    exit()
                if not visited[u]:
                    stack.append(u)
print('Yes')
### BUGGY CODE ###

import heapq
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N, Q = list(map(int, next(sys.stdin).split()))
STX = [list(map(int, next(sys.stdin).split())) for _ in range(N)]
D = [int(next(sys.stdin)) for _ in range(Q)]

# (d, x, 0 or 1) のリスト
events = []

for xi, [s, t, x] in enumerate(STX):
    # [lo, hi) に出発した人は x で止まる
    lo = s - x
    hi = t - x
    events.append((lo, x, 1))  # 追加
    events.append((hi, x, 0))  # 削除

events.sort()
ev = 0
closes = set()
heap = []
for d in D:
    while ev < len(events) and events[ev][0] <= d:
        t, x, op = events[ev]
        if op == 1:
            closes.add(x)
            heapq.heappush(heap, x)
        else:
            closes.remove(x)
        ev += 1
    while heap and heap[0] not in closes:
        heapq.heappop(heap)
    if heap:
        print(heap[0])
    else:
        print(-1)


### FIXED CODE ###

import bisect
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N, Q = list(map(int, next(sys.stdin).split()))
STX = [list(map(int, next(sys.stdin).split())) for _ in range(N)]
D = [int(next(sys.stdin)) for _ in range(Q)]

ans = [-1 for _ in range(Q)]
nexts = [-1 for _ in range(Q)]

for s, t, x in sorted(STX, key=lambda stx: (stx[2], stx[1])):
    # [lo, hi) に出発した人は x で止まる
    # x の小さい順にソート済みなのでここで確定
    lo = max(0, bisect.bisect_left(D, s - x))
    hi = min(len(D), bisect.bisect_left(D, t - x))

    p = lo
    while p < hi:
        if nexts[p] == -1:
            ans[p] = x
            nexts[p] = hi
            p += 1
        else:
            prev = p
            p = nexts[p]
            nexts[prev] = hi

for a in ans:
    print(int(a))