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

import fractions
from functools import reduce
 
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
 
n = int(input())
a = list(map(int,input().split()))
ans = 0
for i in range(n):
    li = a[:i] + a[i + 1:]
    tmp = gcd_list(li)
    if tmp > ans:
        ans = tmp
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Jun 29 20:51:40 2019

@author: makigon
"""

import fractions
from functools import reduce
 
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
 
N = int(input())
a = list(map(int,input().split()))
ans = 0

t_left = [0 for i in range(N)]
t_right = [0 for i in range(N)]

t_left[0] = a[0]
t_left[1] = fractions.gcd(a[0],a[1])

for i in range(2,N):
    t_left[i] = fractions.gcd(t_left[i-1],a[i])

t_right[N-1] = a[N-1]
t_right[N-2] = fractions.gcd(a[N-1],a[N-2])

for j in range(N-3,0,-1):
    t_right[j] = fractions.gcd(t_right[j+1],a[j])
    

for i in range(0,N-2):
    tmp = fractions.gcd(t_left[i],t_right[i+2])
    if tmp > ans:
        ans = tmp
    
print(max(ans,t_right[1],t_left[N-2]))
### BUGGY CODE ###

N,M = map(int,input().split())
modA = [a%M for a in map(int,input().split())]
ans = 0
for l in range(N):
  sumA = 0
  for r in range(l,N):
    sumA += modA[r]
    sumA = sumA%M
    if sumA%M == 0: ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter
N,M = map(int,input().split())
A = list(map(int,input().split()))

sumA = [0] + [0]*N
for i in range(N):
  sumA[i] = (sumA[i-1]+A[i])%M

cnt = Counter(sumA).values()
ans = sum(i*(i-1)//2 for i in cnt)

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

N = int(input())
S = input()

ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            tmp = 0
            for l, value in enumerate(S):
                if tmp == 0:
                    if value == str(i):
                        tmp = 1
                elif tmp == 1:
                    if value == str(j):
                        tmp = 2
                elif tmp == 2:
                    if value == str(k):
                        ans += 1
                        break
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
# st = set()
# for i in range(n-2):
#     for j in range(i+1, n-1):
#         for k in range(j+1, n):
#             pin = s[i] + s[j] + s[k]
#             st.add(pin)
# print(st)
count = 0
# for i in range(1000):
#     if len(str(i)) == 1:
#         v = "00" + str(i)
#     elif len(str(i)) == 2:
#         v = "0" + str(i)
#     else:
#         v = str(i)
#     k = 0
#     for j in range(len(v)):
#         while k < len(s):
#             if s[k] == v[j]:
#                 k += 1
#                 break
#             k += 1
#         else:
#             break
#     else:
#         count += 1
for i in range(1000):
    v = [i // 100, (i // 10) % 10, i % 10]
    first = s[:-2].find(str(v[0]))
    if first == -1:
        continue
    second = s[first + 1:-1].find(str(v[1]))
    if second == -1:
        continue
    third = s[first + 1 + second + 1:].find(str(v[2]))
    if third == -1:
        continue
    # print(v, first, second, third, first + second +1)
    count += 1
print(count)
### BUGGY CODE ###

n=int(input())
s=input()
ans=0
l=[]
for i in range(n):
  for j in range(i+1,n):
    if not s[i]+s[j] in l:
      l.append(s[i]+s[j])
      ans+=len(set(s[j+1:]))
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
ans=0
for i in range(1000):
  v=str(i)
  v=v.zfill(3)
  ss=s
  if not v[0] in ss:
    continue  
  ss=ss[ss.index(v[0])+1:]
  if not v[1] in ss:
    continue
  ss=ss[ss.index(v[1])+1:]
  if not v[2] in ss:
    continue
  ans+=1
print(ans)
### BUGGY CODE ###

import fractions
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

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

ans = []
for i in range(N):
    ans.append(gcd_list(A[:i]+A[i+1:]))
print(max(ans))

### FIXED CODE ###

from fractions import gcd
#input
N = int(input())
A = [int(i) for i in input().split()]
#cluc left and right gcd 
left = [0]*N
right = [0]*N
count = 0
left[0] = A[0]
right[-1] = A[-1]
Ans = []

for i in A[1:]:
    left[count+1] = gcd(left[count],i)
    count += 1

for i in reversed(A[:-1]):
    right[count-1] = gcd(right[count],i)
    count -= 1
# make ans
Ans.append(right[1])
Ans.append(left[-2])
for i in range(N-2):
    Ans.append(gcd(left[i],right[i+2]))
print(max(Ans))
### BUGGY CODE ###

n = int(input())
s = input()
cnt =0
for i in range(n):
  for j in range(i):
    for k in range(j):
      if s[i]!=s[j] and s[k]!=s[j] and s[i]!=s[k] and i-j!=j-k:
        cnt += 1
print(cnt)

### FIXED CODE ###

N=int(input())
S=input()
r=S.count('R')
b=S.count('B')
g=S.count('G')
ans=r*b*g
for i in range(N):
    for s in range(N):
        j=i+s
        k=j+s
        if k>=N:
            break
        if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
            ans-=1
print(ans)
### BUGGY CODE ###

def resolve():
	S=input()
	chk=1
	cnt=0
	while chk==1:
		chk=0
		if len(S)==0:
			break
		if '10' in S:
			S=S.replace('10','',1)
			chk=1
			cnt+=1
		if '01' in S:
			S=S.replace('01','',1)
			chk=1
			cnt+=1
	print(cnt*2)
resolve()

### FIXED CODE ###

def resolve():
	S=input()
	print(min(S.count('1'),S.count('0'))*2)
resolve()
### BUGGY CODE ###

def search(s_y, s_x):
    count = 1
    for vec_x, vec_y in vecs:
        n_y = s_y + vec_y
        n_x = s_x + vec_x

        while judge(n_y, n_x):
            #is_visited[n_y][n_x] = True
            count += 1
            n_y += vec_y
            n_x += vec_x
    return count

def judge(y, x):
    return 0 <= y <= H -1 and 0 <= x <= W - 1 and not is_visited[y][x] and S_list[y][x] != '#'

H, W = map(int, input().split())
S_list = [None] * H
is_visited = [[False] * W for _ in range(H)]

for h in range(H):
    S_list[h] = list(input())

vecs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

max_num = 0
for h in range(H):
    for w in range(W):
        if S_list[h][w] != '#':
            max_num = max(max_num, search(h, w))

print(max_num)


### FIXED CODE ###

#ref. https://atcoder.jp/contests/abc129/submissions/5906191
import numpy as np
import sys

def main():
    sin = sys.stdin.buffer
    H, W = map(int, sin.readline().split())
    grid = np.frombuffer(sin.read(H * (W + 1)), dtype="B") == ord(".")
    grid = grid.reshape((H, W + 1))[:, :-1]

    L = np.empty((H, W), dtype="i4")
    R = np.empty((H, W), dtype="i4")
    T = np.empty((H, W), dtype="i4")
    B = np.empty((H, W), dtype="i4")

    T[0] = grid[0]
    for i in range(1, H):
        T[i] = (T[i - 1] + 1) * grid[i]

    B[-1] = grid[-1]
    for i in range(H - 2, -1, -1):
        B[i] = (B[i + 1] + 1) * grid[i]

    L[:, 0] = grid[:, 0]
    for i in range(1, W):
        L[:, i] = (L[:, i - 1] + 1) * grid[:, i]

    R[:, -1] = grid[:, -1]
    for i in range(W - 2, -1, -1):
        R[:, i] = (R[:, i + 1] + 1) * grid[:, i]

    ans = (T + B + L + R - 3).max()
    print(ans)

main()
### BUGGY CODE ###

n,k=map(int, input().split())
an=[int(i) for i in input().split()]

def comb(n, r,mod):
    r=min(r,n-r)
    p, q = 1, 1
    for i in range(r):
        p = p * (n-i) % mod
        q = q * (i+1) % mod
    return p * pow(q, mod-2, mod) % mod

an=sorted(an)
r_an=list(reversed(an))

mod=10**9+7
max1=0
min1=0
for i in range(1,n-k+2):
    max1+=an[-i]*comb(n-i,k-1,mod)%mod
    min1+=r_an[-i]*comb(n-i,k-1,mod)%mod
print((max1-min1)%mod)

### FIXED CODE ###

n,k=map(int, input().split())
an=[int(i) for i in input().split()]

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r=min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 5
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2,N+1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

an=sorted(an)
r_an=list(reversed(an))

max1=0
min1=0
for i in range(1,n-k+2):
    c=cmb(n-i,k-1,p)
    max1=max1 + an[-i]*c%p
    min1=min1 + r_an[-i]*c%p
print((max1-min1)%p)
### BUGGY CODE ###

H, W, K = map(int, input().split())
cake = [input() for _ in range(H)]
memo = [[0] * W for _ in range(H)]
cake_count_row = [0] * H

for y in range(H):
    count = 0
    for x in range(W):
        if cake[y][x] == "#":
            count += 1
    cake_count_row[y] = count

count = 1
for y in range(H):
    first = True
    if cake_count_row[y] == 0:
        continue 
    for x in range(W):
        if cake[y][x] == "#":
            if first:
                first = False
            else:
                count += 1
        memo[y][x] = count
    if first == False:
        count += 1

for _ in range(H - 1):
    for y in range(H - 1):
        if cake_count_row[y] == 0:
            for x in range(W):
                memo[y][x] = memo[y + 1][x]

for _ in range(H - 1):
    for y in range(H - 1, 0, -1):
        if cake_count_row[y] == 0:
            for x in range(W):
                memo[y][x] = memo[y - 1][x]

for i in range(H):
    print(" ".join(list(map(str, memo[i]))))

### FIXED CODE ###

H, W, K = map(int, input().split())
cake = [input() for _ in range(H)]
memo = [[0] * W for _ in range(H)]
cake_count_row = [0] * H

for y in range(H):
    count = 0
    for x in range(W):
        if cake[y][x] == "#":
            count += 1
    cake_count_row[y] = count

count = 1
for y in range(H):
    first = True
    if cake_count_row[y] == 0:
        continue 
    for x in range(W):
        if cake[y][x] == "#":
            if first:
                first = False
            else:
                count += 1
        memo[y][x] = count
    if first == False:
        count += 1

copy_y_save = -1
for y in range(1, H):
    if cake_count_row[y] == 0:
        for x in range(W):
            memo[y][x] = memo[y - 1][x]

for y in range(H - 2, -1, -1):
    if cake_count_row[y] == 0:
        for x in range(W):
            memo[y][x] = memo[y + 1][x]

for i in range(H):
    print(" ".join(list(map(str, memo[i]))))
### BUGGY CODE ###

n,m=map(int,input().split())
ans=0
for i in range(n):
    if m>=2:
        m-=2
        ans+=1
    else:
        break

while m>=4:
    ans+=1
    m-=4
print(ans)


### FIXED CODE ###

n,m=map(int,input().split())
ans=0
if 2*n<=m:
    ans+=n
    m-=2*n
    ans+=(m//4)
else:
    ans+=m//2
print(ans)
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
c=[0 for _ in range(n)]
for i in range(n-1):
  if s[i:i+2]=='AC':
    c[i]=1
for i in range(q):
  ans=0
  l,r=map(int,input().split())
  ans=sum(c[l-1:r-1])
 # if s[]
  print(ans)

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
c=[0 for _ in range(n)]
p=''
d=0
for i in range(n):
  x=s[i]
  if p=='A' and x=='C':
    d+=1
  p=x
  c[i]=d
for i in range(q):
  ans=0
  l,r=map(int,input().split())
  ans=c[r-1]-c[l-1]

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

a, b, n = map(int, input().split())
ans = 0
for x in range(1,n+1):
    f = (x / b - x // b) * a // 1
    

    if ans <= f:
        ans = f
print(int(ans))

### FIXED CODE ###

a, b, n = map(int, input().split())
M = min(b-1,n)
print(int((M/b-M//b) * a))
### BUGGY CODE ###

x,y,z,k=list(map(int,input().split()))
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))

#a.sort(reverse=True)
#b.sort(reverse=True)
#c.sort(reverse=True)

li=[]
for i in a:
  for j in b:
    li.append(i+j)
li.sort(reverse=True)

ansli=[]
for i in c:
  for j in range(min(k,len(li))):
    ansli.append(i+li[j])
ansli.sort(reverse=True)

for i in range(k):
  print(ansli[i])

### FIXED CODE ###

from heapq import *

x,y,z,k=list(map(int,input().split()))
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

q=[]
li=[]
heappush(q,((a[0]+b[0]+c[0]) * (-1),0,0,0))

for i in range(k):
  node=heappop(q)
  
  print(node[0]*-1)
  if node[1]+1 != x:
    node_a = ((a[node[1]+1]+b[node[2]]+c[node[3]])*(-1), node[1]+1, node[2], node[3])
    if node_a not in q:
      heappush(q,node_a)
  
  if node[2]+1 != y:
    node_b = ((a[node[1]]+b[node[2]+1]+c[node[3]])*(-1), node[1], node[2]+1, node[3])
    if node_b not in q:
      heappush(q,node_b)
  
  if node[3]+1 != z:
    node_c = ((a[node[1]]+b[node[2]]+c[node[3]+1])*(-1), node[1], node[2], node[3]+1)
    if node_c not in q:
      heappush(q,node_c)
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))
flag = True
if n%2 == 1:
    for i in range(0,n,2):
        if i == 0:
            if li.count(0) != 1:
                flag = False
        else:
            if li.count(i) != 2:
                flag = False
else:
    for i in range(1,n,2):
        if li.count(i) != 2:
            flag = False
if not flag:
    print(0)
    exit()

if n%2 == 1:
    print(2**((n-1)//2))
else:
    print(2**(n//2))

### FIXED CODE ###

import collections
n = int(input())
li = list(map(int,input().split()))

c = collections.Counter(li)
#print(c)
# Counter({'a': 4, 'c': 2, 'b': 1})
#print(c.items())
# dict_items([('a', 4), ('b', 1), ('c', 2)])
count_list = list(c.items())
count_list.sort()
keys = set(c.keys())
#print(keys,{i for i in range(n) if i%2 == 1})
#print(count_list)
flag = True
if n%2 == 1:
    if keys != {i for i in range(n) if i%2 == 0}:
        print(0)
        exit()
    for i,c in enumerate(count_list):
        #print(c[0],c[1])
        if c[0] == 0:
            if c[1]!=1:
                flag = False
        else:
            if c[1]!=2:
                flag = False
else:
    if keys != {i for i in range(n) if i%2 == 1}:
        print(0)
        exit()
    for i in count_list:
        if i[1] != 2:
            flag = False
if not flag:
    print(0)
    exit()

ans_tmp = 0
if n%2 == 1:
    ans_tmp = 2**((n-1)//2)
else:
    ans_tmp = 2**(n//2)
print(ans_tmp%(10**9+7))
### BUGGY CODE ###

L, R = map(int, input().split())
li = []
if R-L+1 >= 2019:
  print(0)
else:
  for i in range(L, R+1):
    for j in range(L, R+1):
      if i != j:
        a = i*j
        if a < 2019:
          li.append(a)
        else:
          while a > 2019:
            a %= 2019
            li.append(a)
      else:
        li.append(2018)
  print(min(li))

### FIXED CODE ###

L, R = map(int, input().split())
li = []
li_a =[]
if R-L+1 >= 2019:
  print(0)
else:
  for i in range(L, R+1):
    li.append(i%2019)
  for x in li:
    for y in li:
      if x != y:
        li_a.append((x*y)%2019)
  print(min(li_a))
### BUGGY CODE ###

N, A, B = map(int, input().split())
a = 0
b = 0
while True:
  if a + b + A >= N:
    ans = N - b 
    break
  else:
    a += A
    if a + b + B >= N:
      ans = a
      break
    else:
      b += B
print(ans)

### FIXED CODE ###

N, A, B = map(int, input().split())
ans  = (N//(A+B))*A
if N%(A+B)<=A:
  ans += N%(A+B)
elif N%(A+B) !=0:
  ans += A
print(ans)
### BUGGY CODE ###

n,m = input().split()
n,m = int(n),int(m)
price = []
honsu = []
for i in range(n):
  a,b = input().split()
  price.append(int(a))
  honsu.append(int(b))
 
 
for j in range(n):
  k = j + 1
  while(k<n):
    if price[j] > price[k]:
      temp1,temp2 = price[j],honsu[j]
      price[j] = price[k]
      honsu[j] = honsu[k]
      price[k] = temp1
      honsu[k] = temp2
    k+=1
money = 0
l = 0
while m > 0:
  if(m-honsu[l]>0):
    m -= honsu[l]
    money += honsu[l] * price[l]
  else:
    c = abs(m-honsu[l])
    m -= honsu[l]-c
    money += (honsu[l]-c) * price[l]
  l += 1
print(money)

### FIXED CODE ###

n,m = map(int,input().split())
price = []
honsu = []
c = []
for i in range(n):
  a,b = map(int,input().split())
  c.append([a,b])
c = sorted(c)
price,honsu=zip(*c)
money = 0
l = 0
while m > 0:
  if(m-honsu[l]>0):
    m -= honsu[l]
    money += honsu[l] * price[l]
  else:
    c = abs(m-honsu[l])
    m -= honsu[l]-c
    money += (honsu[l]-c) * price[l]
  l += 1
print(money)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import math
sys.setrecursionlimit(500005)


def solve(N: int):
    for i in range(1,N+1):
        ri = math.ceil(math.sqrt(i))
        counter = 0
        for x in range(1,ri+1):
            for y in range(1,ri+1):
                for z in range(1,ri+1):
                    if (x*x+y*y+z*z+x*y+y*z+z*x == i):
                        counter += 1
        print(counter)


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import math
sys.setrecursionlimit(500005)


def solve(N: int):
    rn = math.ceil(math.sqrt(N))
    arr = [0] * N
    counter = 0
    for x in range(1,rn+1):
        for y in range(1,rn+1):
            for z in range(1,rn+1): 
                if ((x*x+y*y+z*z+x*y+y*z+z*x) > N ):
                    continue
                else:
                    arr[(x*x+y*y+z*z+x*y+y*z+z*x) -1 ] += 1
    for i in arr:
        print(i)

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

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

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))
    Aset = set(A)

    gcdnum = 1
    gcd = math.gcd

    for a in Aset:
        gcdnum = (gcdnum * a) // gcd(gcdnum, a)
    ans = 0
    for a in A:
        a = gcdnum // a
        ans += a
        ans %= mod

    print(ans)




if __name__ == '__main__':
    solve()

### FIXED CODE ###

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))

    lcmnum = 1
    def gcd(a, b):
        if (a == 0):
            return b
        return gcd(b%a, a)

    def lcm(x, y):
        return (x * y) // gcd(x, y)
    for a in A:
        lcmnum = lcm(lcmnum, a)

    ans = 0
    for a in A:
        a = lcmnum // a
        ans += a
    ans %= mod

    print(ans)




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

N, Q = map(int, input().split())
 
S = input()
 
lr = []
 
for q in range(Q):
  lr.append(list(map(int, input().split())))
  
for q in lr:
  st = q[0]-1
  en = q[1]
  s = S[st:en]
  print(s.count('AC'))

### FIXED CODE ###

import sys
 
N, Q = map(int, input().split())
 
S = input()
 
lr = [list(map(int, i.split())) for i in sys.stdin]

Sum = [0]

sum_ = 0

for i in range(len(S)-1):
  if S[i] == 'A' and S[i+1] == 'C':
    sum_ += 1
  Sum.append(sum_)

for  q in range(Q):
  ans = Sum[lr[q][1]-1]-Sum[lr[q][0]-1]
  print(ans)
### BUGGY CODE ###

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

q = list(input())
tList = list(map(int,input().split()))

tCount = 0


for tmp_t in tList:
    if 0 < sList.count(tmp_t):
        tCount += 1

print(tCount)

### FIXED CODE ###

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

q = list(input())
tList = list(map(int, input().split()))

tCount = 0


def middle_idx(tmin, tmax):
    return int((tmin + tmax) / 2)


for tmp_t in tList:
    tmp_min = 0
    tmp_max = len(sList) - 1
    if (tmp_t >= sList[tmp_min] and tmp_t <= sList[tmp_max]):
        while ( tmp_max - tmp_min > 1 ):
            tmp_mid = middle_idx(tmp_max, tmp_min)
            if sList[tmp_mid] > tmp_t:
                tmp_max = tmp_mid
            elif sList[tmp_mid] < tmp_t:
                tmp_min = tmp_mid
            elif sList[tmp_mid] == tmp_t:
                tmp_min = tmp_max
        if(sList[tmp_max] == tmp_t or sList[tmp_min] == tmp_t or sList[tmp_mid] == tmp_t):
            tCount += 1
    else:
        pass

print(tCount)
### BUGGY CODE ###

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

DP = [[{} for _ in range(N)] for _ in range(N)]
DP[0][N-1][(1, 1)] = float("inf")

def initialize(l, r, xl, xr):
  for m in range(l+1, r):
    DP[l][m][(xl, xl+xr)] = float("inf")
    DP[m][r][(xl+xr, xr)] = float("inf")
    initialize(l, m, xl, xl+xr)
    initialize(m, r, xl+xr, xr)
  return

initialize(0, N-1, 1, 1)

for i in range(N-1):
  for xl, xr in DP[i][i+1].keys():
    DP[i][i+1][(xl, xr)] = xl * A[i] + xr * A[i+1]
    
for d in range(2, N):
  for i in range(N-d):
    l = i
    r = i+d
    for xl, xr in DP[l][r].keys():
      tmp = float("inf")
      for m in range(l+1, r):
        v = DP[l][m][(xl, xl+xr)] + DP[m][r][(xl+xr, xr)] - (xl+xr) * A[m]
        if v < tmp:
          tmp = v
      DP[l][r][(xl, xr)] = tmp
print(DP[0][N-1][(1,1)])

### FIXED CODE ###

from functools import lru_cache
 
N = int(input())
A = list(map(int, input().split()))
 
@lru_cache(None)
def f(l, r, xl, xr):
  if l+1 == r:
    return xl * A[l] + xr * A[r]
  tmp = float("inf")
  for m in range(l+1, r):
    v = f(l, m, xl, xl+xr) + f(m, r, xl+xr, xr) - (xl+xr) * A[m]
    tmp = min(tmp, v)
  return tmp
 
print(f(0, N-1, 1, 1))
### BUGGY CODE ###

#ないよりも10倍以上早くなる
import sys
input = sys.stdin.readline
 
K,S=map(int,input().split())
if 2<=K<=2500 and 0<=S<=3*K:
    count=0
    Ks=[]
    for x in range(K+1):
        for y in range(K+1):
            for z in range(K+1):
                if z==S-x-y: count+=1
    print(count)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
K,S=map(int,input().split())
count=0
for x in range(K+1):
    for y in range(K+1):
        if S-(x+y)>=0 and S-(x+y)<=K: count+=1
print(count)
### BUGGY CODE ###

import sys
from operator import itemgetter
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
def main():
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while(e[0] > d):
			if cont == True:
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			else:
				mini = min(kouho)
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			cont = True
			if q < Q-1:
				q = q + 1
				d = int(inputs())
			else:
				flag = True
				q = q + 1
				break
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			cont = False
	for t in [None]*(Q-q):
		print(-1)
		
def sub():
	V = [list(map(int,inputs().split())) for p in [0]*N]
	M = [int(inputs()) for p in [0]*Q]
	V.sort(key = lambda x:(x[2],x[0],x[1]))
	for v in V:
		v[0] -= v[2]
		v[1] -= v[2] + 1
	for m in M:
		for n in range(N):
			if V[n][0] <=m and m <= V[n][1]:
				print(V[n][2])
				break
		else:
			print(-1)


if N>500000:
	sub()
else:
	main()

### FIXED CODE ###

import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				print(mini-(mini//1000000001)*1000000002)
			else:
				mini = min(kouho)
				print(mini-(mini//1000000001)*1000000002)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			if mini == e[2]:
				cont = False
	for t in [None]*(Q-q):
		print(-1)
main()