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

def gcd(x, y):
    if x > y:
        tmp = x
        x = y
        y = tmp
    if x == 0:
        return y
    else:
        return gcd(y%x, x)

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

# if N == 2:
#     print(max(A[0], A[1]))
#     return 0

Llist = [0]
Rlist = [0]

for i in range(N):
    Llist.append(gcd(Llist[i], A[i])) 
    Rlist.insert(0, gcd(Rlist[0], A[N-1-i]))

ans = 0
for i in range(N):
    t = gcd(Llist[i], Rlist[i+1])
    if ans < t:
        ans = t

print(ans)


### FIXED CODE ###

def gcd(x, y):
    if x > y:
        tmp = x
        x = y
        y = tmp
    if x == 0:
        return y
    else:
        return gcd(y%x, x)

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

Llist = [0]
Rlist = [0]

for i in range(N):
    Llist.append(gcd(Llist[i], A[i])) 
    # Rlist.insert(0, gcd(Rlist[0], A[N-1-i]))
    Rlist.append(gcd(Rlist[i], A[N-1-i]))
Rlist = Rlist[::-1]
ans = 0
for i in range(N):
    t = gcd(Llist[i], Rlist[i+1])
    if ans < t:
        ans = t

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

n = int(input())
a = list(map(int,input().split()))
M = max(a)+1
if M == 2:
    print("pairwise coprime")
    exit()
count = [0]*(M)

for i in range(2,M):
    if count[i] == 0:
        for j in range(i,M,i):
            if count[j] == 0:
                count[j] = i
check = [0]*(M)
for i in a:
    x = i
    while x > 1:
        check[count[x]] += 1
        y = count[x]
        while x%y == 0:
            x //= y
ans = max(check)
if ans == 1:
    print("pairwise coprime")
elif ans == n:
    print("not coprime")
else:
    print("setwise coprime")

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
M = max(a)+1
if M == 2:
    print("pairwise coprime")
    exit()
count = [0]*(M)
prime = [2,3,5,7,11,13]
for i in range(14,int(M**0.5)+2):
    check = True
    for j in prime:
        if i%j == 0:
            check = False
            break
    if check:
        prime.append(i)

for i in a:
    for j in prime:
        if i < j:
            break
        if i%j==0:
            while i%j == 0:
                i //= j
            count[j] += 1
    if i > 1:
        count[i] += 1

ans = max(count)

if ans == 1:
    print("pairwise coprime")
elif ans == n:
    print("not coprime")
else:
    print("setwise coprime")
### BUGGY CODE ###

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

l=list()
c=2
while m>1:
  if m%c==0:
    l.append(c)
    m = m/c
  else:
    c+=1

e=[[x,l.count(x)] for x in set(l)]    

l2=[1]
for i in range(len(e)):
  for j in range(len(l2)):
    for k in range(e[i][1]):
      l2.append(l2[j]*e[i][0]**(k+1))

l2.sort()
m=1
for i in range(len(l2)):
  if a//n>=l2[i]:
    m=max(l2[i],m)

print(m)


### FIXED CODE ###

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

d=list()
for i in range(1,int(m**0.5)+1):
  if m%i==0:
    d.append(i)
    if i!=m//i:
      d.append(m//i)

d.sort()

c=1
for i in range(len(d)):
  if m//d[i]>=n:
    c=max(d[i],c)

print(c)
### BUGGY CODE ###

s=input()
k=int(input())
cnt=set()
for i in range(len(s)):
  for j in range(len(s)-i):
    cnt.add(s[i:i+j+1])
ans=sorted(list(cnt))
print(ans[k-1])

### FIXED CODE ###

s=input()
k=int(input())
cnt=set()
for i in range(len(s)):
  for j in range(min(len(s)-i,k)):
    cnt.add(s[i:i+j+1])
ans=sorted(list(cnt))
print(ans[k-1])
### BUGGY CODE ###

def main():
    N=int(input())
    A=list(map(int,input().split()))
    from math import sqrt
    s=set()
    A.sort()
    a=0
    t=0
    if A[0]!=1:
        for i in A:
            if i in s:
                if t==i:
                    a-=1
                    t=0
                continue
            s.add(i)
            for j in range(2,int(sqrt(i)+1.5)):
                if i%j:
                    continue
                if j in s:
                    break
                if i//j in s:
                    break
            else:
                t=i
                a+=1
    else:
        if N>1 and A[1]==1:
            a=0
        else:
            a=1
    print(a)
main()

### FIXED CODE ###

from math import sqrt
from time import perf_counter
t0=perf_counter()
N=int(input())
A=list(map(int,input().split()))
A.sort()
def main():
    a=0
    s=set()
    t=0
    if A[0]!=1:
        for i in A:
            if i in s:
                if t==i:
                    a-=1
                    t=0
                continue
            for j in range(2,int(sqrt(i)+1.1)):
                if i%j:
                    continue
                if j in s:
                    break
                if i//j in s:
                    break
            else:
                t=i
                a+=1
            s.add(i)
            if perf_counter()-t0>1.9:
                a=N
                break                
    else:
        if N>1 and A[1]==1:
            a=0
        else:
            a=1
    print(a)
main()
### BUGGY CODE ###

import math
S = int(input())

x,y = 1,S

for i in range(2,1+int(math.sqrt(S))):
    if S%i == 0:
        x = i
        y = S//i
        if y <= 10**9:
            break
    
    
print("{} {} {} {} {} {}".format(0,0,0,x,y,x))


### FIXED CODE ###

import math
S = int(input())

x,y = 1,S
ret = int(math.sqrt(S))
if(ret**2 == S):
    print("{} {} {} {} {} {}".format(0,0,0,ret,ret,ret))
else:
    print("{} {} {} {} {} {}".format(0,0,ret+1,(ret+1)**2-S,1,ret+1))
### BUGGY CODE ###

import heapq
n=int(input())
a=list(map(int,input().split()))
q=a[0:n]
sums=[0]*(n+1)
sums[0]=sum(q)
heapq.heapify(q)
am=a[n:2*n]
for i in range(0,n):
    heapq.heappush(q,am[i])
    heapq.heappop(q)
    sums[i+1]=sum(q)
p=a[2*n:3*n]
p=list(map(lambda x: x*(-1),p))
sums[n]+=sum(p)
heapq.heapify(p)
for i in range(n-1,-1,-1):
    heapq.heappush(p,(-1)*am[i])
    heapq.heappop(p)
    sums[i]+=sum(p)
print(max(sums))

### FIXED CODE ###

import heapq
n=int(input())
a=list(map(int,input().split()))
q=a[0:n]
sums=[0]*(n+1)
sums[0]=sum(q)
heapq.heapify(q)
am=a[n:2*n]
for i in range(0,n):
    heapq.heappush(q,am[i])
    sums[i+1]=sums[i]+am[i]-heapq.heappop(q)
p=a[2*n:3*n]
p=list(map(lambda x: x*(-1),p))
sump=sum(p)
sums[n]+=sump
heapq.heapify(p)
for i in range(n-1,-1,-1):
    heapq.heappush(p,(-1)*am[i])
    sump=sump-am[i]-heapq.heappop(p)
    sums[i]+=sump
print(max(sums))
### BUGGY CODE ###

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

    answer = sum(A)
    numNumberList = [0] * 100001

    for Ai in A:
        numNumberList[Ai] = A.count(Ai)

    for i in range(Q):
        B, C = list(map(int, input().split()))
        answer = answer + (int(C) - int(B)) * numNumberList[B]

        numNumberList[C] = numNumberList[C] + numNumberList[B]
        numNumberList[B] = 0

        print(answer)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

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

    answer = sum(A)
    setA = set(A)
    numNumberList = [0] * 100001

    for Ai in A:
        numNumberList[Ai] = numNumberList[Ai] + 1    

    for i in range(Q):
        B, C = list(map(int, sys.stdin.readline().split()))
        answer = answer + (int(C) - int(B)) * numNumberList[B]

        numNumberList[C] = numNumberList[C] + numNumberList[B]
        numNumberList[B] = 0

        print(answer)

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

n = int(input())
l = list(map(int,input().split()))
anz = 1
for i in l:
    anz *= i
print(anz if anz <= 1000000000000000000 else -1)

### FIXED CODE ###

import sys
n = int(input())
l = list(map(int,input().split()))
if 0 in l:
  print(0)
  sys.exit()
flag = True
anz = 1
for i in l:
  anz *= i
  if anz > 1000000000000000000:
    flag = False 
    break
print (anz if flag else -1)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
for i in range(n):
    print(max(a[:i]+a[i+1:]))


### FIXED CODE ###

import numpy as np
n = int(input())
a = [int(input()) for _ in range(n)]
t1 = max(a)
t1_idx = [i for i, v in enumerate(a) if v == t1]
a.sort()

if len(t1_idx) < 2:
    try:
        t2 = a[-1*len(t1_idx)-1]
    except:
        for i in range(n):
            print(t1)

    for i in range(n):
        if i in t1_idx:
            print(t2)
        else:
            print(t1)
else:
    for i in range(n):
        print(t1)
### BUGGY CODE ###

N = int(input())
S = input()
cnt = []

for i in range(0, len(S)):
    left = S[:i]
    leader = S[i]
    right = S[i+1:]
    temp_cnt = 0
    temp_cnt += left.count('W')
    temp_cnt += right.count('E')
    cnt.append(temp_cnt)
    
output = min(cnt)

print(output)

### FIXED CODE ###

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

left = 0
right = S[1:].count('E')

cnt = [left+right]

for i in range(1,len(S)):
    if S[i-1] == 'W':
        left += 1
    
    if S[i] == 'E':
        right -= 1
        
    cnt.append(left+right)

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

# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

# TLE が厳しすぎる

def accumulate(S1, S2):
    res = [0]
    c = 0
    for i in range(min(len(S1), len(S2))):
        if S1[i] == S2[i]:
            c += 1
        res.append(c)
    return res

inf = 2 * 10**9
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    z1 = accumulate(C1, C2);  z1.reverse()
    Z1.append(z1)
    Z2.append([])
    for j in range(1, H+1):
        #z1 = accumulate(C1, C2[j:]);  z1.reverse();  Z1.append(z1)
        res = [0]
        c = 0
        for i in range(H-j):
            if C1[i] == C2[i+j]:
                c += 1
            res.append(c)
        res.reverse();  Z1.append(res)

        #z2 = accumulate(C1[j:], C2);  z2.reverse();  Z2.append(z2)
        res = [0]
        c = 0
        for i in range(H-j):
            if C1[i+j] == C2[i]:
                c += 1
            res.append(c)
        res.reverse();  Z2.append(res)
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + (Z1[j-k][k] if j>=k else Z2[k-j][j])
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)


### FIXED CODE ###

# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate_reverse(S1, S2):
    n = min(len(S1), len(S2))
    res = [0] * (n+1)
    c = 0
    for i in range(n):
        if S1[i] == S2[i]:
            c += 1
        res[n-i-1] = c
    return res

inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    Z1.append(accumulate_reverse(C1, C2))
    for j in range(1, H+1):
        Z1.append(accumulate_reverse(C1, C2[j:]))
        Z2.append(accumulate_reverse(C1[j:], C2))
    Z1 += Z2[::-1]
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + Z1[j-k][min(j, k)]
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)
### BUGGY CODE ###

import math
import sys
import itertools
from math import gcd
from math import sqrt
from sys import stdin
def input() : return stdin.readline().rstrip()
def mips():
    return map(int,input().split())
def ii():
    return int(input())
sys.setrecursionlimit(10**9)

N,K = mips()
ans = 10**9
P = [p for p in mips()]
L = list(map(list,itertools.permutations(P,K)))
for el in L:
    ans = min(ans,sum(el))
print(ans)
    


### FIXED CODE ###

import math
import sys
import itertools
from math import gcd
from math import sqrt
from sys import stdin
def input() : return stdin.readline().rstrip()
def mips():
    return map(int,input().split())
def ii():
    return int(input())
sys.setrecursionlimit(10**9)

N,K = mips()
ans = 0
P = [p for p in mips()]
P.sort()
for i in range(K):
    ans += P[i]
print(ans)
### BUGGY CODE ###

import sys
from itertools import combinations

input = sys.stdin.readline


def main():
    n = int(input())
    lines = ["".join(sorted(input().strip())) for _ in range(n)]
    count = 0
    for text in set(lines):
        count += len([_ for _ in combinations(range(lines.count(text)), 2)])
    print(count)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from functools import reduce
from operator import mul
from collections import Counter

input = sys.stdin.readline


def cmb(n, r):
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


def main():
    n = int(input())
    lines = ["".join(sorted(input().strip())) for _ in range(n)]
    count = 0
    for _, v in Counter(lines).most_common():
        if v == 1:
            break
        count += cmb(v, 2)
    print(count)


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

import sys
sys.setrecursionlimit(10 ** 7)
#f = open('input.txt','r')
input = sys.stdin.readline
#sys.stdin = f

N = int(input())
A = [int(input()) for _ in range(N)]
cntA = [0 for _ in range(max(A)+1)]
for a in A:
    cntA[a] += 1
    cntA[a] %= 2
print(sum(cntA))

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
cnt = 1
ans = 0
if len(A) == 1:
    print(1)
    exit()
for i in range(1,N):
    if A[i-1] == A[i]:
        cnt += 1
    else:
        ans += cnt%2
        cnt = 1
if cnt >= 1:
    ans += cnt%2
print(ans)
### BUGGY CODE ###

#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a // gcd(a, b) * b
#print(lcm(lcm(1000000,999999),999998))
#print(999998//2*999999)


#print(1000000*999999*999998%mod)
n=I()
lis=LI()
promod=1
LCM=1
for i in range(n):
    LCM=lcm(lis[i],LCM)
#print(LCM)
ans=0
for i in range(n):
    ans=(ans+LCM//lis[i])%mod
print(ans)
'''for i in range(n):
    promod=(promod*(lis[i]%mod))%mod
smmod=0
for i in range(n):
    smmod=(smmod+promod*pow(lis[i],mod-2,mod))%mod
#print(smmod)
x=(promod*pow(LCM,mod-2,mod))%mod
ans=(smmod*pow(x,mod-2,mod))%mod
print(ans)'''
    
    


### FIXED CODE ###

#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a // gcd(a, b) * b
#print(lcm(lcm(1000000,999999),999998))
#print(999998//2*999999)


#print(1000000*999999*999998%mod)
n=I()
lis=LI()
promod=1
LCM=1
for i in range(n):
    LCM=lcm(lis[i],LCM)
#print(LCM)
for i in range(n):
    promod=(promod*(lis[i]%mod))%mod
smmod=0
for i in range(n):
    smmod=(smmod+promod*pow(lis[i],mod-2,mod))%mod
#print(smmod)
x=(promod*pow(LCM,mod-2,mod))%mod
ans=(smmod*pow(x,mod-2,mod))%mod
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
ans=N
while ans>=K:
  ans-=K
  
nk=abs(ans-K)
if nk<K and nk<N:
  print(nk)
else:
  print(ans)  


### FIXED CODE ###

N,K=map(int,input().split())
ans=N%K
  
nk=abs(ans-K)
if nk<K and nk<N:
  print(nk)
else:
  print(ans)
### BUGGY CODE ###

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


for i in range(10**111111):
  a =0

if ( A * 3 + P ) % 2 == 0:
  print(int( ( A * 3 + P ) / 2 ))
else:
  print( int(( A * 3 + P - 1) / 2 ))

### FIXED CODE ###

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

if ( A * 3 + P ) % 2 == 0:
  print(int( ( A * 3 + P ) / 2 ))
else:
  print( int(( A * 3 + P - 1) / 2 ))
### BUGGY CODE ###

n, k = map(int, input().split())
aList = list(map(int, input().split()))
aSet = set(aList)
aCount = [aList.count(i) for i in aSet]
aCount.sort()
aCount = aCount[:-k]
print(sum(aCount))


### FIXED CODE ###

n, k = map(int, input().split())
aList = list(map(int, input().split()))
num = [0 for _ in range(n + 1)]
for i in aList:
    num[i] += 1
num.sort()
num = num[:-k]
print(sum(num))
### BUGGY CODE ###

from collections import defaultdict


def main():
    N = int(input())
    A = list(map(int, input().split()))
    MAX_EXP = 30  # 2**30 < 2 * (10 ** 9) < 2**31
    pow2 = [1] * (MAX_EXP + 1)
    for e in range(1, MAX_EXP + 1):
        pow2[e] = 2 * pow2[e - 1]
    counter = defaultdict(int)
    for a in A:
        counter[a] += 1
    DISTINCT_A = list(counter.keys())
    DISTINCT_A.sort(reverse=True)  # 大きい順に並べておく
    # 和が2のべき乗になるペアの間をedgeで結んだグラフを作る
    adj = defaultdict(list)
    for a in DISTINCT_A:
        for e in range(MAX_EXP + 1):
            b = pow2[e] - a
            if counter[b] == 0:
                continue
            if a > b:
                adj[a].append(b)
            elif a < b:
                adj[b].append(a)
    # ノードの値が大きい順に貪欲にペアを作っていく
    ans = 0
    for a in DISTINCT_A:
        for b in adj[a]:
            cnt = min(counter[a], counter[b])
            ans += cnt
            counter[a] -= cnt
            counter[b] -= cnt
    # 最後に2のべき乗のノードはそれ単体でペアを作れるので、その分を足す
    for e in range(MAX_EXP + 1):
        a = pow2[e]
        ans += counter[a] // 2
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict


def main():
    N = int(input())
    A = list(map(int, input().split()))
    MAX_EXP = 30  # 2**30 < 2 * (10 ** 9) < 2**31
    pow2 = [1] * (MAX_EXP + 1)
    for e in range(1, MAX_EXP + 1):
        pow2[e] = 2 * pow2[e - 1]
    counter = defaultdict(int)
    for a in A:
        counter[a] += 1
    DISTINCT_A = list(counter.keys())
    DISTINCT_A.sort(reverse=True)  # 大きい順に並べておく
    # 和が2のべき乗になるペアの間をedgeで結んだグラフを考え
    # ノードの値が大きい順に貪欲にペアを作っていく
    ans = 0
    for a in DISTINCT_A:
        b = pow2[a.bit_length()] - a
        if counter[b] == 0:
            continue
        cnt = min(counter[a], counter[b])
        ans += cnt
        counter[a] -= cnt
        counter[b] -= cnt
    # 最後に2のべき乗のノードはそれ単体でペアを作れるので、その分を足す
    for e in range(MAX_EXP + 1):
        a = pow2[e]
        ans += counter[a] // 2
    print(ans)


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

# -*- coding: utf-8 -*-
import sys
import collections

def main():
	N, Q = map(int, input().split(" "))
	S = input()
	S = list(S)
	
	Qs = []
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		Qs.append((l, r))
	
	ans = []
	for i, val in enumerate(Qs):
		l, r = val
		tmp = S[l-1:r]
		ans_t = 0
		
		for j, val in enumerate(tmp):
			if val == "A":
				if j+1 < len(tmp) and tmp[j+1] == "C":
					ans_t += 1
		ans.append(ans_t)
	
	
	for i in ans:
		print(i)
	
if __name__ == "__main__":
	main()
	

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

def main():
	N, Q = map(int, input().split(" "))
	S = input()
	S = list(S)
	
	Qs = []
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		Qs.append((l, r))
	
	ptn = []
	hit = 0
	flg = False
	for i, val in enumerate(S):
		if val == "A":
			ptn.append(hit)
			if i+1 < len(S) and S[i+1] == "C":
				hit += 1
				ptn.append(hit)
				flg = True
		else:
			if flg == False:
				ptn.append(hit)
			else:
				flg = False
		
	ans = []
	for i, val in enumerate(Qs):
		l, r = val
		if l == r:
			ans.append(0)
			break
			
		tmp = ptn[r-1] - ptn[l-1]
		ans.append(tmp)
	
	
	for i in ans:
		print(i)
	
if __name__ == "__main__":
	main()
### BUGGY CODE ###

import heapq
import sys

class rode():
    def __init__(self,x,y):
        self.x = x
        self.y = y
    def __lt__(self, other):
        return self.y < other.y
    def __gt__(self, other):
        return other > self
    def __le__(self, other):
        return not(other > self)
    def __ge__(self, other):
        return not(self > other)

n,m = map(int,input().split())
da = [[] for i in range(n)]
for i in range(m):
    l,r,c = map(int,input().split())
    da[l-1].append([r-1,c])
for i in range(1,n):
    da[i].append([i-1,0])
pq=[]
ju = [False for i in range(n)]
ju[0] = True
for i in da[0]:
    heapq.heappush(pq, rode(i[0],i[1]))
while(len(pq)):
    now = heapq.heappop(pq)
    if now.x == n-1:
        print(now.y)
        sys.exit()
    if ju[now.x]:
        continue
    ju[now.x] = True
    for i in da[now.x]:
        heapq.heappush(pq,rode(i[0],now.y+i[1]))
print(-1)

### FIXED CODE ###

import heapq
import numpy as np
import sys

n,m = map(int,input().split())
da = [[] for i in range(n)]
for i in range(1,n):
    da[i].append([i-1,0])
for i in range(m):
    l,r,c = map(int,input().split())
    da[l-1].append([r-1,c])
pq=[]
ju = np.zeros(n,dtype=bool)
ju[0] = True
for i in da[0]:
    heapq.heappush(pq, [i[1],i[0]])
while(len(pq)):
    now = heapq.heappop(pq)
    if now[1] == n-1:
        print(now[0])
        sys.exit()
    if ju[now[1]]:
        continue
    ju[now[1]] = True
    for i in da[now[1]]:
        if ju[i[0]]:
            continue
        heapq.heappush(pq,[now[0]+i[1],i[0]])
print(-1)
### BUGGY CODE ###

# は？なんやこれ無限にわからん
# 半分全列挙的な気持ちでやる？
x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
ab = []
for av in a:
    for bv in b:
        ab.append(av + bv)
ab = sorted(ab, reverse=True)[:k]
abc = []
for abv in ab:
    for cv in c:
        abc.append(abv + cv)
abc = sorted(abc, reverse=True)[:k]
for ans in abc:
    print(ans)


### FIXED CODE ###

# は？なんやこれ無限にわからん
# 半分全列挙的な気持ちでやる？
x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
ab = []
for av in a:
    for bv in b:
        ab.append(av + bv)
ab = sorted(ab, reverse=True)[:k]
abc = []
for abv in ab:
    for cv in c:
        abc.append(abv + cv)
abc = sorted(abc, reverse=True)[:k]
for ans in abc:
    print(ans)