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

n, m = map(int, input().split())
d = {}
ans = [0] * (n)
for _ in range(m):
    a, b = map(int, input().split())
    if not a in d.keys():
        d[a] = [b]
    elif not b in d[a]:
        d[a].append(b)
    if not b in d.keys():
        d[b] = [a]
    elif not a in d[b]:
        d[b].append(a)

q = [1]
while not len(q) == 0:
    x = q.pop(0)
    for i in d[x]:
        if ans[i-1] == 0:
            ans[i-1] = x
        q.append(i)
if 0 in ans:
    print('No')
else:
    print('Yes')
    for j in ans[1:]:
        print(j)

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
d = [[] for _ in range(n+1)]
ans = [0] * (n)
for _ in range(m):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)

q = deque([1])
while not len(q) == 0:
    x = q.popleft()
    for i in d[x]:
        if ans[i-1] == 0:
            ans[i-1] = x
            q.append(i)

if 0 in ans:
    print('No')
else:
    print('Yes')
    s  = "\n".join(map(str, ans[1:]))
    print(s)
### BUGGY CODE ###

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

dp = [float('inf')] * n

dp[0] = 0

for i in range(1, n):
    for j in range(1, k+1):
        if i - j < 0:
            continue
        dp[i] = min(dp[i], dp[i-j] + abs(h[i] - h[i-j]))

print(dp[n-1])


### FIXED CODE ###

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

dp = [float('inf')] * n

dp[0] = 0

for i in range(1, n):
    for j in range(1, k+1):
        if i - j < 0:
            continue
        dp[i] = min(dp[i], dp[i-j] + abs(h[i] - h[i-j]))

print(dp[n-1])
### BUGGY CODE ###

N,K,Q=map(int,input().split())
A=[K]*N
for q in range(Q):
  win=int(input())
  for i,j in enumerate(A):
    if i!=win-1:
      A[i]-=1
for i,j in enumerate(A):
    if j >0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

N,K,Q=map(int,input().split())
A=[0]*N
for i in range(Q):
    A[int(input())-1]+=1
for j in range(N):
    if K-Q+A[j]>0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from collections import deque

H,W = map(int,input().split())
A = [list(input()) for i in range(H)]

directions = [[-1,0],[1,0],[0,-1],[0,1]]

D = [[-1]*W for i in range(H)]

B = []
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            B.append([i,j])
            D[i][j] = 0

q = deque(B)

while q:
    nh,nw= q.pop()
    for dh,dw in directions:
        if not (0<= nh+dh < H and 0 <= nw+dw < W):
            continue
        elif D[nh+dh][nw+dw] != -1:
            continue
        elif A[nh+dh][nw+dw] == '#':
            D[nh+dh][nw+dw] = D[nh][nw]
            q.append([nh+dh,nw+dw])
        elif A[nh+dh][nw+dw] == '.':
            D[nh+dh][nw+dw] = D[nh][nw]+1
            q.appendleft([nh+dh,nw+dw])

print(max(max(D[i]) for i in range(H)))

### FIXED CODE ###

from collections import deque

H,W = map(int,input().split())
A = [list(input()) for i in range(H)]

directions = [[-1,0],[1,0],[0,-1],[0,1]]

D = [[-1]*W for i in range(H)]

B = []
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            B.append([i,j])
            D[i][j] = 0

q = deque(B)

while q:
    nh,nw= q.pop()
    for dh,dw in directions:
        if not (0<= nh+dh < H and 0 <= nw+dw < W):
            continue
        elif D[nh+dh][nw+dw] != -1:
            continue
        elif A[nh+dh][nw+dw] == '#':
            D[nh+dh][nw+dw] = D[nh][nw]
            q.append([nh+dh,nw+dw])
        elif A[nh+dh][nw+dw] == '.':
            D[nh+dh][nw+dw] = D[nh][nw]+1
            q.appendleft([nh+dh,nw+dw])

print(max(max(D[i]) for i in range(H)))
### BUGGY CODE ###

import math
import sys
from copy import copy
import numpy as np
from collections import defaultdict, deque, Counter 
from itertools import accumulate, product, permutations,combinations, combinations_with_replacement
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from fractions import gcd

max_value = 1000000000
min_value = -1000000000
sys.setrecursionlimit(max_value)

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

count = 0


if s[0] == 'W' or s[-1] == 'W':
    print(0)
    sys.exit()

LR_list = ['' for i in range(2*n)]
LR_list[0] = 'L'

for i in range(1,len(LR_list)):
    if s[i] == s[i-1]:
        if LR_list[i-1] == 'R':
            LR_list[i] = 'L'
        else:
            LR_list[i] = 'R'
    else:
        if LR_list[i-1] == 'R':
            LR_list[i] = 'R'
        else:
            LR_list[i] = 'L'

values = []

if LR_list.count('L') != LR_list.count('R'):
    print(0)
    sys.exit()
for i in range(len(LR_list)):
    if LR_list[i] == 'R':
        li = LR_list[:i].count('L')
        ri = LR_list[:i].count('R')
        values.append(li-ri)
print(np.array(values).prod()*math.factorial(n))



### FIXED CODE ###

import math
import sys
from copy import copy
import numpy as np
from collections import defaultdict, deque, Counter 
from itertools import accumulate, product, permutations,combinations, combinations_with_replacement
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from fractions import gcd

max_value = 1000000000
min_value = -1000000000
sys.setrecursionlimit(max_value)

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

count = 0


if s[0] == 'W' or s[-1] == 'W':
    print(0)
    sys.exit()

LR_list = ['' for i in range(2*n)]
LR_list[0] = 'L'

for i in range(1,len(LR_list)):
    if s[i] == s[i-1]:
        if LR_list[i-1] == 'R':
            LR_list[i] = 'L'
        else:
            LR_list[i] = 'R'
    else:
        if LR_list[i-1] == 'R':
            LR_list[i] = 'R'
        else:
            LR_list[i] = 'L'

values = []

if LR_list.count('L') != LR_list.count('R'):
    print(0)
    sys.exit()


li = 0
ri = 0
for i in range(len(LR_list)):
    if i != 0:
        if LR_list[i-1] == 'L':
            li += 1
        elif LR_list[i-1] == 'R':
            ri += 1
    if LR_list[i] == 'R':
        values.append(li-ri)
value = 1
for i in range(len(values)):
    value = value * values[i] % (10**9+7)
for i in range(2,n+1):
    value = value * i %(10**9+7)
print(value)
### BUGGY CODE ###

import sys
#大きすぎるとダメ
sys.setrecursionlimit(2700)
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
inf=1000000000000000
d=[[inf]*w for i in range(h)]


def dfs(i,j):
    global h,w,s
    nex=[(0,-1),(0,1),(-1,0),(1,0)]
    for k in range(4):
        l,m=i+nex[k][0],j+nex[k][1]
        if 0<=i+nex[k][0]<h and 0<=j+nex[k][1]<w:
            if s[l][m]=="." and d[l][m]>d[i][j]+1:
                d[l][m]=d[i][j]+1
                dfs(l,m)
d[0][0]=0
dfs(0,0)
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ans+=1
if d[h-1][w-1]==inf:
    print(-1)
else:
    print(ans-d[h-1][w-1]-1)




### FIXED CODE ###

#一個だけRE、わからねえ
#解答見る
import sys
sys.setrecursionlimit(1005)
h,w=map(int,input().split())

def go_next(I,J,n):
    n+=1
    global dp,w,h
    if n>1000:
        return
    if 0<=I<h-1:
        if x[I+1][J]=="." and dp[I+1][J]>dp[I][J]+1:
            dp[I+1][J]=dp[I][J]+1
            go_next(I+1,J,n)
    if 0<I<=h-1:
        if x[I-1][J]=="." and dp[I-1][J]>dp[I][J]+1:
            dp[I-1][J]=dp[I][J]+1
            go_next(I-1,J,n)
    if 0<=J<w-1:
        if x[I][J+1]=="." and dp[I][J+1]>dp[I][J]+1:
            dp[I][J+1]=dp[I][J]+1
            go_next(I,J+1,n)
    if 0<J<=w-1:
        if x[I][J-1]=="." and dp[I][J-1]>dp[I][J]+1:
            dp[I][J-1]=dp[I][J]+1
            go_next(I,J-1,n)

x=[]
for i in range(h):
    x.append(list(input()))
#print(x)
c=0
for i in range(h):
    for j in range(w):
        if x[i][j]==".":
            c+=1
dp=[[10000000000 for i in range(w)]for j in range(h)]
dp[0][0]=1
go_next(0,0,0)
if dp[h-1][w-1]==10000000000:
    print(-1)
else:
    print(c-dp[h-1][w-1])
### BUGGY CODE ###

import numpy as np
n = list(map(int,input().split()))
a = np.array(list(map(int,input().split())))
for i in range(n[1]):
    a[a.argmax()] = a[a.argmax()]//2 
print(np.sum(a))


### FIXED CODE ###


N, M = map(int,input().split())
A = list(-int(i) for i in input().split())
import heapq

heapq.heapify(A)
for _ in range(M):
    a = heapq.heappop(A)//(-2)
    heapq.heappush(A,-a)

print(-sum(A))
### BUGGY CODE ###

import itertools

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

divided = []
ans = 0
for i in range(N):
    count = A_list.count(i + 1)
    divided.append(count)
    ans += len(list(itertools.combinations(range(count), 2)))

for k in range(1, N + 1):
    n = divided[A_list[k - 1] - 1]
    ans_k = ans
    if n > 1:
        ans_k -= n - 1

    print(int(ans_k))

### FIXED CODE ###

import collections
import math

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

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

counts = collections.Counter(A_list)
ans = 0
for _, v in counts.items():
    # ans += len(list(itertools.combinations(range(v), 2)))
    if v > 1:
        ans += combinations_count(v, 2)

for k in range(1, N + 1):
    n = counts[A_list[k - 1]]
    ans_k = ans
    if n > 1:
        ans_k -= n - 1

    print(int(ans_k))
### BUGGY CODE ###

from collections import deque
n,m=map(int,input().split())
G=[[] for i in range(n)]

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

for i in range(n):
    dist=[None]*n
    q=deque()
    if dist[i]==None:
        dist[i]=0
    q.append(i)
    while q:
        cur=q.popleft()
        for nx,d in G[cur]:
            if dist[nx]==None:
                dist[nx]=dist[cur]+d
                q.append(nx)
            elif dist[nx]!=dist[cur]+d:
                print('No')
                exit()
print('Yes')


### FIXED CODE ###

# D - People on a Line
from collections import deque
n,m=map(int,input().split())
dist=[None]*n
edge=[[] for i in range(n)]

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

for i in range(n):
    q=deque()
    if dist[i]==None:
        dist[i]=0
        q.append(i)
    while q:
        cur=q.popleft()
        for nx,d in edge[cur]:
            if dist[nx]==None:
                dist[nx]=dist[cur]+d
                q.append(nx)
            elif dist[nx]!=dist[cur]+d:
                print('No')
                exit()
print('Yes')
### BUGGY CODE ###

"""
AtCoder :: Beginner Contest 174 :: Logs
https://atcoder.jp/contests/abc174/tasks/abc174_e
"""
import sys
import math
import heapq


def main():
    """Main program."""
    log_count, cut_count = (int(i) for i in sys.stdin.readline().split())
    logs = [(-float(i), 0, float(i)) for i in sys.stdin.readline().split()]
    heapq.heapify(logs)
    for _ in range(cut_count):
        curr_length, cuts, init_length = heapq.heappop(logs)
        curr_length, cuts = -curr_length, -cuts
        cuts += 1
        curr_length = init_length / (cuts + 1)
        heapq.heappush(logs, (-curr_length, -cuts, init_length))
    print(math.ceil(-logs[0][0]))


if __name__ == '__main__':
    main()

### FIXED CODE ###

"""
AtCoder :: Beginner Contest 174 :: Logs
https://atcoder.jp/contests/abc174/tasks/abc174_e
"""
import sys
from math import ceil


def main():
    """Main program."""
    log_count, cut_count = (int(i) for i in sys.stdin.readline().split())
    logs = [int(i) for i in sys.stdin.readline().split()]
    high = max(logs)
    low = 1
    soln = high
    # Binary search for the answer.
    while low <= high:
        mid = (low + high) // 2
        cuts_needed = sum([int(ceil(log / mid)) - 1 for log in logs])
        if cuts_needed <= cut_count:
            soln = min(soln, mid)
            high = mid - 1
        else:
            low = mid + 1
    print(soln)


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

N = int(input())
A = list(map(int,input().split()))
M = 1000001
cnt = [0]*M
ans = 0
for x in A:
    if cnt[x] != 0:
        cnt[x] = 2
    for i in range(x,M,x):
        cnt[i] += 1
for x in A:
    if cnt[x] == 1:
        ans += 1
print(ans)

    


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
M = 1000001
cnt = [0]*M
ans = 0
for x in A:
    if cnt[x] != 0:
        cnt[x] = 2
        continue
    for i in range(x,M,x):
        cnt[i] += 1
for x in A:
    if cnt[x] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for i in range(Q)]
B = [K-Q]*N

for i in range(N-1):
    B[i] += A.count(i+1)

for i in range(N):
    if B[i] > 0:
        print("Yes")
    else:
        print("No")



### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for i in range(Q)]
B = [K-Q]*N

for i in range(Q):
    B[A[i]-1] += 1
    
for i in range(N):
#if A.count(i+1) > S :
#      B[i] += S + A.count(i+1)

    if B[i] > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

s=input()
#s = ("2020 2040")
#print(s) 
s = s.split(" ")
 
L = int( s[0] )
R = int( s[1] )
 
 
result =4.0e9  
for i in range(L,R):
    for j in range(i+1,R+1):
        mod = i*j % 2019
        #print(i,j,i*j,mod)
        if result > mod:
            result = mod
 
print(result)

### FIXED CODE ###

s=input()
#s = ("2020 2040")
#print(s) 
s = s.split(" ")
 
L = int( s[0] )
R = int( s[1] )
 
 
result =4.0e9  
for i in range(L,min(L+2019,R)):
    for j in range(i+1,min(R+1,L+2020)):
        mod = i*j % 2019
        #print(i,j,i*j,mod)
        if result > mod:
            result = mod
 
print(result)
### BUGGY CODE ###

N,M = map(int,input().split())
l = M//N
if M+1-N < l:
    for i in range(N,M+1):
        if M%i == 0:
            print(M//i)
            break
else:
    for i in range(l,-1,-1):
        if M % i == 0:
            print(i)
            break

### FIXED CODE ###

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

m = M
f = {}
while m%2 == 0:
    f[2] = f.get(2,0) + 1
    m = m//2

k = 3
l = int(m**0.5)+1
while m != 1:
    if k > l:
        f[m] = f.get(m,0)+1
        break
    while m%k == 0:
        f[k] = f.get(k,0)+1
        m = m//k
    k += 2
C=[1]
for k in f:
    C_tmp = []
    for c in C:
        for i in range(f[k]):
            C_tmp.append(c*(k**(i+1)))
    C.extend(C_tmp)
ans_r = M
for c in C:
    if c>=N and c<ans_r:
        ans_r = c
print(M//ans_r)
### BUGGY CODE ###

n, k = map(int, input().split())
ans = []
aru = []
nai = []
spe = set()
f = []
m = 0
for i in range(n):
    t, d = map(int, input().split())
    nai.append([t,d])
nai = sorted(nai, key=lambda x: x[1], reverse = True)
for i in range(k):
    anstmp = nai.pop(0)
    if(anstmp[0] not in spe):
        ans.append(anstmp[1])
        spe.add(anstmp[0])
    else:
        aru.append(anstmp[1])

f.append(sum(ans) + sum(aru))
s = len(spe)
for i in range(len(nai)):
    if(len(aru) == 0): break
    if(nai[i][0] not in spe):
        aru.pop(-1)
        ans.append(nai[i][1])
        spe.add(nai[i][0])
        f.append(sum(ans) + sum(aru))
for i in range(len(f)):
    m = max(m, f[i] + (s + i)**2)
print(m)


### FIXED CODE ###

n, k = map(int, input().split())
nai = [list(map(int, input().split())) for _ in range(n)]

nai = sorted(nai, key=lambda x: -x[1])

ans = 0
aru = []
spe = set()
m = 0
for i in range(k):
    anstmp = nai.pop(0)
    if(anstmp[0] not in spe):
        ans+=anstmp[1]
        spe.add(anstmp[0])
    else:
        aru.append(anstmp[1])
sumaru = sum(aru)
m = ans + sumaru + len(spe)**2

for i in range(len(nai)):
    if(len(aru) == 0): break
    if(nai[i][0] not in spe):
        sumaru-=aru.pop()
        ans+=nai[i][1]
        spe.add(nai[i][0])
    m = max(m, ans + sumaru + len(spe)**2)
print(m)
### BUGGY CODE ###

n=int(input())

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

bit=[0 for _ in range(30)]
b=[]

for x in a:
  y=[0 for _ in range(30)]
  for i in range(30):
    if (x>>i)&1:
      y[i]+=1
      bit[i]+=1
  b.append(y)
     
ans1=[]
for g in b:
  ans=0
  for j in range(30):
    if (bit[j]%2)!=(g[j]):
      ans+=2**j
  ans1.append(str(ans))
  
print(' '.join(ans1))

### FIXED CODE ###

n=int(input())

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

bit=[0 for _ in range(30)]
b=[]

for x in a:
  y=[0 for _ in range(30)]
  for i in range(30):
    if (x>>i)&1:
      y[i]+=1
      bit[i]+=1
  b.append(y)
     
ans1=[]
for g in b:
  ans=0
  for j in range(30):
    if (bit[j]%2)!=(g[j]):
      ans+=2**j
  ans1.append(str(ans))
  
print(' '.join(ans1))
### BUGGY CODE ###

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

ans = 1
for i in a:
    ans *= i

if ans > 1000000000000000000:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

ans = 1
if 0 in a:
    print(0)
else:
    for i in a:
        ans *= i
        if ans > 1000000000000000000:
            print(-1)
            exit()

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

n = int(input())
a = list(map(int, input().split()))
ans = 0
double = set(a)
for i in double:
    if not a.count(i) == 1:
        ans -= a.count(i)
a = sorted(a)
# a.sort()
if n == 1:
    print(1)
    exit()
if a[0] == 1:
    if a[1] == 1:
        print(0)
        exit()
    else:
        print(1)
        exit()

check = True
loop = list(range(len(a)))
for i in loop:
    for j in range(0, i):
        if not a[j] == 1:
            if a[j]*2 > a[i]:
                break
        if i == j:
            continue
        if a[i]%a[j] == 0:
            check = False
            break

    if check:
        ans += 1
        # print(i)
    check = True
# print(a)
# print(ans)
# print(double)

# ans -= len(set(double))
# ans -= len(double)
print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
c = Counter(a)
m = max(a) + 1
dp = [False]*m
ans = 0
for ai in a:
    if dp[ai]:
        continue
    if c[ai] == 1:
        ans += 1
    for i in range(ai, m, ai):
        dp[i] = True
print(ans)
### BUGGY CODE ###

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

mod = 10**9+7

a = 0
b = 0
ans = 1

for i in range(N*M,0,-1):
  #print(i,a,b,ans)
  if i in A and i in B:
    ans = ans
    a += 1
    b += 1
  elif i in A: # i not in B
    ans *= b
    ans %= mod
    a+=1
  elif i in B:
    ans *= a
    ans %= mod
    b+=1
  else:
    if a*b - (N*M - i) <= 0:
      print(0)
      break
    else:
      ans *= a*b - (N*M - i)
      ans %= mod
      
else:
  print(ans)
    
    
  


### FIXED CODE ###

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

mod = 10**9+7

a = 0
b = 0
ans = 1

for i in range(N*M,0,-1):
  #print(i,a,b,ans)
  if i in A and i in B:
    ans = ans
    a += 1
    b += 1
  elif i in A: # i not in B
    ans *= b
    ans %= mod
    a+=1
  elif i in B:
    ans *= a
    ans %= mod
    b+=1
  else:
    if a*b - (N*M - i) <= 0:
      print(0)
      break
    else:
      ans *= a*b - (N*M - i)
      ans %= mod
      
else:
  print(ans)
### BUGGY CODE ###

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

li = [0] * N
for i in range(N): li[i] = sum(range(1, p[i]+1)) / p[i]

ans, total = sum(li[:K]), sum(li[:K])
if N != K:
  for i in range(1, N - K + 1):
    total = total - li[i-1] + li[i-1+K]
    ans = max(ans, total)
  print(ans)
else: print(ans)

### FIXED CODE ###

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

li = [0] * N
for i in range(N): li[i] = sum(range(1, p[i]+1)) / p[i]

ans, total = sum(li[:K]), sum(li[:K])
if N != K:
  for i in range(1, N - K + 1):
    total = total - li[i-1] + li[i-1+K]
    ans = max(ans, total)
  print(ans)
else: print(ans)
### BUGGY CODE ###

import sys

H,W=map(int,next(sys.stdin).split())
S=[[*ln] for ln in map(str.strip,sys.stdin)]

xs=[[0]*(W+1) for _ in range(H+1)]
ys=[[0]*(W+1) for _ in range(H+1)]
for i in range(H):
    for j in range(W):
        if S[i][j]!='#':
            if j==0:
                xs[i][j]=1
            else:
                xs[i][j]+=1+xs[i][j-1]
            if i==0:
                ys[i][j]=1
            else:
                ys[i][j]+=1+ys[i-1][j]

ans=0
for i in range(H-1,-1,-1):
    for j in range(W-1,-1,-1):
        if xs[i][j]==0:
            continue
        if xs[i][j+1]:
            x=xs[i][j]=xs[i][j+1]
        else:
            x=xs[i][j]

        if ys[i+1][j]:
            y=ys[i][j]=ys[i+1][j]
        else:
            y=ys[i][j]

        if x+y-1>ans:
            ans=x+y-1

print(ans)


### FIXED CODE ###

import sys

H,W=map(int,next(sys.stdin).split())

xs=[[0]*(W+2) for _ in range(H+2)]
ys=[[0]*(W+2) for _ in range(H+2)]
for i in range(1,H+1):
    row=next(sys.stdin)
    for j in range(1,W+1):
        if row[j-1]!='.': continue
        xs[i][j]=1+xs[i][j-1]
        ys[i][j]=1+ys[i-1][j]

ans=0
for i in range(H,0,-1):
    for j in range(W,0,-1):
        if xs[i][j]==0: continue
        x=xs[i][j]=max(xs[i][j],xs[i][j+1])
        y=ys[i][j]=max(ys[i][j],ys[i+1][j])
        ans=max(ans,x+y-1)

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

N, Q = map(int, input().split())
S = input()
lrs = [map(int, input().split()) for _ in range(Q)]

ps = [S[i] == 'A' and S[i+1] == 'C' for i in range(len(S) - 1)]

for l, r in lrs:
    p = len([b for b in ps[l-1:r] if b])
    if r < len(ps)-1 and not ps[r]:
        p -= 1
    print(p)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
lrs = [list(map(int, input().split())) for _ in range(Q)]

cs = [0] * N
s = 0
for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C':
        s += 1
    cs[i+1] = s 

for l, r in lrs:
    print(cs[r-1] - cs[l-1])
### BUGGY CODE ###

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

N,Q = map(int,input().split())
# STX = [list(map(int,input().split())) for _ in range (N)]
STX = []
vals = set()
for _ in range(N):
    s,t,x = map(int,input().split())
    STX.append((max(0,s-x), max(0,t-x), x))
    vals.add(max(0,s-x))
    vals.add(max(0,t-x))
D = [int(input()) for _ in range(Q)]
for d in D:
    vals.add(d)
vals = list(vals)
vals.sort()
L = len(vals)
mapping = [-1]*(L+10)
STX.sort(key=lambda x:x[2])
for s,t,x in STX:
    s1 = bisect.bisect_left(vals, s)
    t1 = bisect.bisect_left(vals, t)
    for i in range(s1, t1):
        if mapping[i]==-1:
            mapping[i] = x
    
for d in D:
    d1 = bisect.bisect_left(vals, d)
    print(mapping[d1])



### FIXED CODE ###

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

N,Q = map(int,input().split())
# STX = [list(map(int,input().split())) for _ in range (N)]
STX = []
vals = set()
for _ in range(N):
    s,t,x = map(int,input().split())
    STX.append((max(0,s-x), max(0,t-x), x))
    vals.add(max(0,s-x))
    vals.add(max(0,t-x))
D = [int(input()) for _ in range(Q)]
for d in D:
    vals.add(d)
vals = list(vals)
vals.sort()
L = len(vals)
mapping = [-1]*(L+1)
imos = [[] for _ in range(L+1)]
STX.sort(key=lambda x:x[2])
priority = 0 
for s,t,x in STX:
    s1 = bisect.bisect_left(vals, s)
    t1 = bisect.bisect_left(vals, t)
    imos[s1].append([1, priority, x])
    imos[t1].append([0, priority, x])
    priority += 1

import heapq
cur = -1
cur_priority = 10**9
que = [(cur_priority, cur)]
valid_priority = [True]*(N+1)
for i in range(L+1):
    for f,p,x in  imos[i]:
        if f:
            heapq.heappush(que, (p, x))
        else:
            valid_priority[p] = False
    
    while que[0][1]!=-1 and valid_priority[que[0][0]]==False:
        heapq.heappop(que)
    mapping[i] = que[0][1]

for d in D:
    d1 = bisect.bisect_left(vals, d)
    print(mapping[d1])