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

def main():
    import sys

    input = sys.stdin.readline

    x, y, z, k = map(int, input().split())
    A = sorted(map(int, input().split()), reverse=True)
    B = sorted(map(int, input().split()), reverse=True)
    C = sorted(map(int, input().split()), reverse=True)

    def is_ok(p: int):
        cnt = 0
        for a in A:
            for b in B:
                for c in C:
                    if a + b + c < p:
                        break
                    cnt += 1
                    if cnt >= k:
                        return True
        return False

    def binary_search():
        ng = 10 ** 10 + 10
        ok = 0
        while abs(ng - ok) > 1:
            mid = (ng + ok) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok

    def logger(p: int):
        ret = []
        for a in A:
            for b in B:
                for c in C:
                    if a + b + c < p:
                        break
                    ret.append(a + b + c)
        return ret

    p = binary_search()  # k個以上のボーダー
    ret = logger(p + 1)
    if len(ret) < k:
        ret.extend([p] * (k - len(ret)))
    ret.sort(reverse=True)
    print(*ret[:k], sep='\n')


main()

# O(K^2logmax)
# https://img.atcoder.jp/abc123/editorial.pdf


### FIXED CODE ###

# https://www.kumilog.net/entry/python-speed-comp#input-%E3%81%A8-sysstdinreadline
# https://teratail.com/questions/88396

from heapq import heapify, heappush, heappop
import sys

input = sys.stdin.readline


class Data:
    def __init__(self, value, indices):
        self.value = value
        self.indices = indices

    def __lt__(self, other):
        return self.value < other.value


X, Y, Z, K = map(int, input().split())
a = map(int, input().split())
b = map(int, input().split())
c = map(int, input().split())

a = list(sorted(a, reverse=True))
b = list(sorted(b, reverse=True))
c = list(sorted(c, reverse=True))

hq = []
heapify(hq)

t = a[0] + b[0] + c[0]
t *= -1

d = Data(t, (0, 0, 0))

heappush(hq, d)

dtpls = ((1, 0, 0), (0, 1, 0), (0, 0, 1))

st = set()

cnt = 0
for _ in range(K):
    d = heappop(hq)
    print(-d.value)
    for dtpl in dtpls:
        na = d.indices[0] + dtpl[0]
        if na >= X: continue
        nb = d.indices[1] + dtpl[1]
        if nb >= Y: continue
        nc = d.indices[2] + dtpl[2]
        if nc >= Z: continue

        nt = a[na] + b[nb] + c[nc]
        nt *= - 1

        ntpl = (na, nb, nc)
        if ntpl in st: continue
        heappush(hq, Data(nt, ntpl))
        st.add(ntpl)
### BUGGY CODE ###

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

come = [a.index(i)+1 for i in range(1,N+1)]
print(*come)

### FIXED CODE ###

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

bef = [0 for i in range(N)]
for i in range(N):
  bef[a[i]-1] = i+1
print(*bef)
### BUGGY CODE ###

N = int(input())
P = tuple(map(int, input().split()))
cnt = N
for a in P:
    for b in P[:P.index(a)+1]:
        if a > b:
            cnt -= 1
            break
print(cnt)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
cnt = 0
max = 2*10**5
for a in P:
    if a <=max:
        #print(a)
        cnt += 1
    max = min(max,a)
print(cnt)
### BUGGY CODE ###

S=input()
N=len(S)
Slis=[]
for i in range(N):
  Slis+=[int(S[i])]
T=[0 for i in range(N+1)]#T[i]はi桁より右側の数字


def kaizyou(n):
  c=1
  for p in range(n):
    c=(c*10)%2019
  return c


for i in range(N):
  T[N-i-1]=(T[N-i]+kaizyou(i)*Slis[N-i-1])%2019

MOD=[0 for i in range(2019)]
for i in range(N+1):
  tmp=T[i]%2019
  MOD[tmp]+=1


  
ans=0

for i in range(2019):
  tmp=MOD[i]
  ans+=tmp*(tmp-1)//2
print(ans)

### FIXED CODE ###

S=input()
N=len(S)
Slis=[]
for i in range(N):
  Slis+=[int(S[i])]
T=[0 for i in range(N+1)]#T[i]はi桁より右側の数字


ten=1

for i in range(N):
  T[N-i-1]=(T[N-i]+ten*Slis[N-i-1])%2019
  ten=(ten*10)%2019

MOD=[0 for i in range(2019)]
for i in range(N+1):
  tmp=T[i]%2019
  MOD[tmp]+=1


  
ans=0

for i in range(2019):
  tmp=MOD[i]
  ans+=tmp*(tmp-1)//2
print(ans)
### BUGGY CODE ###

import queue
import copy

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

def movable(S,px,py):
    if  0 <= px and px < H and 0 <= py and py < W:
        if S[px][py] == ".":
            return True
        else:
            return False
    else:
        return False

def bfs(S,sx,sy):
    S_dist = [[0 for _ in range(W)] for _ in range(H)]
    q = queue.Queue()
    q.put((sx,sy))
    vec = [(0,1),(0,-1),(1,0),(-1,0)]
    write = set([])
    #deepcopyしたやつを使うと遅いので上書きしたやつを戻して再利用
    while not q.empty():
        p = q.get()
        S[p[0]][p[1]] = "#"
        write.add((p[0],p[1]))
        ret = S_dist[p[0]][p[1]]
        for vx,vy in vec:
            if movable(S,p[0]+vx,p[1]+vy):
                S_dist[p[0]+vx][p[1]+vy] = S_dist[p[0]][p[1]]+1
                q.put((p[0]+vx,p[1]+vy))
    for wx,wy in write:
        S[wx][wy] = "."
    return ret

ans = 0
for i in range(H*W):
    if S[i//W][i%W] == ".":
        ans = max(ans,bfs(S,i//W,i%W))
print(ans)


### FIXED CODE ###

import queue
import copy

H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
INF = H*W+1

def movable(S,S_dist,px,py):
    if  0 <= px and px < H and 0 <= py and py < W:
        if S_dist[px][py] == INF and S[px][py] == ".":
            return True
    return False

def bfs(S,sx,sy):
    S_dist = [[INF for _ in range(W)] for _ in range(H)]
    #Sを直接いじれば訪問済みかどうか管理できるがそれだと毎回Sをリセットする必要がある
    #S_distのみ書き込みにすればS_distはローカルだからリセットが不要
    S_dist[sx][sy] = 0
    q = queue.Queue()
    q.put((sx,sy))
    vec = [(0,1),(0,-1),(1,0),(-1,0)]
    ret = 0
    while not q.empty():
        p = q.get()
        ret = S_dist[p[0]][p[1]]
        for vx,vy in vec:
            if movable(S,S_dist,p[0]+vx,p[1]+vy):
                S_dist[p[0]+vx][p[1]+vy] = S_dist[p[0]][p[1]]+1
                q.put((p[0]+vx,p[1]+vy))
    return ret

ans = 0
for i in range(H*W):
    if S[i//W][i%W] == ".":
        ans = max(ans,bfs(S,i//W,i%W))
print(ans)
### BUGGY CODE ###

from sys import exit
import copy
# import numpy as np
from collections import deque

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

cnt = 0


a.insert(0, 0)
b.insert(0, 0)


for i in range(1, n+1):
    a[i] += a[i-1]

for i in range(1, m+1):
    b[i] += b[i-1]


for i in range(n+1):
    for j in range(m+1):
        if a[i] + b[j] <= k:
            pass
        else:
            if a[i] + b[j-1] <= k:
                cnt = max(cnt, i + j - 1)
            break
    else:
        if a[i] + b[j] <= k:
            cnt = max(cnt, i + j)
print(cnt)


### FIXED CODE ###

from sys import exit
import copy
# import numpy as np
from collections import deque

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

cnt = 0


a.insert(0, 0)
b.insert(0, 0)


for i in range(1, n+1):
    a[i] += a[i-1]

for i in range(1, m+1):
    b[i] += b[i-1]

tmp = m
for i in range(n+1):
    for j in range(tmp, -1, -1):
        if a[i] + b[j] <= k:
            cnt = max(cnt, i + j)
            tmp = j
            break


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

import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
res = 0
for i in range(N-2):
    idx = (N-1) - i
    max_, second_max = L[idx], L[idx-1]
    for tmp_idx in range(1, idx):
        second_max = L[tmp_idx]
        tidx = bisect.bisect_right(L, max_ - second_max)
        if len(L[tidx:tmp_idx]) > 0:
            res += len(L[tidx:tmp_idx])
print(res)



### FIXED CODE ###

from bisect import bisect_left
N = int(input())
l = list(map(int, input().split()))
l.sort()
res = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        t = l[i] + l[j]
        idx = bisect_left(l, t)
        res += idx-j-1
print(res)
### BUGGY CODE ###

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

ans_list = []
for r in range(1, n+1, 1):
    index = num_list.index(r)+1
    ans_list.append(str(index))

ans = ' '.join(ans_list)
print(ans)

### FIXED CODE ###

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

ans_list = [0]*n
for i, j in enumerate(num_list):
    ans_list[j-1] = str(i+1)

ans = ' '.join(ans_list)
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
h = [int(i) for i in input().split()]

dp = [float('inf')]*N
dp[0] = 0

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

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(i) for i in input().split()]

dp = [float('inf')]*N
dp[0] = 0

for i in range(N):
    for j in range(1, K+1):
        if i+j < N:
            dp[i+j] = min(dp[i+j], dp[i] + abs(h[i]-h[i+j]))
print(dp[N-1])
### BUGGY CODE ###

m, n, k = map(int, input().split())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))

def check_(lis, num, ti):
    ans = 0
    for i in range(num+1):
        if ans >= ti:
            break
        ans +=  lis[i]
    return i

max_a = check_(a, m, k)
max_b = check_(b, n, k)
ans = 0
for i in range(max_a+1):
    for j in range(max_b+1):
        if sum(a[:i+1]) + sum(b[:j+1]) <= k and i + j > ans:
            ans = i+j 
print(ans)

### FIXED CODE ###

n, m, k = map(int, input().split())
A = [0] + list(map(int,input().split()))
B = [0] + list(map(int,input().split()))
 
for i in range(2,n+1):
    A[i] += A[i-1]
for i in range(2,m+1):
    B[i] += B[i-1]

j = m
ans = 0
for i in range(n+1):
    if A[i] > k:
        break 
    while B[j] > k-A[i]:
        j -= 1
    ans = max(ans, i+j)
print(ans)
### BUGGY CODE ###

N, C = list(map(int, input().split()))
tmax = 0
s = [0 for _ in range(N)]
t = [0 for _ in range(N)]
c = [0 for _ in range(N)]
for i in range(N):
    s[i], t[i], c[i] = list(map(int, input().split()))

tmax = max(t)
c_timeline = [[0]*C for _ in range(2 * tmax + 1)]
for i in range(N):
    S = s[i]
    T = t[i]
    channel = c[i] - 1
    for j in range(2 * S - 1, 2 * T + 1):
        c_timeline[j][channel] = 1

time = [0 for _ in range(2*tmax+1)]
for i, timeline in enumerate(c_timeline):
    time[i] = sum(timeline)

print(max(time))


### FIXED CODE ###

N, C = list(map(int, input().split()))
tmax = 0
s = [0 for _ in range(N)]
t = [0 for _ in range(N)]
c = [0 for _ in range(N)]
for i in range(N):
    s[i], t[i], c[i] = list(map(int, input().split()))

tmax = max(t)
c_timeline = [[0]*C for _ in range(2 * tmax + 1)]
for i in range(N):
    S = s[i]
    T = t[i]
    channel = c[i] - 1
    for j in range(2 * S - 1, 2 * T + 1):
        c_timeline[j][channel] = 1

rokuga = 0
for timeline in c_timeline:
    time = sum(timeline)
    if rokuga < time:
        rokuga = time

print(rokuga)
### BUGGY CODE ###

import operator as op
from functools import reduce

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

ans = 0
combi_lis = []
multi = op.mul
numer = reduce(multi, range(1, K+1), 1)
denom = reduce(multi, range(1, K+1), 1)

#max
for i in range(K-1, N):
  combi = numer//denom
  combi_lis.append(combi)
  ans += num_lis[i]*combi
  numer *= i+1
  numer = numer//(i-K+2)

#min
k = 0
for j in range(N-K,-1,-1):
  ans -= num_lis[j]*combi_lis[k]
  k += 1

ans %= 10**9+7
print(ans)

### FIXED CODE ###

# フェルマーの小定理
N, K = map(int, input().split())
A = list(map(int, input().split()))
 
m = 1000000007
 
fac = [0] * (N + 1)
fac[0] = 1
for i in range(N):
    fac[i + 1] = fac[i] * (i + 1) % m
 
 
def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], m - 2, m) * pow(fac[k], m - 2, m) % m
 
 
A.sort(reverse=True)
maxX = 0
for i in range(N - K + 1):
    maxX += A[i] * mcomb(N - (i + 1), K - 1)
    maxX %= m

A.sort()
minX = 0
for i in range(N - K + 1):
    minX += A[i] * mcomb(N - (i + 1), K - 1)
    minX %= m

print((maxX - minX) % m)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

def main():
  N, M = map(int, readline().split())
  dist = {}
  pre = {}
  A = {}
  for i in range(N):
    dist[i+1] = -1
    pre[i+1] = -1
    A[i+1] = []
  dist[1] = 0
  pre[1] = 0
  for i in range(M):
    ai, bi = map(int, readline().split())
    if bi not in A[ai]:
      A[ai].append(bi)
    if ai not in A[bi]:
      A[bi].append(ai)
  cnt = 1
  depth = 1
  D = [1]
  while cnt < N:
    next = []
    for i in range(len(D)):
      for j in range(len(A[D[i]])):
        if dist[A[D[i]][j]] == -1:
          dist[A[D[i]][j]] = depth
          pre[A[D[i]][j]] = D[i]
          next.append(A[D[i]][j])
          cnt += 1
    D = next
    depth += 1
    if len(next) == 0:
      break
    elif depth > N:
      break
  if cnt == N:
    print('Yes')
    for i in range(1, N):
      print(pre[i+1])
  else:
    print('No')

if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline

def main():
  N, M = map(int, readline().split())
  dist = {}
  pre = {}
  A = {}
  for i in range(N):
    dist[i+1] = -1
    pre[i+1] = -1
    A[i+1] = []
  dist[1] = 0
  pre[1] = 0
  for i in range(M):
    ai, bi = map(int, readline().split())
    A[ai].append(bi)
    A[bi].append(ai)
  cnt = 1
  depth = 1
  D = [1]
  while cnt < N:
    next = []
    for i in range(len(D)):
      for j in range(len(A[D[i]])):
        if dist[A[D[i]][j]] == -1:
          dist[A[D[i]][j]] = depth
          pre[A[D[i]][j]] = D[i]
          next.append(A[D[i]][j])
          cnt += 1
    D = next
    depth += 1
    if len(next) == 0:
      break
    elif depth > N:
      break
  if cnt == N:
    print('Yes')
    for i in range(1, N):
      print(pre[i+1])
  else:
    print('No')

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

n = int(input())
b = {}
for i in range(n):
    temp = input()
    if temp not in b:
        b[temp] = 1
    else:
        b[temp] += 1

list1 = sorted(b.items(), key=lambda x: x[1])
list1.reverse()

a = 0
list2=[]
while a<len(list1) and list1[0][1] == list1[a][1]:
    list2.append(list1[a][0])
    list2.sort()
    a += 1

for a in list2:
    print(a)


### FIXED CODE ###

n = int(input())
b = {}
for i in range(n):
    temp = input()
    if temp not in b:
        b[temp] = 1
    else:
        b[temp] += 1

list1 = sorted(b.items(), key=lambda x: x[1])

a = len(list1)-1
temp = len(list1)-1
list2 = []
while a >= 0 and list1[temp][1] == list1[a][1]:
    list2.append(list1[a][0])
    a -= 1
list2.sort()

for a in list2:
    print(a)
### BUGGY CODE ###

import collections
N, P = map(int, input().split())
S = [int(_) for _ in list(input())]
if P == 2 or P == 5:
    ans = 0
    for n in range(N):
        if S[n] % P == 0:
            ans += n + 1
    print(ans)
else:
    S = [(S[n] * 10**(N - n - 1)) % P for n in range(N)]
    T = [0]
    for n in range(N)[::-1]:
        T.append((T[-1] + S[n]) % P)
    T.reverse()
    lst = [0] * P
    ans = 0
    for t in T:
        ans += lst[t]
        lst[t] += 1
    print(ans)


### FIXED CODE ###

N, P = map(int, input().split())
S = [int(_) for _ in list(input())]
if P == 2 or P == 5:
    ans = 0
    for n in range(N):
        if S[n] % P == 0:
            ans += n + 1
    print(ans)
else:
    S = [(S[n] * pow(10, N - n - 1, P)) % P for n in range(N)]
    S.reverse()
    T = [0]
    for s in S:
        T.append((T[-1] + s) % P)
    lst = {i: 0 for i in range(P)}
    ans = 0
    for t in T:
        ans += lst[t]
        lst[t] += 1
    print(ans)
### BUGGY CODE ###

n,x,y = map(int,input().split())
ans = [0]*(n-1)
for i in range(n-1):
    for j in range(i+1,n):
        dis = min(j-i, abs(j-(x-1))+1+abs((y-1)-i), abs(j-(y-1))+1+abs((x-1)-i))
        ans[dis-1] += 1
for i in range(n-1):
    print(ans[i])

### FIXED CODE ###

n,x,y = map(int,input().split())
ans = [0]*(n-1)
for i in range(1,n):
    for j in range(i+1,n+1):
        dis = min(j-i, abs(j-x)+1+abs(y-i), abs(j-y)+1+abs(x-i))
        ans[dis-1] += 1
for i in range(n-1):
    print(ans[i])
### BUGGY CODE ###

a,b,x=map(int,input().split())
ans=0
for i in range(a,b+1):
    if i%x==0:
        ans+=1
print(ans)

### FIXED CODE ###

import math
a,b,x=map(int,input().split())
if a%x>0 and b//x-a//x==0:
    print(0)
else:
    print((b//x)-math.ceil(a/x)+1)
### BUGGY CODE ###

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

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

dp = [0 for i in range(N)]
if N >= K :    
    for i in range(1,K+1) :
        dp[i] = abs(L[i]-L[0])
    for i in range(K+1,len(dp)) :
        state = float("inf")
        for j in range(i-K,i) :
            calc = abs(L[i]-L[j]) + dp[j]
            if state > calc :
                state = calc
        dp[i] = state
    print(dp[N-1])
else :
    print(abs(min(L[1:])-L[0]))


### FIXED CODE ###

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

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

dp = [0 for i in range(N)]
if N >= K :    
    for i in range(1,K+1) :
        dp[i] = abs(L[i]-L[0])
    for i in range(K+1,len(dp)) :
        state = float("inf")
        for j in range(i-K,i) :
            calc = abs(L[i]-L[j]) + dp[j]
            if state > calc :
                state = calc
        dp[i] = state
    print(dp[N-1])
else :
    print(abs(min(L[1:])-L[0]))
### BUGGY CODE ###

import itertools, functools, math, sys

def prime_stream():
    stream = itertools.count(2)
    sieve = lambda x, y: x % y != 0

    while True:
        prime = next(stream)
        stream = filter(functools.partial(sieve, y=prime), stream)
        yield prime

for line in sys.stdin:
    primes = prime_stream()
    num = int(line)
    count = 0
    for i in range(num):
        if next(primes) > num:
            break
        count += 1
    print(count)

### FIXED CODE ###

import sys

def prime(maximum):
    sieve = [True] * (maximum + 1)

    def sieved(prime):
        for not_prime in range(prime + prime, len(sieve), prime):
            sieve[not_prime] = False

    sieve[0] = sieve[1] = False
    sieved(2)
    for x in range(3, int(maximum ** 0.5) + 1, 2):
        if sieve[x]: sieved(x)
    return [prime for prime, is_prime in enumerate(sieve) if is_prime]

count = 0
numbers = []
for line in sys.stdin:
    numbers.append(int(line))
    count += 1

counts = []
for i in range(count):
    counts.append(0)

for prime in prime(1000000):
    if prime > 999999:
        break
    for i in range(count):
        if prime <= numbers[i]:
            counts[i] += 1

for count in counts:
    print(count)
### BUGGY CODE ###

a, b, c, d = map(int,input().split())

ans = 0

for i in range(a, b+1):
  if i % c != 0 and i % d != 0:
    ans += 1

print(ans)

### FIXED CODE ###

a, b, c, d = map(int, input().split())

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

def f(b, c, d):
  return b - ((b // c) + (b // d)) + b // ((c * d) // gcd(c,d))

print(f(b, c, d) - f(a-1, c, d))
### BUGGY CODE ###

N, M = [int(x) for x in input().split(' ')]

P = {}
for i in range(M):
  l,r = [int(x) for x in input().split(' ')]
  for s in range(l,r+1):
    if s not in P:
      P[s] = 0
    P[s] += 1
    #print(s)
    
cnt = 0
for k,v in P.items():
  if v == M:
    cnt += 1
print(cnt)

### FIXED CODE ###

N, M = [int(x) for x in input().split(' ')]

L = 0
R = N
for i in range(M):
  l,r = [int(x) for x in input().split(' ')]
  if L < l:
    L = l
  if r < R:
    R = r

cnt = 0
if L <= R:
  cnt = R - L + 1
print(cnt)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = [0]*n
for i in range(1,n+1):
  for j in range(n):
    if a[j] == i:
      b[i-1] = j+1
for k in range(n):
  print(b[k],end = " ")

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = [0]*n
for i in range(1,n+1):
  ans[a[i-1]-1] = i
[print(ans[i],end=" ") for i in range(n)]
### BUGGY CODE ###

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

def func(c,result):
    num = max(array[0:c])
    idx = array.index(num)
    result += (-sum(array[idx:c]) + (num*(c-idx)))
    if idx == 0:
        print(result)
        return
    func(idx,result)
    
res = func(N,0)

### FIXED CODE ###

N = int(input())
array = list(map(int,input().split()))
new_array = array
t = sum(array)

for i in range(N-1):
    if array[i] > array[i+1]:
        array[i+1] = array[i]
print(sum(array) - t)
### BUGGY CODE ###

import bisect
import numpy as np
N,M = (int(x) for x in input().split())
A = list(map(int, input().split()))
A.sort()
while M > 0:
    if A[N-1] >= A[N-2]:
        A[N-1] = A[N-1] / 2
        M -= 1
    else:
        temp = A[N-1]
        bisect.insort_left(A,temp)
        del A[-1]
B = np.floor(A)
print(int(np.sum(B)))

### FIXED CODE ###

import heapq
from numpy import ceil,sum
N,M = (int(x) for x in input().split())
A = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(A)
for i in range(M):
    t1 = heapq.heappop(A)
    t2 = t1 / 2
    heapq.heappush(A, t2)
B = ceil(A)
print(int(sum(B)*(-1)))
### BUGGY CODE ###

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

da = [[] for i in range(a)]
d = []
for i in range(b):
    k,kk = map(int,input().split())
    da[k-1].append(kk)
    d.append([k, kk])

for i in range(a):
    da[i].sort()

for i in range(b):
    p = da[d[i][0]-1].index(d[i][1])

    n = str((d[i][0]))
    m = str(p+1)

    for j in range(6-len(n)):
        n = "0" + n
    for j in range(6-len(m)):
        m = "0" + m

    print(n+m)


### FIXED CODE ###

import sys
input = sys.stdin.readline

a,b = map(int,input().split())
aa = []
d = []
for i in range(b):
    k,kk = map(int,input().split())
    d.append([k, kk,i+1])

da = sorted(d)

kkk = da[0][0]
ll = 0
for i in range(b):
    kkkk = da[i][0]
    if kkk == kkkk:
        ll += 1
    else:
        kkk = kkkk
        ll = 1
    aa.append([da[i][2],da[i][0],ll])
aa.sort()

for i in aa:
    m = str(i[1])
    n = str(i[2])
    m = "0"*(6-len(m))+m
    n = "0"*(6-len(n))+n
    print(m+n)
### BUGGY CODE ###

N = int(input())
n = N
B = list(map(int,input().split()))
B = B[::-1]
A = []
flag = 0
while N > 0:
    for m,b in enumerate(B):
        if (N-m == b):
            A.append(b)
            B.pop(m)
            flag = 1
            N -= 1
            break
#print(A)
if len(A) == n:
    for a in A[::-1]:
        print(a)
else:
    print(-1)

### FIXED CODE ###

N = int(input())
n = N
B = list(map(int,input().split()))
B = B[::-1]
A = []
for i in range(N):
    for m,b in enumerate(B):
        if (N-m == b):
            A.append(b)
            B.pop(m)
            N -= 1
            break
if len(A) == n:
    for a in A[::-1]:
        print(a)
else:
    print(-1)
### BUGGY CODE ###

n,m=map(int,input().split())
branch=[tuple(map(int,input().split())) for _ in range(m)]
cango=dict()
res=[0]
data=[0 for _ in range(1+n)]
def calc(k):
    return 1/2*k*(k-1)

def search(data,x):
    if data[x]<=0:
        return x
    else:
        data[x]=search(data,data[x])
    return data[x]

for i in range(m):
    a,b=branch.pop()
    aset={a,}
    bset={b,}
    aroot=search(data,a)
    aidx=data[aroot]
    broot=search(data,b)
    bidx=data[broot]
    if aidx!=0:aset=cango[aidx]
    if bidx!=0:bset=cango[bidx]
    lena=len(aset)
    lenb=len(bset)
    if aidx==0 and bidx==0:
        data[a]=-1*a
        data[b]=a
        cango[-1*a]={a,b}
    elif aidx==bidx and aidx!=0:
        res.append(res[-1])
        continue
    elif aidx==0 and bidx!=0:
        cango[bidx]|={a,}
        data[a]=broot
    elif aidx!=0 and bidx==0:
        cango[aidx]|={b,}
        data[b]=aroot
    elif aidx!=0 and bidx!=0 and aidx!=bidx:
        cango.pop(bidx)
        cango[aidx]|=bset
        data[broot]=aroot
    res.append(res[-1]-calc(lena)-calc(lenb)+calc(lena+lenb))

for j in range(m-1,-1,-1):
    print(int(res[m]-res[j]))

### FIXED CODE ###

n,m=map(int,input().split())
branch=[tuple(map(int,input().split())) for _ in range(m)]
res=[0]
data=[-1 for _ in range(1+n)]
def calc(k):
    k=abs(k)
    return 1/2*k*(k-1)

def search(data,x):
    if data[x]<=0:
        return x
    else:
        data[x]=search(data,data[x])
    return data[x]

for i in range(m):
    a,b=branch.pop()
    aroot=search(data,a)
    broot=search(data,b)
    if aroot==broot:
        res.append(res[-1])
        continue
    res.append(res[-1]-calc(data[aroot])-calc(data[broot])+calc(data[aroot]+data[broot]))
    if data[aroot]<=data[broot]:
        data[aroot]+=data[broot]
        data[broot]=aroot
    elif data[aroot]>data[broot]:
        data[broot]+=data[aroot]
        data[aroot]=broot
for j in range(m-1,-1,-1):
    print(int(res[m]-res[j]))