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

[n,m] = list(map(int,input().split(' ')))
L1 = []
Ln = []
i=0
while i < m:
    l = list(map(int,input().split(' ')))
    if l[0] == 1:
        L1.append(l[1])
    elif l[1] == n:
        Ln.append(l[0])
    i += 1
q=0
for j in L1:
    if j in Ln:
        print("POSSIBLE")
        q = 1
        break
if q == 0:
    print('IMPOSSIBLE')

### FIXED CODE ###

[n,m] = list(map(int,input().split(' ')))
L1 = [0]*n
Ln = [0]*n
i=0
while i < m:
    l0 = list(map(int,input().split(' ')))
    if l0[0] == 1:
        L1[l0[1]] = 1
    elif l0[1] == n:
        Ln[l0[0]] = 1
    i += 1
q = 0
while q < n:
    if L1[q] * Ln[q] == 1:
        print('POSSIBLE')
        q = 0
        break
    else:
        q += 1
if q != 0:
    print('IMPOSSIBLE')
### BUGGY CODE ###

n,m,k=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
a=[sum(A[:i+1]) for i in range(n)]
b=[sum(B[:j+1]) for j in range(m)]
i=n-1
j=m-1
x=0
while i>=0:
  if a[i]>k:
    i-=1
    continue
  while j>=0:
    if b[j]<=k-a[i]:
      break
    j-=1
  x=max(x,i+j+2)
  i-=1
print(x)

### FIXED CODE ###

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

a, b = [0], [0]
for i in range(N):
 a.append(a[i] + A[i])
for i in range(M):
 b.append(b[i] + B[i])

ans, j = 0, M
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 ###

from heapq import heappush, heappop
from math import ceil


def main():
    n, k = map(int, input().split())
    a = [int(i) for i in input().split()]
    c = [1] * n
    h = []
    for i, ai in enumerate(a):
        heappush(h, (-ai, i))
    for _ in range(k):
        ai, i = heappop(h)
        ci = c[i]
        ai = ai * ci / (ci + 1)
        heappush(h, (ai, i))
        c[i] += 1
    print(ceil(-h[0][0]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

from math import ceil


def main():
    n, k = map(int, input().split())
    a = sorted([int(i) for i in input().split()], reverse=True)
    left = 0
    right = a[0]
    while right - left > 1:
        ki = k
        mid = left + (right - left) // 2
        for ai in a:
            if ki < 0:
                left = mid
                break
            if ai <= mid:
                right = mid
                break
            ki -= ceil(ai / mid) - 1
        else:
            if ki < 0:
                left = mid
            else:
                right = mid
    print(right)


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

from functools import reduce, lru_cache


@lru_cache(maxsize=2**14)
def GCD(x, y):
    if y == 0:
        return x
    else:
        return GCD(y, x % y)


def lcm(x, y):
    return (x * y) // GCD(x, y)


def solve():
    MOD = 10 ** 9 + 7
    N, *A = map(int, open(0).read().split())
    
    lcm_num = reduce(lcm, A)
    ans = 0
    for a in A:
        ans += lcm_num // a
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

from fractions import gcd


def solve():
    N, *A = map(int, open(0).read().split())
    MOD = 10 ** 9 + 7

    lcm = 1
    for a in A:
        lcm = a * lcm // gcd(a, lcm)

    ans = [lcm // a for a in A]
    print(sum(ans) % MOD)


if __name__ == '__main__':
    solve()
### 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/l2[i]>=n:
    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 ###

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))

max_A = max(A)
for i in range(N):
    if A[i] != max_A:
        print(max_A)
    else:
        print(sorted(A, reverse=True)[1])

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))

max_A = max(A)
next_A = sorted(A, reverse=True)[1]
for i in range(N):
    if A[i] != max_A:
        print(max_A)
    else:
        print(next_A)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
cnt = 1
for i in A:
    cnt *= i

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

### FIXED CODE ###

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

A.sort()
cnt = 1
for i in A:
    cnt *= i
    if cnt > 10**18:
        print(-1)
        exit()

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

n = int(input())
s = input()
dic = {'R':0,'G':1,'B':2}

lst = []
t_last = (0,0,0)
for i in s[::-1]:
    if i=='R':
        t = (t_last[0]+1, t_last[1], t_last[2])
        lst.append(t)
        t_last = t
    elif i=='G':
        t = (t_last[0], t_last[1]+1, t_last[2])
        lst.append(t)
        t_last = t
    elif i=='B':
        t = (t_last[0], t_last[1], t_last[2]+1)
        lst.append(t)
        t_last = t
lst.reverse()

res = 0
for ni,i in enumerate(s[:-2]):
    lst3 = ['R','G','B']
    lst3.remove(i)
    for nnj,j in enumerate(s[ni+1:-1]):
        if i!=j:
            nj = nnj + ni + 1
            target = [x for x in lst3 if x != j][0]
            res += lst[nj][dic[target]]
            index = nj + (nj-ni)
            if index <= n-1 and s[index] == target:
                res -= 1
print(res)

### FIXED CODE ###

n = int(input())
s = input()

res = s.count('R') * s.count('G') * s.count('B')

for i in range(n):
    for j in range(i+1, n-1):
        k = j + (j - i)
        if k < n:
            if s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]:
                res -= 1
        else:
            break

print(res)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(100000)

N = int(input())
palette = {1:1}
colors = {}
ends = {}
edges = {}

for edge in range(1,N):
    ends[edge] = [int(n) for n in input().split()]

    a, b = ends[edge]
    if a not in edges:
        edges[a] = [edge]
    else:
        edges[a].append(edge)
    if b not in edges:
        edges[b] = [edge]
    else:
        edges[b].append(edge)


def color_edges(parent, root):
    current_palette = palette.copy()
    if parent > 0:
        del current_palette[colors[parent]]
    for edge in edges[root]:
        if edge in colors:
            continue
        if len(current_palette) > 0:
            colors[edge] = current_palette.popitem()[0]
        else:
            color = len(palette) + 1
            palette[color] = 1
            colors[edge] = color
    for edge in edges[root]:
        if edge == parent:
            continue
        a, b = ends[edge]
        if a == root:
            color_edges(edge, b)
        else:
            color_edges(edge, a)

max_edges = 1
root = 1
for node in range(1,N+1):
    if len(edges[node]) > max_edges:
        max_edges = len(edges[node])
        root = node

color_edges(0, root)

print(len(palette))
for edge in range(1,N):
    print(colors[edge])


### FIXED CODE ###

import sys

sys.setrecursionlimit(100000)

N = int(input())
palette = 1
colors = {}
ends = {}
edges = {}

for edge in range(1,N):
    ends[edge] = [int(n) for n in input().split()]

    a, b = ends[edge]
    if a not in edges:
        edges[a] = [edge]
    else:
        edges[a].append(edge)
    if b not in edges:
        edges[b] = [edge]
    else:
        edges[b].append(edge)


def color_edges(parent, root):
    ng = {}
    global palette
    if parent > 0:
        ng[colors[parent]] = True
    for edge in edges[root]:
        if edge in colors:
            color = colors[edge]
        elif palette - len(ng) > 0:
            color = 1
            while color in ng:
                color += 1
            colors[edge] = color
        else:
            palette += 1
            color = palette
            colors[edge] = color

        ng[color] = True
    for edge in edges[root]:
        if edge == parent:
            continue
        a, b = ends[edge]
        if a == root:
            color_edges(edge, b)
        else:
            color_edges(edge, a)

max_edges = 1
root = 1
for node in range(1,N+1):
    if len(edges[node]) > max_edges:
        max_edges = len(edges[node])
        root = node

color_edges(0, root)

print(palette)
for edge in range(1,N):
    print(colors[edge])
### BUGGY CODE ###

import sys

S=sys.stdin.readline()
l=len(S)

mod=10**9+7

a=0
ab=0
ans=0
all=1

for x  in S:
	if x=="A":
		a+=all
	elif x=="B":
		ab+=a
	elif x=="C":
		ans+=ab
	elif x=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3

	ans%=mod
	ab%=mod
	a%=mod
	all%mod


print ans


### FIXED CODE ###

S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M
### BUGGY CODE ###

N = int(input())
S = [input() for _ in range(N)]  
uni_S = []
for s in S:
    if(s not in uni_S):
        uni_S.append(s)

print(len(uni_S))


### FIXED CODE ###

N = int(input())
S = [input() for _ in range(N)]  
S.sort()
uni_count = 1
for i in range(N-1):
    if(S[i+1]!=S[i]):
        uni_count += 1
print(uni_count)
### BUGGY CODE ###

N,A,B = map(int, input().split())
L = []
b = 0
ans = 0
cnt = 0

while True:
  if A == 0: break

  L.append(A)
  b += A
  cnt += A
  if cnt > N:
    ans = b - (cnt - N)
    break

  L.append(B)
  cnt += B
  if cnt > N:
    ans = b
    break

print(ans)

### FIXED CODE ###

N,A,B = map(int, input().split())
L = []
b = 0
ans = 0

if A == 0:
  ans = 0
elif N < A:
  ans = N
elif N < A+B:
  ans = A
else:
  x = N // (A+B)
  y = N % (A+B)
  ans = A * x + min(y, A)

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

import math
N=1000000
prime=[1]*(N+1)
prime[0]=0
prime[1]=0
for i in range(2,int(math.sqrt(N))):
    if prime[i]==1:
        j=i
        while i*j<=N:
            prime[i*j]=0
            j+=1

while True:
    n=input()
    if n==0:break
    cnt=0
    for i in range(n):
        p,m=map(int,raw_input().split())
        for j in range(max(p-m,0),min(p+m+1,N+1)):
            if prime[j]==1:
                cnt+=1
    print cnt-n

### FIXED CODE ###

import math
import bisect
N=1000000
prime=[1]*(N+1)
prime[0]=0
prime[1]=0
for i in range(2,int(math.sqrt(N))):
    if prime[i]==1:
        j=i
        while i*j<=N:
            prime[i*j]=0
            j+=1
prime=[i for i in range(N+1) if prime[i]==1]

while True:
    n=input()
    if n==0:break
    cnt=0
    for i in range(n):
        p,m=map(int,raw_input().split())
        l=bisect.bisect_left(prime,p-m)
        u=bisect.bisect_left(prime,p+m+1)
        cnt+=u-l
    print cnt-n
### BUGGY CODE ###

n,m = map(int,input().split())
one_li = []
to_n_li = []
for _ in range(m):
    a,b = map(int,input().split())
    if a == 1:
        one_li.append(b)
    if b == n:
        to_n_li.append(a)
#print(one_li,to_n_li)
for o in list(set(one_li)):
    if o in list(set(to_n_li)):
        print('POSSIBLE')
        exit()
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

n,m = map(int,input().split())
one_li = []
to_n_li = []
for _ in range(m):
    a,b = map(int,input().split())
    if a == 1:
        one_li.append(b)
    if b == n:
        to_n_li.append(a)
ll = len(set(one_li) & set(to_n_li))
if ll == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')
### BUGGY CODE ###

#入力
K, S = map(int, input().split())

count = 0
x = 0
while x <= K:
    y = 0
    while y <= K:
        a = S-x-y
        if a <= K and a >= 0:
            count += 1
        y += 1
    x += 1

print(count)

#↑TLE

### FIXED CODE ###

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

count = 0
for x in range(0,K+1):
    for y in range(0,K+1):
        a = S-x-y
        if a <= K and a>= 0:
            count += 1
print (count)
### BUGGY CODE ###

N = int(input().strip())
S = input().strip()

dp = [[0 for j in range(N+1)] for i in range(N+1)]

for i in range(N - 1, -1, -1):
    for j in range(N - 1, -1, -1):
        if S[i] != S[j]:
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i + 1][j + 1] + 1

max_length = 0
for i in range(N):
    for j in range(N):
        if i < j:
            length = min(j - i, dp[i][j])
            max_length = max(length, max_length)

print(max_length)


### FIXED CODE ###

N = int(input().strip())
S = input().strip()

dp = [[0 for j in range(N+1)] for i in range(N+1)]

for i in range(N - 1, -1, -1):
    for j in range(N - 1, -1, -1):
        if S[i] != S[j]:
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i + 1][j + 1] + 1

max_length = 0
for i in range(N):
    for j in range(N):
        if i < j:
            length = min(j - i, dp[i][j])
            max_length = max(length, max_length)

print(max_length)
### BUGGY CODE ###

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

ans = 0
for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if i + j + l == s:
                ans += 1

print(ans)

### FIXED CODE ###

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

ans = 0
for i in range(min(s,k)+1):
    for j in range(i,min(s-i,k)+1):
        l = s - i - j
        if k >= l >= j: 
            if i == j and j == l:
                ans += 1
            elif i != j and j!= l and i != l:
                ans += 6
            else:
                ans += 3

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

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 ** 9  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

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)

n, a, b = map(int, input().split())
ans = 2**n % p - 1
ans -= cmb(n, a, p) + cmb(n, b, p)
print(ans % p)


### FIXED CODE ###

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

p = 10 ** 9 + 7
n, a, b = map(int, input().split())
ans = pow(2, n, p) - 1
ans -= cmb(n, a, p) + cmb(n, b, p)
print(ans % p)
### BUGGY CODE ###

n=int(input())
s=input()
lst=list(s)
r=[]
g=[]
b=[]
for i,v in enumerate(lst):
    if v=="R":
        r.append(i)
    elif v=="G":
        g.append(i)
    elif v=="B":
        b.append(i)
comb=len(r)*len(g)*len(b)
out=0
for i in r:
  for j in g:
    for k in b:
      if (i+j)==2*k or (j+k)==2*i or (k+i)==2*j:
        out+=1
print(comb-out)


### FIXED CODE ###

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

X, K, D = map(int, input().split())

if(X > 0):
    if(X-K*D >= 0):
        print(X-K*D)
    else:
        while(X >= 0):
            X = X-D
            K -= 1
        if(K % 2 == 0):
            print(abs(X))
        else:
            print(abs(X+D))
elif(X < 0):
    if((X+K*D) <= 0):
        print(abs(X+K*D))
    else:
        while(X <= 0):
            X = X+D
            K -= 1
        if(K % 2 == 0):
            print(abs(X))
        else:
            print(abs(X-D))
else:
    if(K % 2 == 0):
        print(0)
    else:
        print(abs(D))


### FIXED CODE ###

X, K, D = map(int, input().split())

if(X > 0):
    if(X-K*D >= 0):
        print(X-K*D)
    else:
        l = X//D
        X = X-D*(l+1)
        K = K-l-1
        if(K % 2 == 0):
            print(abs(X))
        else:
            print(abs(X+D))
elif(X < 0):
    if((X+K*D) <= 0):
        print(abs(X+K*D))
    else:
        l = -X//D
        X = X + D*(l+1)
        K = K-l-1
        if(K % 2 == 0):
            print(abs(X))
        else:
            print(abs(X-D))
else:
    if(K % 2 == 0):
        print(0)
    else:
        print(abs(D))
### BUGGY CODE ###

N = int(input())
headB=0
tailA=0 
both = 0
ans = 0
for j in range(N):
    t = input()
    if t[0] == "B":
        if t[-1] == "A":
            both += 1
        else:
            headB += 1
    elif t[-1] == "A":
        tailA += 1
    ans += t.count("AB")
while both > 0:
    tmp = min(tailA,both)
    ans += tmp
    both -= tmp
    tmp = min(headB,both)
    ans += tmp
    both -= tmp
ans += min(headB,tailA)
print(ans)

### FIXED CODE ###

N = int(input())
headB=0
tailA=0 
both = 0
ans = 0
for j in range(N):
    t = input()
    if t[0] == "B":
        if t[-1] == "A":
            both += 1
        else:
            headB += 1
    elif t[-1] == "A":
        tailA += 1
    ans += t.count("AB")
if both > 0:
    ans += both - 1
    if tailA > 0 or headB > 0:
        ans += 1
ans += min(tailA,headB)
print(ans)
### BUGGY CODE ###

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

count=0

for i in range(K+1):
    for j in range(i+1):
        for k in range(j+1):
            if i+j+k==S:
                #print(i,j,k)
                if i==j and j==k:
                    count+=1
                elif i==j or j==k or i==k:
                    count+=3
                else:
                    count+=6
print(count)

### FIXED CODE ###

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

count=0

for x in range(K+1):
    for y in range(x+1):
        z=S-x-y
        if z<0 or z>y:
            pass
        else:
            #print(x,y,z)
            if x==y==z:
                count+=1
            elif x==y or x==z or y==z:
                count+=3
            else:
                count+=6
        
print(count)
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
A = set(a)
l = len(A)
s = []
if l<=k:
    print(0)
    exit()
else:
    for i in A:
        s.append(a.count(i))
s = sorted(s)
print(sum(s[:l-k]))

### FIXED CODE ###

import collections
n,k = map(int,input().split())
a = list(map(int,input().split()))
s = list(collections.Counter(a).values())
s = sorted(s)
print(sum(s[0:len(s)-k]))
### BUGGY CODE ###

N=int(input())
A=[int(x) for x in input().split()]
A=[0]+A+[0]
dist=[0]*(N+1)
for i in range(N+1):
    dist[i]=abs(A[i]-A[i+1])
for i in range(1,N+1):
    if A[i]<min(A[i-1],A[i+1]) or A[i]>max(A[i-1],A[i+1]):
        print(sum(dist)-2*min(dist[i-1],dist[i]))
    else:
        print(sum(dist))

### FIXED CODE ###

N=int(input())
A=[int(x) for x in input().split()]
A=[0]+A+[0]
dist=[0]*(N+1)
S=0
for i in range(N+1):
    S+=abs(A[i]-A[i+1])
for i in range(1,N+1):
    dist[i]=S+abs(A[i-1]-A[i+1])-(abs(A[i-1]-A[i])+abs(A[i]-A[i+1]))

for i in range(1,N+1):
    print(dist[i])
### BUGGY CODE ###

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

sum1=0
j=1
for i in range(N-1):
    while j<N:
        sum1+=a_l[i]^a_l[j]
        j+=1
    j=i+2
print(sum1%(7+10**9))

### FIXED CODE ###

n=int(input())
lis=list(map(lambda x:format(int(x),'b'),input().split()))
l=0
for i in range(n):
    l=max(l,len(lis[i]))

d0=[0]*60
d1=[0]*60

for i in range(n):
    lis[i]=lis[i].zfill(l)
    for j in range(l):
        if lis[i][-j-1]=='0':
            d0[j]+=1
        else:
            d1[j]+=1

ans=0
for i in range(60):
    ans+=(d0[i]*d1[i]*2**i)%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

# AtCoder Beginner Contest 134 E - Sequence Decomposing

import sys

N = int(input())
ans = []

for n in range(N):
    now = int(input())
    for a in ans:
        if a[-1] < now:
            a.append(now)
            break
    else:
        appending = [now]
        ans.append(appending)

print(len(ans))


### FIXED CODE ###

# AtCoder Beginner Contest 134 E - Sequence Decomposing

import sys
import bisect

N = int(input())
now = int(sys.stdin.readline().strip())
ans = [now]

for n in range(N - 1):
    now = int(sys.stdin.readline().strip())

    if now > ans[0]:
        ans[0] = now
    elif ans[-1] >= now:
        ans.append(now)
    else:
        # 2部探査で行進位置を探る
        left = 0  # 挿入不可能
        right = len(ans) - 1  # 挿入可能

        while right - left > 1:
            mid = (right + left) // 2
            if now > ans[mid]:
                right = mid
            else:
                left = mid

        ans[right] = now

print(len(ans))

    # if ans:  # 最初の入力以外であり、すでに追加対象のリストが存在する
    #     if ans[0][-1] < now:
    #         ans[0].append(now)
    #     elif ans[-1][-1] >= now:
    #         appending = [now]
    #         ans.append(appending)
    #     else:
    #         # 二分探索で追加するリストの位置を特定する
    #         left = 0   # 追加できない  ans[left][-1] > now
    #         right = len(ans) - 1  # ans[right][-1] < now
    #
    #         while right - left > 1:
    #             mid = (right - left) // 2
    #             if ans[mid][-1] < now:
    #                 right = mid
    #             else:
    #                 left = mid
    #         ans[right].append(now)
    # else:
    #     appending = [now]
    #     ans.append(appending)

    # for a in ans:
    #     if a[-1] < now:
    #         a.append(now)
    #         break
    # else:
    #     appending = [now]
    #     ans.append(appending)

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

import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

n,m = MAP()
a = MAP()

for i in range(m):
    idx = a.index(max(a))
    a[idx] = a[idx]//2

print(sum(a))

### FIXED CODE ###

import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush,heapify
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

n,m = MAP()
a = MAP()
a = [-i for i in a]
heapify(a)
for i in range(m):
    tmp = -heappop(a)
    heappush(a,-(tmp//2))
print(-sum(a))
### BUGGY CODE ###

s = list(input())
t = list(input())

ans = 'Yes'

for j in range(len(s)):
    if s.count(s[j]) != t.count(t[j]):
        ans = 'No'

print(ans)


### FIXED CODE ###

s = input()
t = input()

counta={}
countb={}

for i in s:
    if i in counta:
        counta[i] += 1
    else:
        counta[i] = 1

for y in t:
    if y in countb:
        countb[y] += 1
    else:
        countb[y] = 1

if sorted(counta.values())  == sorted(countb.values()):
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

N = int(input())
X = input()
fn = {0: 0}

def culc_fn(n, fn):
    if not n in fn.keys():
        popcount = bin(n).count('1')
        tmp = n%popcount
        fn[n] = culc_fn(tmp, fn) + 1
    return fn[n]

for i in range(N):
    tmp = int(X[:i] + ('0' if X[i] == '1' else '1') + X[i+1:], 2)
    print(culc_fn(tmp, fn))

### FIXED CODE ###

# N = 10
# X = '1'*N
N = int(input())
X = input()
popcount_X = X.count('1')
X_ = int(X, 2)

X_mod_minus = X_%(popcount_X-1) if popcount_X > 1 else -1
X_mod_plus = X_%(popcount_X+1)
for i in range(N):
    if X[i] == '0':
        popcount = popcount_X+1
        X_i = (X_mod_plus + pow(2, N-i-1, popcount))%(popcount)
    else:
        if X_mod_minus == -1:
            print(0)
            continue
        popcount = popcount_X-1
        X_i = (X_mod_minus - pow(2, N-i-1, popcount))%(popcount)
    ans = 1
    while X_i > 0:
        X_i %= bin(X_i).count('1')
        ans += 1
    print(ans)
### BUGGY CODE ###

N=int(input())
c=list(input())
le=len(c)
count=0

while 'WR' in ''.join(c):
    count+=1
    w=c.index('W')
    r=le-c[::-1].index('R')-1
    c[w]='R' ; c[r]='W'

print(count)

### FIXED CODE ###

N=int(input())
c=input()
count=0

if 'WR' in c:
    x=c.count('R')
    y=c.count('R',0,x)
    count=x-y
print(count)
### BUGGY CODE ###

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

for i in range(len(nums)):
  tmp_nums = sorted(nums[:i]+nums[i+1:])
  print(tmp_nums[len(tmp_nums)//2])

### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
y = sorted(x)
a = y[n//2-1]
b = y[n//2]
for i in range(n):
  if x[i] <= a:
    print(b)
  else:
    print(a)