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

import sys
input = sys.stdin.readline

def solve():
    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def addValue(iA, A):
        iB = iA + 1
        while iB > 0:
            data[iB] += A
            iB -= iB & -iB
    def getValue(iA):
        iB = iA + 1
        ans = 0
        while iB <= numPow2:
            ans += data[iB]
            iB += iB & -iB
        return ans
    def addRangeValue(iFr, iTo, A):
        addValue(iTo, A)
        if iFr > 0:
            addValue(iFr-1, -A)

    N, M = map(int, input().split())
    LRss = [[] for _ in range(M+1)]
    for _ in range(N):
        L, R = map(int, input().split())
        LRss[R-L+1].append((L, R))

    data, numPow2 = makeBIT(M+1)

    anss = []
    numOK = N
    for d in range(1, M+1):
        ans = numOK
        for i in range(d, M+1, d):
            ans += getValue(i)
        anss.append(ans)
        numOK -= len(LRss[d])
        for L, R in LRss[d]:
            addRangeValue(L, R, 1)

    print('\n'.join(map(str, anss)))


solve()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def solve():
    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def addValue(iA, A):
        iB = iA + 1
        while iB > 0:
            data[iB] += A
            iB -= iB & -iB
    def getValue(iA):
        iB = iA + 1
        ans = 0
        while iB <= numPow2:
            ans += data[iB]
            iB += iB & -iB
        return ans
    def addRangeValue(iFr, iTo, A):
        addValue(iTo, A)
        if iFr > 0:
            addValue(iFr-1, -A)

    N, M = map(int, input().split())
    LRss = [[] for _ in range(M+1)]
    for _ in range(N):
        L, R = map(int, input().split())
        LRss[R-L+1].append((L, R))

    data, numPow2 = makeBIT(M+1)

    anss = []
    numOK = N
    for d in range(1, M+1):
        ans = numOK
        for i in range(d, M+1, d):
            ans += getValue(i)
        anss.append(ans)
        numOK -= len(LRss[d])
        for L, R in LRss[d]:
            addRangeValue(L, R, 1)

    print('\n'.join(map(str, anss)))


solve()
### BUGGY CODE ###

from collections import Counter

# print('input >>')

S = input()
S = S[::-1]

mods = [0] * (len(S)+1)
mods[0] = int(S[0]) % 2019

for i in range(len(mods)-1-1):
    mods[i+1] = (int(S[i+1]) * 10 ** (i+1) + mods[i]) % 2019

# print(mods)

ans = 0

counter = Counter(mods)

for c, n in counter.most_common():
    if n > 1:
        ans += (n * (n-1)) // 2

# print('-----output-----')

print(ans)

### FIXED CODE ###

from collections import Counter

# print('input >>')

S = input()
S = S[::-1] + '0'

mod = 0
mods = [0] * 2019
mods[0] += 1

i_mod = 1

for i in range(len(S)-1):
    # mods[i+1] = (int(S[i+1]) * 10 ** (i+1) + mods[i]) % 2019
    i_mod %= 2019
    mod = (int(S[i]) * i_mod + mod) % 2019
    # print(mod)
    mods[mod]+=1
    i_mod *= 10

# print(mods)

ans = 0

# counter = Counter(mods)

# for n in counter.values():
#     if n > 1:
#         ans += (n * (n-1)) // 2

# print('-----output-----')

for m in mods:
    if m > 1:
        ans += (m * (m-1)) // 2

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

import sys
input = sys.stdin.readline
n,q = map(int,input().split())
s = list(input())
check = [0]*n
for i in range(n-1):
    if s[i] == 'A' and s[i+1] == 'C':
        check[i+1] = 1
for i in range(q):
    l,r = map(int,input().split())
    ans = 0
    for j in range(l,r):
        ans += check[j]
    print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,q = map(int,input().split())
s = list(input())
check = [0]*n
const = 0
for i in range(n-1):
    check[i] = const
    if s[i] == 'A' and s[i+1] == 'C':
        check[i+1] = const + 1
        const += 1
        i += 1
check[-1] = const
for i in range(q):
    l,r = map(int,input().split())
    print(check[r-1]-check[l-1])
### BUGGY CODE ###

def solve():
    MOD = 10 ** 9 + 7
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    A_dict = {}
    B_dict = {}
    for i in range(N):
        A_dict[A[i]] = 1
    for i in range(M):
        B_dict[B[i]] = 1
    
    row, columun = 0, 0
    ans = 1
    for i in range(N * M, 0, -1):
        in_A = i in A_dict
        in_B = i in B_dict
        if in_A and in_B:
            row += 1
            columun += 1
        elif in_A:
            row += 1
            ans *= columun
        elif in_B:
            columun += 1
            ans *= row
        else:
            ans *= row * columun - (N * M - i)
    print(ans % MOD)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

def solve():
    MOD = 10 ** 9 + 7
    N, M = map(int, input().split())
    A = set(map(int, input().split()))
    B = set(map(int, input().split()))
    
    row, columun = 0, 0
    ans = 1
    for i in range(N * M, 0, -1):
        in_A = i in A
        in_B = i in B
        if in_A and in_B:
            row += 1
            columun += 1
        elif in_A:
            row += 1
            ans *= columun
        elif in_B:
            columun += 1
            ans *= row
        else:
            ans *= row * columun - (N * M - i)
        ans %= MOD
    print(ans)


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

n,k=map(int,input().split())
s=input()
s_dimlist=[s[i+1]==s[i] for i in range(n-1)]
s_seqcnt=[]
if s[0]=='0':
    s_seqcnt.append(0)
pre=-1
for i in range(n-1):
    if not s_dimlist[i]:
        s_seqcnt.append(i-pre)
        pre=i
s_seqcnt.append(n-1-pre)
if s[n-1]=='0':
    s_seqcnt.append(0)
# print(s_dimlist)
# print(s_seqcnt)
width=2*k+1
length=len(s_seqcnt)
s_sum=[0 for _ in range(length//2+1)]
cnt=0
for i in range(length):
    if i%2==0:
        num=0
        for j in range(width):
            if i+j>=length:
                break
            num+=s_seqcnt[i+j]
        s_sum[cnt]=num
        cnt+=1
# print(s_sum)
print(max(s_sum))


### FIXED CODE ###

n,k=map(int,input().split())
s=input()
s_dimlist=[s[i+1]==s[i] for i in range(n-1)]
s_seqcnt=[]
if s[0]=='0':
    s_seqcnt.append(0)
pre=-1
for i in range(n-1):
    if not s_dimlist[i]:
        s_seqcnt.append(i-pre)
        pre=i
s_seqcnt.append(n-1-pre)
if s[n-1]=='0':
    s_seqcnt.append(0)
# print(s_dimlist)
# print(s_seqcnt)
width=2*k+1
length=len(s_seqcnt)
s_sum=[0 for i in range(length//2+length%2)]
s_ruiseki=[0 for i in range(length+1)]
s_ruiseki[0]=0
s_ruiseki[1]=s_seqcnt[0]
for i in range(1,length):
    s_ruiseki[i+1]=s_seqcnt[i]+s_ruiseki[i]
# print(s_ruiseki)
for i in range(length//2+length%2):
    num=0
    if 2*i+width-1>=length:
        s_sum[i]=s_ruiseki[length]-s_ruiseki[2*i]
        break
    else:
        s_sum[i]=s_ruiseki[2*i+width]-s_ruiseki[2*i]
# print(s_sum)
print(max(s_sum))
### BUGGY CODE ###

# 初期入力
N= int(input())
S =input()

from collections import Counter
c = Counter(S)
count_all =c["R"] * c["G"] * c["B"]
count =0
for i,v in enumerate(S):
    for j in range(1,(N+1)//2):
        if  i+j*2 <N: 
            if S[i]=="R" and S[i+j] =="G" and S[i+j*2] =="B":
                #print(i-j,i,i+j)
                count +=1
            elif S[i]=="R" and S[i+j] =="B" and S[i+j*2] =="G":
                #print(i-j,i,i+j)
                count +=1
            elif S[i]=="G" and S[i+j] =="R" and S[i+j*2] =="B":
                #print(i-j,i,i+j)
                count +=1
            elif S[i]=="G" and S[i+j] =="B" and S[i+j*2] =="R":
                #print(i-j,i,i+j)
                count +=1
            elif S[i]=="B" and S[i+j] =="G" and S[i+j*2] =="R":
                #print(i-j,i,i+j)
                count +=1
            elif S[i]=="B" and S[i+j] =="R" and S[i+j*2] =="G":
                count +=1
                #print(i-j,i,i+j)

print(count_all - count)   

### FIXED CODE ###

# 初期入力
N= int(input())
S =input()


#
R_index=[]
G_index=[]
B_index=[]
for i,v in enumerate(S):
    if v =="R":
        R_index.append(i)
    if v =="G":
        G_index.append(i)
    if v =="B":
        B_index.append(i)

# 例　R_index各要素から等距離離れたところに左にG、右にBがあればOK
R_B =[]
B_G =[]
count_ij_jk_onaji =0
for r in R_index:
    for g in G_index:
        if 0<=g-(r-g) and g-(r-g)<N  :
            #if S[g-(r-g)]=="B" and r<g:
            if S[g-(r-g)]=="B" :
                count_ij_jk_onaji +=1
               # print(r,g,g-(r-g),"B")
for b in B_index:
    for r in R_index:
        if 0<=r-(b-r) and r-(b-r)<N :
            #if S[r-(b-r)] == "G" and b<r:
            if S[r-(b-r)] == "G" :
                count_ij_jk_onaji +=1
                #print(r,b,r-(b-r),"G")
for g in G_index:
    for b in B_index:
        if 0<=b-(g-b) and b-(g-b)<N :
            #if S[b-(g-b)] =="R" and g<b:
            if S[b-(g-b)] =="R":
                count_ij_jk_onaji +=1
                #print(b,g,b-(g-b),"R")

            
#3つとも異なる文字=all
kotae_all = len(R_index) * len(G_index) * len(B_index) 
print(kotae_all -count_ij_jk_onaji)
### BUGGY CODE ###

import itertools

n=int(input())
lis=[list(map(int,input().split())) for _ in range(2)]
ans=0

for li in itertools.product([0,1], repeat=n):
  v=0
  for id,l in enumerate(li):
    if l:
      v += lis[0][id] - lis[1][id]
      
  if v > ans:
    ans=v
    
print(ans)

### FIXED CODE ###

import itertools

n=int(input())
lis=[list(map(int,input().split())) for _ in range(2)]
ans=0

for li in itertools.product([0,1], repeat=n):
  v=0
  for id,l in enumerate(li):
    if l:
      v += lis[0][id] - lis[1][id]
      
  if v > ans:
    ans=v
    
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split(" "))
routs = {}
tereporter = list(map(int, input().split()))
for i in range(N):
  routs[i + 1] = tereporter[i]
present_location = 1
for i in range(K):
  present_location = routs[present_location]
print(present_location)


### FIXED CODE ###

N, K = map(int, input().split(" "))
routs = {}
location = [0 for i in range(N + 1)]
tereporter = list(map(int, input().split()))
for i in range(N):
  routs[i] = tereporter[i] - 1
present_location = 0
n = 0
for i in range(K):
  n += 1
  present_location = routs[present_location]
  if location[present_location] == 0:
    location[present_location] = n
  else:
    loop = n - location[present_location]
    if (K - location[present_location]) % loop == 0:
      break
    else:
      for i in range((K - location[present_location]) % loop):
        present_location = routs[present_location]
      break
print(present_location + 1)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

class UnionFindTree:
  def __init__(self, n):
    self.nodes = [-1]*n
    
  def find(self, x):
    parents = []
    while True:
      parent = self.nodes[x]
      if parent < 0:
        for p in parents:
          self.nodes[p] = x
        return x
      else:
        x = parent
  
  def unite(self, x, y):
    xp = self.find(x)
    yp = self.find(y)
    self.nodes[xp] += self.nodes[yp]
    self.nodes[yp] = xp  
  
  def size(self, x):
    return -self.nodes[self.find(x)]


def main():
  n, m = map(int, input().split())
  edges = []
  
  for _ in range(m):
    a, b = map(lambda x:int(x)-1, input().split())
    edges.append((a, b))
  uftree = UnionFindTree(n)
  scores = []
  
  for a, b in edges[::-1]:
    ap = uftree.find(a)
    bp = uftree.find(b)
    if  ap != bp:
      scores.append(uftree.size(ap) * uftree.size(bp))
      uftree.unite(a, b)    
    else:
      scores.append(0)
      
  sum = 0
  for score in scores[::-1]:
    sum += score
    print(sum)

if __name__=='__main__':
  main()



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

class UnionFindTree:
  def __init__(self, n):
    self.nodes = [-1]*n
    
  def find(self, x):
      parent = self.nodes[x]
      if parent < 0:
        return x
      else:
        self.nodes[x] = self.find(self.nodes[x])
        return self.nodes[x]
  
  def unite(self, x, y):
    xp = self.find(x)
    yp = self.find(y)
    if self.nodes[xp] > self.nodes[yp]:
      xp, yp = yp, xp
    self.nodes[xp] += self.nodes[yp]
    self.nodes[yp] = xp  
  
  def size(self, x):
    return -self.nodes[self.find(x)]


def main():
  n, m = map(int, input().split())
  edges = []
  
  for _ in range(m):
    a, b = map(lambda x:int(x)-1, input().split())
    edges.append((a, b))
  uftree = UnionFindTree(n)
  scores = []
  
  for a, b in edges[::-1]:
    ap = uftree.find(a)
    bp = uftree.find(b)
    if  ap != bp:
      scores.append(uftree.size(ap) * uftree.size(bp))
      uftree.unite(a, b)    
    else:
      scores.append(0)
      
  sum = 0
  for score in scores[::-1]:
    sum += score
    print(sum)

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

N=int(input())
A = [int(x) for x in input().split()]
flag=False
for i in range(N):
    check=A[i]
    for k in range(N):
        if i!=k and check==A[k]:
            flag=True
            break
    if flag:
        break
if flag:
    print("NO")
else:
    print("YES")

### FIXED CODE ###

#C
from collections import Counter
N=int(input())
A=[int(x) for x in input().split()]

A_C=Counter(A)

flag=True
for i,v in A_C.items():
    if v!=1:
        flag=False
        break
if flag:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

#14
N =int(input())
a = list(map(int,input().split()))
b = ""

for i in range(N):
    b += str(a.index(i+1)+1) + " "
    
    
print(b)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
L = [[] for i in range(N)]
for i in range(N):
    L[i] = [A[i], i+1]
L.sort()
ans = [0 for i in range(N)]
for i in range(N):
    ans[i] = L[i][1]
print(*ans)
### BUGGY CODE ###

import math

n,m,l=map(int,input().split())
INF=(10**9)+1

g=[]
f=[]
for i in range(n):
    g.append([INF]*(n))
    f.append([INF]*(n))

for i in range(len(g)):
    for j in range(len(g)):
        if i==j:
            g[i][j]=0
            f[i][j]=0

for i in range(m):
    a,b,c=map(int,input().split())
    g[a-1][b-1]=c
    g[b-1][a-1]=c
    f[a-1][b-1]=c
    f[b-1][a-1]=c

for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j]=min(g[i][j],g[i][k]+g[k][j])
            f[i][j]=min(f[i][j],f[i][k]+f[k][j])

for i in range(n):
    for j in range(n):
        if f[i][j]<=l:
            g[i][j]=1
        else:
            g[i][j]=INF
        if i==j:
            g[i][j]=0

for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j]=min(g[i][j],g[i][k]+g[k][j])

q=int(input())
for i in range(q):
    s,t=map(int,input().split())
    u=g[s-1][t-1]

    if u>=INF:
        print (-1)
    else:
        print (u-1)

### FIXED CODE ###

n,m,l=map(int,raw_input().split())
INF=(10**9)+1

g=[]
f=[]
for i in xrange(n):
    g.append([INF]*(n))
    f.append([INF]*(n))

for i in xrange(len(g)):
    for j in xrange(len(g)):
        if i==j:
            g[i][j]=0
            f[i][j]=0

for i in xrange(m):
    a,b,c=map(int,raw_input().split())
    g[a-1][b-1]=c
    g[b-1][a-1]=c
    f[a-1][b-1]=c
    f[b-1][a-1]=c

for k in xrange(n):
    for i in xrange(n):
        for j in xrange(n):
            g[i][j]=min(g[i][j],g[i][k]+g[k][j])
            f[i][j]=min(f[i][j],f[i][k]+f[k][j])

for i in xrange(n):
    for j in xrange(n):
        if f[i][j]<=l:
            g[i][j]=1
        else:
            g[i][j]=INF
        if i==j:
            g[i][j]=0

for k in xrange(n):
    for i in xrange(n):
        for j in xrange(n):
            g[i][j]=min(g[i][j],g[i][k]+g[k][j])

q=int(raw_input())
for i in xrange(q):
    s,t=map(int,raw_input().split())
    u=g[s-1][t-1]

    if u>=INF:
        print (-1)
    else:
        print (u-1)
### BUGGY CODE ###

#C-Poll
import collections
n=int(input())
words = [input() for _ in range(n)]
count = collections.Counter(words)
leng = len(count)
Flg = True
ansallay = []
for num in range(n-1):
    #もし配列が1種類しかなかった場合はそれだけ足してbreakする
    if(leng == 1):
      ansallay.append(count.most_common()[num][0])
      break
    ansallay.append(count.most_common()[num][0])
    if(count.most_common()[0][1] != count.most_common()[num+1][1]):
        break
    num += 1
    if(num == leng-1):
      if(count.most_common()[0][1] == count.most_common()[num][1]):
        ansallay.append(count.most_common()[num][0])
      break
ansallay.sort()
for word in ansallay:
    print(word)

### FIXED CODE ###

#C-Poll
import collections
n=int(input())
words = [input() for _ in range(n)]
count = collections.Counter(words)
leng = len(count)
ansallay = []
#抽出用に何回出てればansに出すかを変数に突っ込む
record = count.most_common()[0][1]
ms=count.most_common()
for num in range(leng):
    if(ms[num][1] == record):
        ansallay.append(ms[num][0])
    else:
        break
ansallay.sort()
for word in ansallay:
    print(word)
### BUGGY CODE ###

# Problem D - Multiple of 2019

from collections import Counter

# input
S = input()
s_len = len(S)

# initialization
ans = 0
mod_list = [0]*(s_len + 1)

# mod count
for i in range(1, s_len+1):
    tmp_num = int(S[s_len-i:])
    mod_list[i] = tmp_num % 2019

# output
mod_counter = Counter(mod_list)
for k in mod_counter.keys():
    m_c = mod_counter[k]
    if m_c>=2:
        ans += m_c * (m_c-1) // 2
print(ans)


### FIXED CODE ###

# Problem D - Multiple of 2019

# input
S = list(input())
N = len(S)

# initialization
ans = 0

# count
nums_2019 = [0]*2019
nums_2019[0] = 1
s = 0
for i in range(N-1, -1, -1):
    s += int(S[i]) * pow(10, N - i - 1, 2019)
    nums_2019[s%2019] += 1

for i in range(2019):
    if nums_2019[i]>=2:
        ans += nums_2019[i] * (nums_2019[i]-1) // 2

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

import logging

logger = logging.getLogger(__name__)
logger.setLevel(logging.INFO)
h = logging.FileHandler("logtest.log")
logger.addHandler(h)

N, Q = map(int, input().split())
logger.info("N: {}, Q: {}".format(N, Q))
s = input()
logger.info("s: {}".format(s))

Query = [input().split() for i in range(Q)]

left, right = 0, N - 1

# 二分探索: boundaryを求める
for t, d in reversed(Query):
    logger.info("t: {}, d: {}".format(t, d))
    logger.info("[before] left: {}, right: {}".format(left, right))
    if d == "L":
        if t == s[left]:
            left += 1
        if right < N - 1 and t == s[right + 1]:
            right = min(right + 1, N - 1)
    else:
        if left > 0 and t == s[left - 1]:
            left = max(left - 1, 0)
        if t == s[right]:
            right -= 1
    logger.info("[after] left: {}, right: {}\n".format(left, right))
print(right - left + 1)


### FIXED CODE ###

# N, Q = map(int, input().split())
import sys

input = sys.stdin.readline

N, Q = tuple(map(int, input().split()))
s = input()

Query = [input().split() for i in range(Q)]

left, right = 0, N - 1

for t, d in reversed(Query):
    if d == "L":
        if t == s[left]:
            left += 1
        if right < N - 1 and t == s[right + 1]:
            right = min(right + 1, N - 1)
    else:
        if left > 0 and t == s[left - 1]:
            left = max(left - 1, 0)
        if t == s[right]:
            right -= 1
print(max(right - left + 1, 0))
### BUGGY CODE ###

k=int(input())

lis = [i for i in range(1,10)]
for _ in range(k-1):
    x=lis.pop(0)
    if x%10!=0:
        lis.append(10*x+(x%10)-1)
    lis.append(10*x+(x%10))
    if x%10!=9:
        lis.append(10*x+(x%10)+1)
print(lis.pop(0))

### FIXED CODE ###

from collections import deque
k=int(input())

lis = deque([i for i in range(1,10)])
for _ in range(k-1):
    x=lis.popleft()
    if x%10!=0:
        lis.append(10*x+(x%10)-1)
    lis.append(10*x+(x%10))
    if x%10!=9:
        lis.append(10*x+(x%10)+1)
print(lis.popleft())
### BUGGY CODE ###

import bisect

s=input()
t=input()

#print(index)
condition=0
#t2=list(set(t))
#print(t2)

#for i in range(len(t)):
# if s.count(t[i])==0:
#   condition=1
#   break
index=list()
for a in range(len(t)):
 index.append([i for i, x in enumerate(s) if x == t[a]])

for i in range(len(t)):
 if index[i]==[]:
   condition=1
   break

if condition==1:
  print(-1)
else:
  #print(index)
  b=index[0][0]
  j=1
  loop=0
  count=0
  if len(t)==1:
    print(b+1)
  else:
   while j <= len(t)-1:
     c=bisect.bisect_left(index[j],b)
     #print(j,index[j],b,c,loop)
     if c < len(index[j]) and c != index[j][len(index[j])-1]:
        b=index[j][c]
        #print(j,b,loop)
        j=j+1
        if j==len(t):
          print(b+loop+1)
          break
     else:
        loop=loop+len(s)
        b=index[j][0]
        j=j+1
        if j==len(t):
          print(b+loop+1)
          break
        if loop == len(s)*(10**100):
           print(-1)
           break
        



### FIXED CODE ###

import bisect

s=input()
t=input()

#index=list()
#for a in range(len(t)):
# index.append([i for i, x in enumerate(s) if x == t[a]])

char_appear = {ch: [] for ch in 'abcdefghijklmnopqrstuvwxyz'}
for i, ch in enumerate(s):
    char_appear[ch].append(i)
#print(char_appear['a'])
      
b=0
loop=0
condition=0

for j in range(len(t)):
  if len(char_appear[t[j]])<1:
    print(-1)
    condition=1
    break
  c=bisect.bisect(char_appear[t[j]],b)
 # print(j,char_appear[t[j]],b,c,loop)
  if j<1:
    b=char_appear[t[0]][0]    
  elif c == len(char_appear[t[j]]): #or c==char_appear[t[j]][len(char_appear[t[j]])-1]: 
     loop +=1
     b=char_appear[t[j]][0]
     if loop==10**100:
        print(-1)
        condition=1
        break
  else:
     b=char_appear[t[j]][c]
     #print(j,b,loop)


if condition==0:
 print(b+loop*len(s)+1)
### BUGGY CODE ###

import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

N,M = map(int, sys.stdin.readline().split())
list_A = list(map(int, sys.stdin.readline().split()))

for i in range(M):
    list_A.sort(reverse=True)
    list_A[0] = int(list_A[0]/2) 

ans = 0

for i in range(N):
    ans += list_A[i]

print(ans)


### FIXED CODE ###

import sys
import math
import numpy as np
from fractions import gcd

import heapq

# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

N,M = map(int, sys.stdin.readline().split())
list_A = list(map(int, sys.stdin.readline().split()))
# list_A.sort(reverse=True)

# list_A_np = np.array(list_A)

# hq = heapq.heapify(list_A)
for i in range(N):
    list_A[i] = -list_A[i]

heapq.heapify(list_A)
# print(list_A)
# print(int(-4.34))

for i in range(M):
    tmp = heapq.heappop(list_A)
    heapq.heappush(list_A, int(tmp/2))

# for i in range(M):
    # list_A.sort(reverse=True)
    # idx_max = list_A.index(max(list_A))
    # list_A[idx_max] = int(list_A[idx_max]/2)

    # if(list_A[0] > list_A[1]):
    #     list_A[0] = int(list_A[0]/2)
    # else:
    #     list_A.sort(reverse=True)
    #     list_A[0] = int(list_A[0]/2)


    # if(list_A_np[0] > list_A_np[1]):
    #     list_A_np[0] = int(list_A_np[0]/2)
    # else:
    #     # idx_max = list_A_np.argmax()
    #     # list_A_np[idx_max] = int(list_A_np[idx_max]/2)
    #     list_A_np = np.sort(list_A_np)[::-1]
    #     list_A_np[0] = int(list_A_np[0]/2)

    # idx_max = list_A_np.argmax()
    # list_A_np[idx_max] = int(list_A_np[idx_max]/2)

ans = 0

for i in range(N):
    # ans += list_A[i]
    # ans += list_A_np[i]
    # ans += hq.pop
    ans += heapq.heappop(list_A)

print(-ans)