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

import sys
input = sys.stdin.readline

N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
tmp = []
for _ in range(M):
    tmp.append( list(map(int,input().split())))

tmp = sorted(tmp,key = lambda x:-x[1])
cnt = 0
t = []
for i in range(M):
    t=t+[tmp[i][1]]*tmp[i][0]
    cnt+= tmp[i][0]
    if cnt >=N:
        break
A = sorted(A+t,reverse = 1)

print(sum(A[:N]))


### FIXED CODE ###

import sys
input = sys.stdin.readline

def sol():
    N,M = list(map(int,input().split()))
    A = list(map(int,input().split()))
    tmp = sorted([list(map(int,input().split())) for _ in range(M)],key = lambda x:-x[1])

    t = []
    for a,b in tmp:
        t+=[b]*a
        
        if len(t) >=N:
            break

    A += t
    A.sort(reverse = 1)
    print(sum(A[:N]))

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

N = int(input())
A = list(map(int, input().split()))
A.sort()
cnt = 0
for i in range(N):
    for j in range(i):
        if A[i] % A[j] == 0:
            cnt += 1
            if A[i] == A[j] and i == j+1:
                cnt += 1
            break
print(N - cnt)


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
counter = Counter(A)
B = [1] * (max(A) + 1)
for a in A:
    for k in range(a  * 2,len(B),a):
            B[k] = 0
print(sum(B[a] == 1 and counter[a] == 1 for a in A))
### BUGGY CODE ###

h,w = map(int,input().split())
c,d = map(int,input().split())
e,f = map(int,input().split())
s = []
t = []
m = h*w
for i in range(h):
    s.append(input())
    t.append([m]*w)
c -= 1
d -= 1
t[c][d] = 0
cnt = 0
stc1 = [[c,d]]
stc2 = []
while(1):
#for i in range(10):
    if(c > 0):
        if(s[c-1][d] == '.' and t[c-1][d] > cnt):
            t[c-1][d] = cnt
            stc1.append([c-1,d])
    if(d > 0):
        if(s[c][d-1] == '.' and t[c][d-1] > cnt):
            t[c][d-1] = cnt
            stc1.append([c,d-1])
    if(c < h-1):
        if(s[c+1][d] == '.' and t[c+1][d] > cnt):
            t[c+1][d] = cnt
            stc1.append([c+1,d])
    if(d < w-1):
        if(s[c][d+1] == '.' and t[c][d+1] > cnt):
            t[c][d+1] = cnt
            stc1.append([c,d+1])
    for j in range(-2,3):
        for k in range(-2,3):
            if(abs(j)+abs(k) > 1):
                if(c+j >= 0 and c+j < h and d+k >= 0 and d+k < w):
                    if(s[c+j][d+k] == '.' and t[c+j][d+k] > cnt+1):
                        t[c+j][d+k] = min(t[c+j][d+k],cnt+1)
                        stc2.append([c+j,d+k])
    if(len(stc1) > 1):
        stc1 = stc1[1:]
        c = stc1[0][0]
        d = stc1[0][1]
    else:
        if(len(stc2) > 0):
            stc1 = stc2
            stc2 = []
            c = stc1[0][0]
            d = stc1[0][1]
            cnt += 1
        else:
            break
            
if(t[e-1][f-1] == m):
    print(-1)
else:
    print(t[e-1][f-1])

### FIXED CODE ###

h,w = map(int,input().split())
c,d = map(int,input().split())
e,f = map(int,input().split())
s = []
t = []
m = h*w
for i in range(h):
    s.append(input())
    t.append([m]*w)
c -= 1
d -= 1
t[c][d] = 0
cnt = 0
stc1 = [[c,d]]
stc2 = []
a = 0
while(1):
    if(c > 0):
        if(s[c-1][d] == '.' and t[c-1][d] > cnt):
            t[c-1][d] = cnt
            stc1.append([c-1,d])
    if(d > 0):
        if(s[c][d-1] == '.' and t[c][d-1] > cnt):
            t[c][d-1] = cnt
            stc1.append([c,d-1])
    if(c < h-1):
        if(s[c+1][d] == '.' and t[c+1][d] > cnt):
            t[c+1][d] = cnt
            stc1.append([c+1,d])
    if(d < w-1):
        if(s[c][d+1] == '.' and t[c][d+1] > cnt):
            t[c][d+1] = cnt
            stc1.append([c,d+1])
    for j in range(-2,3):
        for k in range(-2,3):
            if(abs(j)+abs(k) > 1):
                if(c+j >= 0 and c+j < h and d+k >= 0 and d+k < w):
                    if(s[c+j][d+k] == '.' and t[c+j][d+k] > cnt+1):
                        t[c+j][d+k] = min(t[c+j][d+k],cnt+1)
                        stc2.append([c+j,d+k])
    if(len(stc1) > a+1):
        a += 1
        c = stc1[a][0]
        d = stc1[a][1]
    else:
        if(len(stc2) > 0):
            stc1 = stc2
            stc2 = []
            a = 0
            c = stc1[0][0]
            d = stc1[0][1]
            cnt += 1
        else:
            break
if(t[e-1][f-1] == m):
    print(-1)
else:
    print(t[e-1][f-1])
### BUGGY CODE ###

def main():
    r, g, b, n = map(int, input().split())

    count = 0
    for i in range((n+(r-1))//r+1):
        for j in range((n+(g-1))//g+1):
            for k in range((n+(b-1))//b+1):
                if (i*r)+(j*g)+(k*b) == n:
                    count += 1
    print(count)
          
 

if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    r, g, b, n = map(int, input().split())

    count = 0

    for i in range(3001):
        for j in range(3001):
            v = (i*r) + (j*g) 
            if n >= v and (n-v)%b == 0: 
                count += 1



    print(count)
                

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

s = input()
c = 0
while 'BW' in s:
  c += 1
  s = s.replace("BW", "WB", 1)
print(c)

### FIXED CODE ###

s = input()
t = list(s).count('W')
a = [i for i, x in enumerate(list(s)) if x == 'W']
b = int((t - 1) * t / 2)
print(sum(a)-b)
### BUGGY CODE ###

n = int(input())
s = []
for i in range(n):
    s.append(input())
ss = set(s)
sd = {}
for i in ss:
    sd[i] = s.count(i)
m = max(sd.values())
r = [k for k, v in sd.items() if v == m]
r.sort()
for i in r:
    print(i)

### FIXED CODE ###

n = int(input())
s = {}
for i in range(n):
    w = input()
    if w in s.keys():
        s[w] = s[w] + 1
    else:
        s[w] = 1
m = max(s.values())
r = [k for k, v in s.items() if v == m]
r.sort()
for i in r:
    print(i)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
import pprint

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	# a_ext = {}
	b_sum_ext = {}
	b_ext = []
	# ai + aj = (j+1) - (i+1)
	# ai + i + 1 = -aj + j + 1

	for i, ai in enumerate(a):
		# a_ext[a[i] + i + 1] = 1
		log.print(a[i]+i+1, -a[i]+i+1)
		b_sum_ext[-a[i]+i+1] = b_sum_ext.get(-a[i]+i+1, 0)+1
	# log.print(b_sum_ext)
	for i in range(n):
		b_sum_ext[-a[i]+i+1] = b_sum_ext.get(-a[i]+i+1, 0)-1
		b_ext.append(dict(b_sum_ext))
	# log.print(b_ext)
	cnt = 0
	log.print(cnt)
	cnt = 0
	for i, ai in enumerate(a):
		if b_ext[i].get(a[i] + i + 1, 0) != 0:
			log.print(i+1, a[i] + i + 1)
			cnt += b_ext[i].get(a[i] + i + 1, 0)
	print(cnt)

	


main()

### FIXED CODE ###

#!/usr/bin/env python3

import sys
import pprint

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	# a_ext = {}
	b_sum_ext = {}
	b_ext = []
	# ai + aj = (j+1) - (i+1)
	# ai + i + 1 = -aj + j + 1

	for i, ai in enumerate(a):
		# a_ext[a[i] + i + 1] = 1
		log.print(a[i]+i+1, -a[i]+i+1)
		b_sum_ext[-a[i]+i+1] = b_sum_ext.get(-a[i]+i+1, 0)+1
	cnt = 0
	log.print(cnt)
	cnt = 0
	for i, ai in enumerate(a):
		b_sum_ext[-a[i]+i+1] = b_sum_ext.get(-a[i]+i+1, 0)-1
		if b_sum_ext.get(a[i] + i + 1, 0) != 0:
			log.print(i+1, a[i] + i + 1)
			cnt += b_sum_ext.get(a[i] + i + 1, 0)
	print(cnt)

	


main()
### BUGGY CODE ###

from collections import deque

def solve(s):
    que = deque()
    que.append(s)
    while len(que) > 0:
        top = que.pop()
        if top == '':
            return 'YES'

        if top[:5] == 'dream':
            if top[5:7] == 'er':
                que.append(s[:7])
            que.append(s[:5])
        elif top[:5] == 'erase':
            if len(top) > 5 and top[5] == 'r':
                que.append(top[:6])
            else:
                que.append(top[:5])
    return 'NO'

print(solve(input()))


### FIXED CODE ###

from collections import deque

def solve(s):
    stack = deque()
    stack.append(s)
    while len(stack) > 0:
        top = stack.pop()
        if top == '':
            return 'YES'

        if top[:5] == 'dream':
            if top[5:7] == 'er':
                stack.append(top[7:])
            stack.append(top[5:])
        elif top[:5] == 'erase':
            if len(top) > 5 and top[5] == 'r':
                stack.append(top[6:])
            else:
                stack.append(top[5:])
    return 'NO'

print(solve(input()))
### BUGGY CODE ###

n=int(input())
s=input()
ans=0
for i in range(1000,2000):
    templ=list(str(i))
    t=templ[1:]
    #print(t)
    p=0
    for q in range(n):
        if s[q]==t[p]:
            p+=1
        if p>2:
            ans+=1
            break         

print(ans)


### FIXED CODE ###

n=int(input())
s=input()
ans=0
for i in range(1000,2000):
    templ=list(str(i))
    t=templ[1:]
    #print(t)
    p=0
    for q in range(n):
        if s[q]==t[p]:
            p+=1
        if p>2:
            ans+=1
            break         

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

import math
n = int(input())
L = list(map(int,input().split()))
L.sort()
c = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        lg = L[i] + L[j]
        st = L[j] - L[i]

        BL = j + 1
        BH = n - 1

        if L[BL] >= lg or L[BH] <= st:
            continue

        if L[BH] < lg:
            m1 = BH
        else:
            m1 = math.ceil((BL + BH) / 2)
            while True:
                if L[m1] >= lg:
                    BH = m1 - 1
                else:
                    BL = m1
                if BH <= BL:
                    m1 = BH
                    break
                m1 = math.ceil((BH + BL)/2)

        BL = j + 1
        BH = n - 1
        if L[BL] > st:
            m2 = BL
        else:
            m2 = (BL + BH) // 2
            while True:
                if L[m2] <= st:
                    BL = m2 + 1
                else:
                    BH = m2
                if BH <= BL:
                    m2 = BL
                    break
                m2 = (BH + BL) // 2

        c += max(0,m1-m2+1)


print (c)

### FIXED CODE ###

import math
from bisect import bisect_right
from bisect import bisect_left

n = int(input())
L = list(map(int,input().split()))
L.sort()
c = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        lg = L[i] + L[j]
        st = L[j] - L[i]
        if lg > L[j+1] and st < L[n-1]:
            if lg > L[n-1]:
                m1 = n - (j+1)
            else:
                m1 = bisect_left(L[j+1:],lg)
            c += max(0,m1)
print (c)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)
def list_euclid(int_list):
    ans = int_list[0]
    for i in range(1,len(int_list)):
        ans = euclid(ans, int_list[i])
        if ans == 1:
            return ans
    return ans
n = int(input())
a = list(map(int, input().split()))
a.sort()
max = 0
b_int = 0
if n < 5:
  for i in range(0,n):
    if b_int == a[0]:
      p = a.pop(0)
      a.append(p)
    else:
      p = a.pop(0)
      b_int = p
      x = list_euclid(a)
      if max < x:
        max = x
      a.append(p)
else:
  for i in range(0,n):
    if b_int == a[0]:
      p = a.pop(0)
      a.append(p)
    else:
      p = a.pop(0)
      b_int = p
      k = len(a) // 2
      x = 0
      y = list_euclid(a[0:k])
      if y == 1:
        x = 1
      else:
        z = list_euclid(a[k:n-1])
        x = euclid(y, z)
      if max < x:
        max = x
      a.append(p)
print(max)

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
import sys
def gcd(a, b): #最大公約数
  while b:
    a, b = b, a % b
  return int(a)
    
n = int(input())
a = list(map(int, input().split()))
if n==2:
  print(max(a))
  sys.exit(0)
elif n==3:
  lis = [gcd(a[0], a[1]), gcd(a[1], a[2]), gcd(a[2], a[0])]
  print(max(lis))
  sys.exit(0)
tmp_unused = gcd(a[0], a[1])
tmp_used = max(a[0], a[1])
#print("used=", tmp_used, "unused=", tmp_unused)
for i in range(2,n):
  #print(a[i])
  tmp_used = max(tmp_unused, gcd(tmp_used, a[i]))
  tmp_unused = gcd(tmp_unused, a[i])
  
  #print("used=", tmp_used, "unused=", tmp_unused)
print(tmp_used)
### BUGGY CODE ###

a,b,c=map(int,input().split())
moda=a%b
keep=0
for i in range(0,10**8):
  if (moda*i)%b==c:
    keep=1
    print("YES")
    break
if keep==0:
  print("No")

### FIXED CODE ###

a,b,c=map(int,input().split())
moda=a%b
keep=0
for i in range(1,10**6):
  if (moda*i)%b==c:
    keep=1
    print("YES")
    break
if keep==0:
  print("NO")
### BUGGY CODE ###

N,M=map(int,input().split())
num=[int(x) for x in input().split()]
s=[list(map(int,input().split())) for y in range(M)]

for a,b in s:
    num+=[b]*a

lst=sorted(num)
ans=sum(lst[-N:])
print(ans)

### FIXED CODE ###

N,M=map(int,input().split())
arr=[int(x) for x in input().split()]
s=[list(map(int,input().split())) for y in range(M)]
s.sort(key=lambda z: z[1], reverse=True)

sum_a=0
for a,b in s:
    arr+=[b]*a
    sum_a+=a
    if sum_a>=N:
        break

lst=sorted(arr)
ans=sum(lst[-N:])
print(ans)
### BUGGY CODE ###

from collections import deque
def solve():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1

    ans = [0] * N
    
    for start_vertex in range(N):
        q = deque()
        distance_list = [float('inf')] * N
        def push(vertex, distance):
            if distance_list[vertex] != float('inf'):
                return
            distance_list[vertex] = distance
            q.append(vertex)
        
        push(start_vertex, 0)
        while len(q) > 0:
            vertex = q.popleft()
            distance = distance_list[vertex]

            if vertex - 1 >= 0:
                push(vertex-1,distance+1)
            if vertex + 1 < N:
                push(vertex+1,distance+1)
            if vertex == X:
                push(Y,distance+1)
            if vertex == Y:
                push(X,distance+1)
        for d in distance_list:
            ans[d] += 1
    
    ans = list(map(lambda x: x // 2, ans))
    print(*ans[1:], sep='\n')
        

if __name__ == '__main__':
    solve()

### FIXED CODE ###

from collections import defaultdict, deque
def solve():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1
    cnter = defaultdict(int)

    for i in range(N):
        for j in range(i,N):
            n_step = min(abs(j-i), abs(X-i)+1+abs(Y-j), abs(Y-i)+1+abs(j-X))
            cnter[n_step] += 1
    
    for i in range(1,N):
        print(cnter[i])


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

import numpy as np

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

a=np.array(input().split(),dtype=np.int64)
f=np.array(input().split(),dtype=np.int64)
a.sort()
f.sort()
f=f[::-1]
af=a*f

# r以下にするのに必要修行回数がk以内かどうか
def safe(r):
    return sum(np.maximum(0,af-r+f-1)//f)<=k
    
m=-1
M=10**12

while True:
    pos=(m+M)//2
    if safe(pos):
        M=pos
    else:
        if m==pos:#終わり
            print(M)
            break
        m=pos



### FIXED CODE ###

import numpy as np

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

a=np.array(input().split(),dtype=np.int64)
f=np.array(input().split(),dtype=np.int64)

a.sort()
f.sort()
f=f[::-1]
af=a*f

# r以下にするのに必要修行回数がk以内かどうか
def safe(r):
    return (np.maximum(0,(af-r+f-1)//f)).sum()<=k
    
m=-1
M=10**12

while m+1<M:
    pos=(m+M)//2
    if safe(pos):
        M=pos
    else:
        m=pos
print(M)
### BUGGY CODE ###

N, K = map(int, input().split())
K = min(K, N)
h = list(map(int, input().split()))
cost = [abs(h[i] - h[0]) for i in range(K)]

for i in range(K, N):
#  print(i, cost)
  cost = cost[1:] + [min([cost[j] + abs(h[i]-h[i-K+j]) for j in range(K)])]

print(cost[-1])

### FIXED CODE ###

N, K = map(int, input().split())
K = min(K, N)
h = list(map(int, input().split()))
cost = [abs(h[i] - h[0]) for i in range(K)]

for i in range(K, N):
#  print(i, cost)
  cost = cost[1:] + [min([cost[j] + abs(h[i]-h[i-K+j]) for j in range(K)])]

print(cost[-1])
### BUGGY CODE ###

import itertools

mod = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
ans = 0
arr = list(itertools.combinations(a, 2))
for i, j in arr:
    ans += i * j
print(ans % mod)


### FIXED CODE ###

mod = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
dp = [0]

def calc(A, n, dp):
    dp += [A[0] * A[1]]
    rsum = A[0] + A[1]
    for i in range(2, n):
        dp += [dp[-1] + rsum * A[i]]
        rsum += A[i]

    i = dp.index(max(dp))
    rsum = 0
    for j in range(i + 1):
        rsum += A[j]
    res = max(dp)
    dp2 = max(dp)
    for j in range(0, i):
        rsum -= A[j]
        dp2 -= A[j] * rsum
        res = max(dp2, res)
    return res

ans = calc(a, n, dp) % mod
print(ans)
### BUGGY CODE ###

n,m = map(int, input().split())
s = {_ for _ in range(1,n+1)}
for i in range(m):
  l,r = map(int, input().split())
  s &= {_ for _ in range(l,r+1)}
print(len(s))

### FIXED CODE ###

n,m = map(int, input().split())
left = set()
right = set()
for i in range(m):
  l,r = map(int, input().split())
  left.add(l)
  right.add(r)
mini = max(left)
maxi = min(right)
print(len(range(mini,maxi+1)))
### BUGGY CODE ###

from itertools import product
n,c = map(int,input().split())
cost = [list(map(int,input().split())) for i in range(c)]
grid = [list(map(int,input().split())) for i in range(n)]
sum0 = []
sum1 = []
sum2 = []
for color in range(c):
  s0,s1,s2 = 0,0,0
  for i in range(n):
    for j in range(n):
      x = grid[i][j]-1
      if (i+j)%3 == 0:
        s0 += cost[x][color]
      elif (i+j)%3 == 1:
        s1 += cost[x][color]
      else:
        s2 += cost[x][color]
  sum0.append((s0,color))
  sum1.append((s1,color))
  sum2.append((s2,color))
ans = 10**18
for a,b,c in product(sum0,sum1,sum2):
  if a[1] != b[1] and b[1] != c[1] and c[1] != a[1]:
    ans = min(ans,a[0]+b[0]+c[0])
print(ans)

### FIXED CODE ###

from itertools import product
n,c = map(int,input().split())
cost = [list(map(int,input().split())) for i in range(c)]
grid = [list(map(int,input().split())) for i in range(n)]
sum0 = []
sum1 = []
sum2 = []
for color in range(c):
  s0,s1,s2 = 0,0,0
  for i in range(n):
    for j in range(n):
      x = grid[i][j]-1
      if (i+j)%3 == 0:
        s0 += cost[x][color]
      elif (i+j)%3 == 1:
        s1 += cost[x][color]
      else:
        s2 += cost[x][color]
  sum0.append((s0,color))
  sum1.append((s1,color))
  sum2.append((s2,color))
ans = 10**18
for a,b,c in product(sum0,sum1,sum2):
  if a[1] != b[1] and b[1] != c[1] and c[1] != a[1]:
    ans = min(ans,a[0]+b[0]+c[0])
print(ans)
### BUGGY CODE ###

import collections
import math

n = int(input())
a_lst = [int(elem) for elem in input().split()]

for i in range(n):
  res = 0
  lst = a_lst[:i]+a_lst[i+1:]
  c = collections.Counter(lst)
  for k in c.keys():
    if c[k] > 1:
      res += math.factorial(c[k]) // (math.factorial(c[k] - 2) * math.factorial(2))
  print(res)

### FIXED CODE ###

import collections

n = int(input())
a_lst = [int(elem) for elem in input().split()]
c = collections.Counter(a_lst)
res1 = 0
for k in c.keys():
  res1 += c[k] * (c[k] - 1) // 2

for i in range(n):
  res = res1
  res -= c[a_lst[i]] - 1
  print(res)
### BUGGY CODE ###

def main():
    n = int(input())
    d = dict()
    for a in list(map(int, input().split())):
        d[a] = d.get(a, 0) + 1

    for _ in range(int(input())):
        b, c = map(int, input().split())
        if d.get(b, 0) != 0:
            temp = d[b]
            d[b] -= temp
            d[c] = d.get(c, 0) + temp

        print(sum(k*v for k, v in d.items()))

main()

### FIXED CODE ###

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

    sum_a = sum(A)

    d = dict()

    for a in A:
        d[a] = d.get(a, 0) + 1

    for _ in range(int(input())):
        b, c = map(int, input().split())
        if d.get(b, 0) != 0:

            temp = d[b]         
            d[b] -= temp
            d[c] = d.get(c, 0) + temp

            sum_a += (c - b) * temp
        print(sum_a)
        
main()
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
*A, = map(int, input().split())
*B, = map(int, input().split())
*C, = map(int, input().split())

S = []
for a in A:
    for b in B:
        S.append(a+b)
S.sort()
C.sort()
T = C

L = X*Y

left = 3; right = max(A)+max(B)+max(C)+1
while left+1 < right:
    mid = (left + right) >> 1
    cur = L
    cnt = 0
    for c in C:
        while cur > 0 and S[cur-1]+c > mid:
            cur -= 1
        cnt += L - cur
    if cnt < K:
        right = mid
    else:
        left = mid
ans = []
for c in C:
    cur = L
    while cur > 0 and S[cur-1]+c >= right:
        v = S[cur-1]+c
        ans.append(v)
        cur -= 1
ans.sort(reverse=1)
while len(ans) < K:
    ans.append(left)
print(*ans[:K], sep='\n')

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
*A, = map(int, input().split())
*B, = map(int, input().split())
*C, = map(int, input().split())

S = []
for a in A:
    for b in B:
        S.append(a+b)
S.sort()
C.sort()
T = C

L = X*Y

left = 3; right = max(A)+max(B)+max(C)+1
while left+1 < right:
    mid = (left + right) >> 1
    cur = L
    cnt = 0
    for c in C:
        while cur > 0 and S[cur-1]+c > mid:
            cur -= 1
        cnt += L - cur
    if cnt < K:
        right = mid
    else:
        left = mid
ans = []
for c in C:
    cur = L
    while cur > 0 and S[cur-1]+c >= left:
        v = S[cur-1]+c
        if v == left and len(ans) >= K:
            break
        ans.append(v)
        cur -= 1
ans.sort(reverse=1)
print(*ans[:K], sep='\n')
### BUGGY CODE ###

def solve():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    indices = {}
    for i in range(n):
        indices[a[i]] = i
    b = sorted(a)
    for j in range(n - 1, -1, -1):
        i = indices[b[j]]
        while i + 2 < n and a[i] > a[i + 2]:
            tmp = a[i + 2]
            a[i + 2] = a[i]
            a[i] = tmp
            indices[a[i]] = i
            indices[a[i + 2]] = i + 2
            i += 2
    ans = 0
    for i in range(n - 1):
        if a[i] != b[i]:
            ans += 1
            tmp = a[i + 1]
            a[i + 1] = a[i]
            a[i] = tmp
    print(ans)


def main():
    solve()


if __name__ == '__main__':
    main()


### FIXED CODE ###

def solve():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    e = [a[i] for i in range(0, n, 2)]
    a.sort()
    o = set(a[i] for i in range(1, n, 2))
    ans = 0
    for i in range((n + 1) // 2):
        if e[i] in o:
            ans += 1
    print(ans)


def main():
    solve()


if __name__ == '__main__':
    main()