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

def main():
    import sys
    input = sys.stdin.buffer.readline
    
    r, c, k = map(int, input().split())
    tizu = [[0 for _ in range(c)] for _ in range(r)]
    for _ in range(k):
        rr, cc, v = map(int, input().split())
        tizu[rr - 1][cc - 1] = v
        
    dp = [[[0, 0, 0, 0] for _ in range(c)] for _ in range(r)]
    dp[0][0][1] = tizu[0][0]
    
    for i in range(r):
        for j in range(c):
            if i != 0:
                tmp = max(dp[i - 1][j])
                dp[i][j][0] = tmp
                dp[i][j][1] = tmp + tizu[i][j]
            if j != 0:
                dp[i][j][0] = max(dp[i][j][0], dp[i][j - 1][0])
                dp[i][j][1] = max(dp[i][j][1], dp[i][j - 1][1], dp[i][j - 1][0] + tizu[i][j])
                dp[i][j][2] = max(dp[i][j - 1][2], dp[i][j - 1][1] + tizu[i][j])
                dp[i][j][3] = max(dp[i][j - 1][3], dp[i][j - 1][2] + tizu[i][j])
    print(max(dp[-1][-1]))
    
main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    
    r, c, k = map(int, input().split())
    tizu = [0 for _ in range(r * c)]
    for _ in range(k):
        rr, cc, v = map(int, input().split())
        tizu[(rr - 1) * c + (cc - 1)] = v
        
    dp = [[0, 0, 0, 0] for _ in range(c)]
    dp[0][1] = tizu[0]
    
    for i in range(r):
        for j in range(c):
            v = tizu[i * c + j]
            if v:
                if i != 0:
                    tmp = max(dp[j])
                    dp[j] = [tmp, tmp + v, 0, 0]
                if j != 0:
                    tmp0 = dp[j - 1][0]
                    tmp1 = dp[j - 1][1]
                    tmp2 = dp[j - 1][2]
                    lst = [max(dp[j][0], tmp0), max(dp[j][1], tmp1, tmp0 + v), max(tmp2, tmp1 + v), max(dp[j - 1][3], tmp2 + v)]
                    dp[j] = lst
            else:
                if i != 0:
                    tmp = max(dp[j])
                    dp[j] = [tmp, 0, 0, 0]
                if j != 0:
                    lst = [max(dp[j][0], dp[j-1][0]), dp[j-1][1], dp[j-1][2], dp[j - 1][3]]
                    dp[j] = lst
    print(max(dp[-1]))
    
main()
### BUGGY CODE ###

n = int(input())
x = [0]*n
y = [0]*n
for i in range(n-1, -1, -1):
  a,b = map(int, input().split())
  x[i] = a
  y[i] = b

ans = 0
for i in range(n):
  while (x[i]+ans) % y[i] != 0:
    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
x = [0]*n
y = [0]*n
for i in range(n-1, -1, -1):
  a,b = map(int, input().split())
  x[i] = a
  y[i] = b

ans = 0
for i in range(n):
  if (x[i]+ans) % y[i] != 0:
    ans += y[i]-(x[i]+ans)%y[i]
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
# Union-Find
a=list(range(n))
def find(x):
  while a[x] != x:
    a[x] = a[a[x]]
  return a[x]

for _ in range(m):
  x,y=map(int,input().split())
  x,y=find(x-1),find(y-1)
  if x == y: continue
  a[y]=x

count=[0]*n
for i in range(n):
  count[find(i)] += 1
print(max(count))


### FIXED CODE ###

n,m=map(int,input().split())
# Union-Find
a=list(range(n))
def find(x):
  g = x
  while g != a[g]: g = a[g]
  a[x] = g
  return g

for _ in range(m):
  x,y=map(int,input().split())
  x,y=find(x-1),find(y-1)
  if x == y: continue
  a[y]=x

count=[0]*n
for i in range(n):
  count[find(i)] += 1
print(max(count))
### BUGGY CODE ###

N = int(input())
V = list(map(int,input().split()))
C = list(map(int,input().split()))

xy = []

for i in range(2 ** N):
  value = 0
  cost = 0
  for j in range(N):
    if ((i >> j) & 1):
      value += V[j]
      cost += C[j]
  
  xy.append(value - cost)
  
print(max(xy))

### FIXED CODE ###

N = int(input())
V = list(map(int,input().split()))
C = list(map(int,input().split()))

ans = 0

for i in range(N):
  if V[i] >= C[i]:
    ans += V[i] - C[i]
    
print(ans)
### BUGGY CODE ###

from sys import stdin
input = stdin.readline
from math import gcd
from collections import Counter,defaultdict
n = int(input())
a = list(map(int,input().split()))
s = Counter(a)
a = sorted(s)
if s[1]==2:
    ans = 0
elif s[1]==1:
    ans = 1
else:
    ans = 0
    for i in range(len(a)):
        if s[a[i]]>1:
            continue
        for j in range(i):
            if a[i]%a[j]==0:
                break
        else:
            ans+=1
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))
c = Counter(a)
s = set()
ans = 0
for i in sorted(set(a)):
    j=i*2
    while j<=1000000:
        s.add(j)
        j+=i
    if i not in s and c[i]==1:
        ans+=1
            
print(ans)
### BUGGY CODE ###

from itertools import permutations, accumulate
mod = 2019

a = list(map(int,input()))
n = len(a) #入力の桁数

for i in range(n):
    a[i] *= pow(10,n-i-1) #pow(a,b)==a^b べき乗
    
s = [0]+list(accumulate(a)) #accumulate([1,2,3,4,5]) --> 1 3 6 10 15
d = [0]*mod
ans = 0
for i in s:
    j = i%mod
    ans += d[j]
    d[j] += 1
print(ans)

### FIXED CODE ###

from itertools import permutations, accumulate
mod = 2019

a = list(map(int,input()))
n = len(a) #入力の桁数

for i in range(n):
    a[i] *= pow(10,n-i-1,mod) #pow(a,b)==a^b べき乗
    
s = [0]+list(accumulate(a)) #accumulate([1,2,3,4,5]) --> 1 3 6 10 15
d = [0]*mod
ans = 0
for i in s:
    j = i%mod
    ans += d[j]
    d[j] += 1
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())

r = False
for i in range(Q):
    x = input().split()
    
    if x[0] == "1":
        r = not r
        
    else:
        if x[1] == "1":
            if r == False :
                S = x[2] + S
            else:
                S = S + x[2]
        else:
            if r == True :
                S = x[2] + S
            else:
                S = S + x[2]
        
if r:
    print(S[::-1])
else:
    print(S)

### FIXED CODE ###

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

day = deque(S)

r = False
for i in range(Q):
    x = input().split()
    
    if x[0] == "1":
        r = not r
        
    else:
        if x[1] == "1":
            if r == False :
                day.appendleft(x[2])
            else:
                day.append(x[2])
        else:
            if r == True :
                day.appendleft(x[2])
            else:
                day.append(x[2])
                
day = list(day)
        
if r:
    print("".join(day[::-1]))
else:
    print("".join(day))
### BUGGY CODE ###

def myAnswer(N:int,A:list) -> None:
   MAX = max(A)
   tmp = A[:]
   for i in range(N):
      if(A[i] == MAX):
         tmp.remove(A[i])
         print(max(tmp))
         tmp = A[:]
      else:
         print(MAX)

def modelAnswer():
   tmp=1
def main():
   N = int(input())
   A =[]
   for _ in range(N):
      A.append(int(input()))
   myAnswer(N,A)

if __name__ == '__main__':
   main()

### FIXED CODE ###

def myAnswer(N:int,A:list) -> None:
   MAX1 = max(A)
   tmp = A[:]
   tmp.remove(MAX1)
   MAX2 = max(tmp)
   for i in range(N):
      if(A[i] == MAX1):
         print(MAX2)
      else:
         print(MAX1)

def modelAnswer():
   tmp=1
def main():
   N = int(input())
   A =[]
   for _ in range(N):
      A.append(int(input()))
   myAnswer(N,A)

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

import numpy as np
n = int(input())
abc = [list(map(int, input().split())) for _ in range(n)]

ex = np.array([[1,2], [0,2], [0,1]])
dp = np.array([abc[0]] + [[0]*3 for _ in range(n-1)])

for i in range(n-1):
    for j in range(3):
        dp[i+1][j] = abc[i+1][j] + np.max(np.take(dp[i], ex[j]))

print(max(dp[-1]))

### FIXED CODE ###

n = int(input())
abc = [list(map(int, input().split())) for _ in range(n)]
dp = [[0,0,0] for _ in range(n)]

dp[0] = abc[0]
ls = [[1,2], [0,2], [0,1]]

if n == 1:
    ans = min(dp[0])
else:
    for i in range(1,n):
        for j in range(3):
            dp[i][j] = max([ dp[i-1][k] for k in ls[j] ]) + abc[i][j]

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

N = int(input())
s = [''] * N
for i in range(N):
    tmp = sorted(input())
    s[i] = ''.join(tmp)
s.sort()
cnt = 0
index = 1
for i in range(0,N - 1,index):
    index = 1
    for j in range(i + 1, N):
        if s[i] == s[j]:
            cnt += 1
            index += 1
        else:
            break

print(cnt)


### FIXED CODE ###

N = int(input())
s = [''] * N
for _ in range(N):
    tmp = sorted(input())
    s[_] = ''.join(tmp)
tmp = sorted(s)
cnt = 1
index = 0
ansFlag = True
ans1 = 0
while ansFlag:
    cnt = 1
    for j in range(index + 1, N):
        if tmp[index] == tmp[j]:
            cnt += 1
            index += 1
        else:
            index += 1
            break

    tmp2 = 0
    for i in range(cnt, 0, -1):
        tmp1 = i - 1
        tmp2 += tmp1
        ans = tmp2
    ans1 += ans
    if index == (N - 1):
        ansFlag = False

print(ans1)
### BUGGY CODE ###

def main():
  n=int(input())
  A=[int(input()) for i in range(n)]
  L = [1]
  crt=1
  for i in range(n):
    crt = A[crt-1]
    if crt in L:
      print(-1)
      break
    if crt == 2:
      print(len(L))
      break
    L.append(crt)
main()

### FIXED CODE ###

def main():
  n=int(input())
  A=[int(input()) for i in range(n)]
  crt=1
  cnt=0
  for i in range(n):
    cnt += 1
    crt = A[crt-1]
    if crt == 2:
      print(cnt)
      break
  else:
    print(-1)
main()
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from functools import lru_cache

N, K = map(int,read().split())

def F(N, K):
    """N以下で0でないものがちょうどK個。0を含める"""
    assert N >= 0
    if N < 10:
        if K == 0:
            return 1
        if K == 1:
            return N
        return 0
    q,r = divmod(N,10)
    ret = 0
    if K >= 1:
        # 1の位が nonzero
        ret += F(q, K-1) * r
        ret += F(q-1, K-1) * (9-r)
    # 1の位が zero
    ret += F(q, K)
    return ret

# F(100, 1), F(25, 2), F(314159, 2)

print(F(N, K))


### FIXED CODE ###

import sys
import math
sys.setrecursionlimit(10 ** 7)

# 桁DP
# 再帰

N = input()
K = int(input())
lenN = len(N)


# 組み合わせの数
def comb(n, k):
    return math.factorial(n) // (math.factorial(k) * math.factorial(n-k))


# i桁目から
# 残りk個 Non-Zero
# Nよりもsmallerか？
# というときの組み合わせの数
def CntAlmostZero(i, k, smaller):
    # N桁まで取り出した時
    if i == lenN:
        if k == 0:
            return 1
        else:
            return 0

    if k == 0:
        return 1

    # Nよりも小さい時
    if smaller:
        # 残りの桁でK個使える時
        if (lenN - i) >= k:
            return comb(lenN - i, k) * (9 ** k)
        # 無理なら 0
        else:
            return 0
    # 前がNと同じ桁の時(初期は0なので必ずこっち)
    else:
        # 見てる桁が0の時
        if N[i] == '0':
            return CntAlmostZero(i + 1, k, False)
        # 見てる桁が0以外の時
        else:
            # 0だったら
            zero = CntAlmostZero(i+1, k, True)
            # 同じだったら
            same = CntAlmostZero(i+1, k-1, False)
            # その間だったら
            aida = CntAlmostZero(i+1, k-1, True) * (int(N[i]) - 1)

            return zero + same + aida

    return 1


ans = CntAlmostZero(0, K, False)
print(ans)
### BUGGY CODE ###

ny = input().split()
n = int(ny[0])
yen = int(ny[1])

ichiman = -1
gosen = -1
sen = -1
flg = False

for x in range(n + 1):
	if flg : break
	for y in range(n-x+1):
		if flg : break
		for z in range(n-x-y+1):
			if x + y + z == n and 10000*x + 5000*y + 1000*z == yen:
				ichiman = x
				gosen = y
				sen = z
				flg = True

print(ichiman,gosen,sen)

### FIXED CODE ###

ny = input().split()
n = int(ny[0])
yen = int(ny[1])

ichiman = -1
gosen = -1
sen = -1
flg = False

for x in range(n + 1):
	if flg : break
	for y in range(n-x+1):
		if 10000*x + 5000*y + 1000*(n-x-y) == yen:
			flg = True
			ichiman = x
			gosen = y
			sen = n-x-y
			break

print(ichiman,gosen,sen)
### BUGGY CODE ###

s_inv = str(input())[::-1]
dp = [1]+[0]*2018
MOD = 0
k = 1
ans = 0
num = 0

for i in range(len(s_inv)):
  num+=int(s_inv[i])*k
  MOD = num % 2019
  dp[MOD] += 1
  k = k*10

for i in dp:
  ans += i*(i-1)/2

print(int(ans))


### FIXED CODE ###

s_inv = str(input())[::-1]
dp = [1]+[0]*2018
MOD = 0
ans = 0
num = 0
k = 1

for i in range(len(s_inv)):
  num+=int(s_inv[i])*k
  MOD = num % 2019
  dp[MOD] += 1
  k = k*10
  k %= 2019
for i in dp:
  ans += i*(i-1)/2

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

n=int(input())

dic={}
for i in range(n):
    s=input()
    if s not in dic:
        dic[s]=1
    else:
        dic[s]+=1
dic2=sorted(dic.items(), key=lambda x:x[1],reverse=True)

keys=sorted([k for k,v in dic.items() if v==max(dic.values()) ])
for i in keys:
    print(i)

### FIXED CODE ###

n=int(input())

dic={}
for i in range(n):
    s=input()
    if s not in dic:
        dic[s]=1
    else:
        dic[s]+=1
dic2=sorted(dic.items(), key=lambda x:x[1],reverse=True)
ma=dic2[0][1]

keys=sorted([k for k,v in dic.items() if v==ma])
for i in keys:
    print(i)
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[10**9]*n
dp[0]=0
for i in range(n-1):
    for j in range(i+1,min(i+k+1,n)):
        dp[j]=min(dp[j],dp[i]+abs(h[j]-h[i]))
print(dp[-1])

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[10**9]*n
dp[0]=0
for i in range(n-1):
    for j in range(i+1,min(i+k+1,n)):
        dp[j]=min(dp[j],dp[i]+abs(h[j]-h[i]))
print(dp[-1])
### BUGGY CODE ###

import collections


def main():
    n = int(input())
    word_list = []

    for _ in range(n):
        word_list.append(input())

    c = collections.Counter(word_list)
    most_freq_word = [i for i in c if c[i] == max(c.values())]

    most_freq_word.sort()
    s = '\n'.join(most_freq_word)
    print(s)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import collections


def main():
    n = int(input())
    word_list = []

    for _ in range(n):
        word_list.append(input())

    c = collections.Counter(word_list)
    max_freq = max(c.values())
    most_freq_word = sorted([i for i in c if c[i] == max_freq])
    print('\n'.join(most_freq_word))


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

from operator import mul
from functools import reduce

N = int(input())
x = [int(i) for i in input().split()]
y = reduce(mul, x)

if y > 10**18:
    print(-1)
else:
    print(y)

### FIXED CODE ###

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

now=1
if 0 in A:
    print(0)
    exit()
for a in A:
    now = now * a
    if now>10**18:
        print(-1)
        exit()
print(now)
### BUGGY CODE ###


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


ans = 1

for i in range(2,int(p**(1./n))+1):
	while(p%(i**n)==0 and p>=(i**n)):
		ans*=i
		p//=i**n
print(ans)



### FIXED CODE ###

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


ans = 1
if(n==1):print(p)
else:

	for i in range(2,int(p**(1./n))+1):
		while(p%(i**n)==0):
			ans*=i
			p//=i**n
	print(ans)
### BUGGY CODE ###

MOD = 10**9 + 7


def gcd(a, b):
    while b != 0:
        a, b = b, a - (a // b) * b

    return a


def lcm(iterable):
    a = iterable[0]

    for b in iterable:
        a = a * b // gcd(a, b)

    return a


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

    lcm_an = lcm(an)

    ans = 0
    for a in an:
        ans += lcm_an // a
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import functools

MOD = 10**9 + 7


def lcm(a, b) -> int:
    c, d = a, b
    while d != 0:
        c, d = d, c % d
    return a // c * b


def inv_mod(x):
    return pow(x, MOD - 2)


def pow(x: int, n: int) -> int:
    res = 1
    while n > 0:
        if n & 1 == 1:
            res = res * x % MOD
        x = x * x % MOD
        n >>= 1

    return res


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

    lcm_an = functools.reduce(lcm, an)
    lcm_an %= MOD

    ans = 0
    for a in an:
        ans = (ans + lcm_an * inv_mod(a)) % MOD

    print(ans)


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

ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else y
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

#maincode-------------------------------------------------
s = input()
q = ini()
mae = ''
bac = s
for i in range(q):
    a = input()
    if a[0] == '1':
        temp = mae
        mae = bac
        bac = temp
    else:
        if a[2] == '1':
            mae = mae + a[4]
        else:
            bac = bac + a[4]
mae = mae[::-1]
print(mae + bac)

### FIXED CODE ###

ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else y
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

#maincode-------------------------------------------------
s = input()
q = ini()
mae = ''
bac = s
for i in range(q):
    a = input()
    if a[0] == '1':
        temp = mae
        mae = bac
        bac = temp
    else:
        if a[2] == '1':
            mae = mae + a[4]
        else:
            bac = bac + a[4]
mae = mae[::-1]
print(mae + bac)
### BUGGY CODE ###

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

List=[]

while len(List) < N:
    for i in range(A):
        List.append("b")
    for i in range(B):
        List.append("r")

for i in range (len(List)-N):
    del List[N]

print(List.count("b"))


### FIXED CODE ###

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

brset = A + B
inside = N // (A+B)
count = inside*A

if inside*brset + A <= N:
    count += A
else:
    count += N - (inside*brset)

print(count)
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)

ans = 0
for i in range(0, N-2):
    a = L[i]
    for j in range(i+1, N-1):
        b = L[j]
        for k in range(j+1, N):
            c = L[k]
            if c > a - b:
                ans += 1
            else:
                break
print(ans)

### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int, input().split()))
l.sort()

'''
リストをソートし、a, b <= cとなるようにa, bを取り出せば、
a < b + c, b < c + a という条件は満たすので、
a, bを取り出したとき、c < a + b を満たすcを二分探索で探す
'''

ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        ans += bisect.bisect_left(l, l[i]+l[j]) - j - 1
print(ans)
### BUGGY CODE ###

x=int(input())
for i in range(int(x**0.5)+1):
    for j in range(-(int(x**0.5)+1),int(x**0.5)+1):
        if i**5-j**5==x:
            print(str(i)+" "+str(j))
            break
    else:
        continue
    break

### FIXED CODE ###

x=int(input())
for n in range(1,int(x**0.5)+1):
    if x%n==0:
        for a in range(int(x**0.5)+1):
            if 5*a**4-10*a**3*n+10*a**2*n**2-5*a*n**3+n**4==x//n:
                print(str(a)+" "+str(a-n))
                break
            a=-a
            if 5*a**4-10*a**3*n+10*a**2*n**2-5*a*n**3+n**4==x//n:
                print(str(a)+" "+str(a-n))
                break
        else:
            continue
        break
### BUGGY CODE ###

x,y,a,b,c = map(int,input().split())
p = sorted(list(map(int,input().split())),reverse=True)
q = sorted(list(map(int,input().split())),reverse=True)
r = sorted(list(map(int,input().split())),reverse=True)

z = sorted(p+q+r,reverse=True)
ans = 0
c = 0
for i in z:
    if x+y-c==0:
        break
    elif p and i == p[0] and x>0:
        ans+=i
        p.pop(0)
        x -= 1
    elif q and i == q[0] and y>0:
        ans += i
        q.pop(0)
        y -= 1
    elif i == r[0] and x+y-c>0:
        ans += i
        r.pop(0)
        c += 1
print(ans)

### FIXED CODE ###

x,y,a,b,c = map(int,input().split())
p = sorted(list(map(int,input().split())))
q = sorted(list(map(int,input().split())))
r = sorted(list(map(int,input().split())))

z = sorted(p+q+r,reverse=True)
ans = 0
c = 0
for i in z:
    if x+y-c==0:
        break
    elif p and i == p[-1] and x>0:
        ans+=i
        p.pop()
        x -= 1
    elif q and i == q[-1] and y>0:
        ans += i
        q.pop()
        y -= 1
    elif i == r[-1] and x+y-c>0:
        ans += i
        r.pop()
        c += 1
print(ans)
### BUGGY CODE ###

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

l = [0]*n
m = [0]*n
r = [0]*n
for i in range(n):
  l[i] = as_[i]
  m[i] = as_[n+i]
  r[i] = (-1)*as_[2*n+i]

import heapq
heapq.heapify(l)
heapq.heapify(r)

l_maxs = [0]*(n+1)
r_mins = [0]*(n+1)

for i in range(n+1):
  if i != 0:
    j = i-1
    heapq.heappush(l, m[j])
    heapq.heappop(l)
    l_max = sum(l)
    
    k = -i
    heapq.heappush(r, m[k]*(-1))
    heapq.heappop(r)
    r_min = sum(r)
    
  else:
    l_max = sum(l)
    r_min = sum(r)
    
  l_maxs[i] = l_max
  r_mins[i] = r_min

#print(l_maxs)
#print(r_mins)

print(max([l_maxs[i] + r_mins[n-i] for i in range(n+1)]))

### FIXED CODE ###

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

l = [0]*n
m = [0]*n
r = [0]*n
for i in range(n):
  l[i] = as_[i]
  m[i] = as_[n+i]
  r[i] = (-1)*as_[2*n+i]

import heapq
heapq.heapify(l)
heapq.heapify(r)

l_maxs = [0]*(n+1)
r_mins = [0]*(n+1)

sl = sum(l)
sr = sum(r)

for i in range(n+1):
  if i != 0:
    j = i-1
    heapq.heappush(l, m[j])
    a = heapq.heappop(l)
    sl += m[j] -a
    
    k = -i
    heapq.heappush(r, m[k]*(-1))
    b = heapq.heappop(r)
    sr += m[k]*(-1) - b
    
  l_maxs[i] = sl
  r_mins[i] = sr

#print(l_maxs)
#print(r_mins)

print(max([l_maxs[i] + r_mins[n-i] for i in range(n+1)]))
### BUGGY CODE ###

N=int(input())
S=input()
a=S.count('R')
b=S.count('G')
c=S.count('B')
ans=a*b*c
for i in range(N):
  for j in range(i+1,N):
    if S[i]!=S[j]:
      if (2*j-i)<=N-1:
        if S[i]!=S[2*j-i] and S[j]!=S[2*j-i]:
          ans-=1
print(ans)

### FIXED CODE ###

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

def main():
    import sys
    input = sys.stdin.readline
    from bisect import bisect_left

    N,Q = map(int,input().split())
    info = [list(map(int,input().split())) for _ in range(N)]
    info.sort(key=lambda x:x[2])
    D = sorted([int(input()) for _ in range(Q)])
    nD = sorted([(d,i) for i, d in enumerate(D)])

    S = set(range(Q))
    ans = [-1]*Q

    for s,t,x in info:
        left = bisect_left(D,s-x)
        right = bisect_left(D,t-x)
        for d,i in nD[left:right]:
            if i in S:
                ans[i] = x
                S.remove(i)

    for a in ans:
        print(a)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from bisect import bisect_left
inf = float('inf')

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

res = 1
while res < Q:
    res <<= 1
N0 = res
data = [inf for _ in range(2*N0-1)]

def update(l, r, x):
    L = l + N0
    R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R] = min(data[R], x)
        if L & 1:
            data[L] = min(data[L], x)
            L += 1
        L >>= 1; R >>= 1

def value(k):
    k += N0
    res = data[k]
    while k != 0:
        k >>= 1
        res = min(res, data[k])
    return res


for S, T, X in STX:
    l = bisect_left(D, S-X)
    r = bisect_left(D, T-X)
    update(l, r, X)

for k in range(Q):
    ans = value(k)
    if ans == inf:
        ans = -1
    print(ans)