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

n, m = [int(i) for i in input().split(" ")]
s = [int(input()) for _ in range(m)]

divider = 10**9 + 7
ans = [0]*(n + 1)
ans[0] = 1
ans[1] = 1
l = list(range(2, n+1))

if 1 in s:
    ans[1] = 0
    s.remove(1)


for i in s:
    l.remove(i)   

for i in l:
    ans[i] = ans[i-1] + ans[i-2]
    
   
print(ans[n] % divider)

### FIXED CODE ###

n, m = [int(i) for i in input().split(" ")]

l = list(range(1, n+1))
divider = 10**9 + 7
ans = [0]*(n + 1)
broken = [False]*(n+1)
ans[0] = 1
ans[1] = 1

for i in range(m):
    a = int(input())
    broken[a] = True
    if a == 1:
        ans[1] = 0
    
for i in range(2,n+1):
    if broken[i] == False:
        ans[i] = ans[i-1] + ans[i-2]
    
   
print(ans[n] % divider)
### BUGGY CODE ###

#!/usr/bin/env python3
s = input()
l = len(s)
ans = 0
for i in range(l):
    for j in range(i + 1, l + 1):
        if int(s[i:j]) % 2019 == 0:
            ans += 1
print(ans)


### FIXED CODE ###

s = input()
l = len(s)
mod = [1] + [0 for _ in range(2019)]
ml = [0 for _ in range(l + 1)]
ans = 0

tmp = 0
for idx, degit in enumerate(s[::-1]):
    m = int(degit) * pow(10, idx, 2019)
    m = (m + tmp) % 2019
    tmp = m
    ans += mod[m]
    mod[m] += 1

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

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

DIV = 10**9+7

def comb(l, r):
    if l == 0:
        return 1
    val = 1
    for i in range(r, r-l, -1):
        val *= i
    for i in range(l, 0, -1):
        val //= i
    return val

def calc_rec_num(N, M, xi, xj, yi, yj):
    cnt = 1
    cnt *= N - yi
    cnt *= M - yj
    # rotate
    if xi != yi and xj != yj:
        cnt *= 2
    return cnt


p = comb(K-2, N*M-2)
#print(K-2, N*M-2, p)
ans = 0
for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            continue
        d = i+j
        #print(i, j, calc_rec_num(N, M, 0, 0, i, j))
        ans += d * calc_rec_num(N, M, 0, 0, i, j)
        #if ans > DIV:
        #    ans %= DIV
        #print(ans)

print((ans*p)%DIV)


### FIXED CODE ###

from math import factorial
N, M, K = map(int, input().split())

MOD = 10**9+7

fact = [1] * (N*M+1)
for i in range(2, N*M+1):
    fact[i] = fact[i-1] * i % MOD

def comb(n, r):
    r = n-r if n-r < r else r
    return fact[n] * pow(fact[r], MOD-2, MOD) * pow(fact[n-r], MOD-2, MOD) % MOD

p = comb(N*M-2, K-2)
ans = 0
for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            continue
        d = i+j
        cnt = (N-i) * (M-j)
        if i != 0 and j != 0:
            cnt *= 2
        ans += d * cnt % MOD
ans = ans * p % MOD

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

n, k, q = map(int, input().split())
score_card = [k for _ in range(n)]
for i in range(q):
    tmp = int(input())
    for j in range(len(score_card)):
        if j + 1 == tmp:
            pass
        else:
            score_card[j] = score_card[j] - 1

for i in score_card:
    if i > 0:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

n, k, q = map(int, input().split())
score_list = [k-q for _ in range(n)]
for i in range(q):
    tmp = int(input())
    score_list[tmp - 1] = score_list[tmp - 1] + 1

for j in score_list:
    if j > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import copy
from functools import lru_cache
import math
def resolve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    for k in range(K):
        #print("i", i)
        B = [0] * N
        for i in range(N):
            l = max(0, i - A[i])
            r = min(i + A[i], N-1)
            B[l] += 1
            if r+1 < N:
                B[r+1] -= 1

        for i in range(1, N):
            B[i] += B[i - 1] 

        A = copy.deepcopy(B)

        if min(A) == N:
            break

    print(" ".join(map(str, B)))

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

import copy
from functools import lru_cache
import numpy as np
from numba import njit

#@njit
# @njit('(i8[::1],)', cache=True)
# def func(A):
#     N = len(A)
#     B = np.zeros_like(A)
#     for i in range(N):
#         l = max(0, i - A[i])
#         r = min(i + A[i], N-1)
#         B[l] += 1
#         if r+1 < N:
#             B[r+1] -= 1

#     B = np.cumsum(B)
#     return B

def resolve():
    N, K = map(int, input().split())
    A = np.array(list(map(int, input().split())))

    # N = 2 * 10**5
    # K = 2 * 10**5
    # A = np.array([0] *  N)

    @njit
    def func(A):
        #N = len(A)
        B = np.zeros_like(A)
        for i in range(N):
            l = max(0, i - A[i])
            r = min(i + A[i], N-1)
            B[l] += 1
            if r+1 < N:
                B[r+1] -= 1

        B = np.cumsum(B)
        return B

    for k in range(K):
        #print(k)
        A = func(A)
        if k >= 50:
            break

    print(" ".join(map(str, A)))

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

comp = 0
def merge(A, left, right):
    global comp
    if not left +1 < right:
        return [A[left]]
    mid = (left + right) // 2
    L = merge(A, left, mid)
    R = merge(A, mid, right)
    result = []
    i = j = 0
    while i < len(L) and j < len(R):
        comp += 1
        if L[i] <= R[j]:
            result.append(L[i])
            i += 1
        else:
            result.append(R[j])
            j += 1
    while i < len(L):
        comp += 1
        result.append(L[i])
        i += 1
    while j < len(R):
        comp += 1
        result.append(R[j])
        j += 1
    return result
n = int(input())
*A, = map(int, input().split())
B = merge(A, 0, n)
print(*B)
print(comp)

### FIXED CODE ###

comp = 0
def m(L, R):
    global comp
    j = 0
    for l in L:
        while j < len(R) and R[j] < l:
            yield R[j]
            j += 1
        yield l
    while j < len(R):
        yield R[j]
        j += 1
    comp += len(L) + len(R)
def merge(A):
    global comp
    if len(A) == 1:
        return A
    if len(A) == 2:
        comp += 2
        a, b = A
        return A if a < b else (b, a)
    mid = len(A) // 2
    A[:] = m(merge(A[:mid]), merge(A[mid:]))
    return A

n, *A = map(int, open(0).read().split())
B = merge(A)
print(*B)
print(comp)
### BUGGY CODE ###

n = int(input())
s = list(input())
x = 10000000
for i in range(n):
  a = s[:i]
  b = s[i+1:]
  c = a.count("W")+b.count("E")
  if x>c:
    x = c
print(x)

### FIXED CODE ###

n = int(input())
s = list(input())
a = []
a.append(s[1:].count("E"))
for i in range(n-1):
    if s[i+1] == "E" and s[i] == "E":
        a.append(a[i]-1)
    elif s[i+1] == "W" and s[i] == "E":
        a.append(a[i])
    elif s[i+1] == "E" and s[i] == "W":
        a.append(a[i])
    elif s[i+1] == "W" and s[i] == "W":
        a.append(a[i]+1)
print(min(a))
### BUGGY CODE ###

import sys

#+++++

def pp_in():
	s=input()
	return '#'+s+'#'
		
def main():
	h , w = map(int, input().split())
	mm=[pp_in() for _ in range(h)]
	ap='#'*(w+2)
	mm=[ap]+mm
	mm.append(ap)
	
	rr=[[[0,0] for _ in range(w+2)] for __ in range(h+2)]
	
	if isTest:
		for r in rr:
			print(r)
		for m in mm:
			print(m)
	
	for hi, hm in enumerate(mm):
		start=-1
		for wj, wc in enumerate(hm):
			if wc == '.' and start == -1:
				#it's new '.' pos.
				start=wj
			elif wc == '.':
				pass
			elif wc == '#' and start == -1:
				pass
			else:
				lb = wj - start
				for ii in range(start, wj):
					rr[hi][ii][0] = lb
				start=-1
	
	for wi in range(w+2):
		start=-1
		for hj in range(h+2):
			cc=mm[hj][wi]
			if cc == '.' and start == -1:
				#it's new '.' pos.
				start=hj
			elif cc == '.':
				pass
			elif cc == '#' and start == -1:
				pass
			else:
				lb = hj - start
				for ii in range(start, hj):
					rr[ii][wi][1] = lb
				start=-1
	
	if isTest:
		for r in rr:
			print(r)
			
	p_ret=max([max([sum(vv) for vv in r]) for r in rr])
	ret=p_ret-1
	return ret

	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys

#+++++

		
def main():
	h , w = map(int, input().split())
	mm=[input() for _ in range(h)]
	
	rr_lr=[[0]*(w) for _ in range(h)]
	rr_rl=[[0]*(w) for _ in range(h)]
	rr_ud=[[0]*(w) for _ in range(h)]
	rr_du=[[0]*(w) for _ in range(h)]
							
	for hi in range(h):
		ll=0
		rl=0
		for wj in range(w):
			if mm[hi][wj] == '.':
				ll+=1
				rr_lr[hi][wj]=ll
			else:
				ll=0				
				
			if mm[hi][w-1-wj] == '.':
				rl+=1
				rr_rl[hi][w-1-wj]=rl
			else:
				rl=0				
					
	for wi in range(w):
		ll=0
		rl=0
		for hj in range(h):
			if mm[hj][wi] == '.':
				ll+=1
				rr_ud[hj][wi]=ll
			else:
				ll=0
				
			if mm[(h-1)-hj][wi] == '.':
				rl+=1
				rr_du[(h-1)-hj][wi]=rl
			else:
				rl=0
				
	ret=0
	for i in range(w):
		for j in range(h):
			vv=rr_lr[j][i]-3
			vv+=rr_rl[j][i]
			vv+=rr_du[j][i]
			vv+=rr_ud[j][i]
			ret = max(ret,vv)
	
	return ret

	
#+++++

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
### BUGGY CODE ###

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

for i in range(k):
  if a >0:
    a -=1
  else:
    b -=1
    
print(str(a) + " " +str(b))



### FIXED CODE ###

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

newk = k-a
if newk >= 0:
  a = 0
  b = b-newk
  if b <= 0:
    print(str(0) + " " +str(0))
  else:
    print(str(0) + " " + str(b))
else:
  a = a-k
  print(str(a) + " " +str(b))
### BUGGY CODE ###

from collections import deque
INF = float("inf")

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch, cw = ch-1, cw-1
dh, dw = dh-1, dw-1
S = [input() for _ in range(h)]

dist = [[INF] * w for _ in range(h)]
dist[ch][cw] = 0
q = deque([(cw, ch)])

while q:
    x, y = q.popleft()
    for _x in range(-2, 3):
        for _y in range(-2, 3):
            if _x == _y == 0:
                continue
            next_x, next_y = x + _x, y + _y
            if not 0 <= next_x < w:
                continue
            if not 0 <= next_y < h:
                continue
            if S[next_y][next_x] == "#":
                continue
            if abs(_x) + abs(_y) <= 1:
                if dist[next_y][next_x] <= dist[y][x]:
                    continue
                q.appendleft((next_x, next_y))
                dist[next_y][next_x] = dist[y][x]
            else:
                if dist[next_y][next_x] <= dist[y][x] + 1:
                    continue
                q.append((next_x, next_y))
                dist[next_y][next_x] = dist[y][x] + 1

if dist[dh][dw] != INF:
    print(dist[dh][dw])
else:
    print(-1)


### FIXED CODE ###

from collections import deque
INF = float("inf")

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch, cw = ch-1, cw-1
dh, dw = dh-1, dw-1
S = [input() for _ in range(h)]

dist = [[INF] * w for _ in range(h)]
dist[ch][cw] = 0
q = deque([(cw, ch)])

while q:
    x, y = q.popleft()
    for _x in range(-2, 3):
        for _y in range(-2, 3):
            if _x == _y == 0:
                continue
            next_x, next_y = x + _x, y + _y
            if not 0 <= next_x < w:
                continue
            if not 0 <= next_y < h:
                continue
            if S[next_y][next_x] == "#":
                continue
            if abs(_x) + abs(_y) <= 1:
                if dist[next_y][next_x] <= dist[y][x]:
                    continue
                q.appendleft((next_x, next_y))
                dist[next_y][next_x] = dist[y][x]
            else:
                if dist[next_y][next_x] <= dist[y][x] + 1:
                    continue
                q.append((next_x, next_y))
                dist[next_y][next_x] = dist[y][x] + 1

if dist[dh][dw] != INF:
    print(dist[dh][dw])
else:
    print(-1)
### BUGGY CODE ###

from collections import Counter

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

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

div_l = []
for i in range(n):
    for j in make_divisors(a[i]):
        div_l.append(j)

dict = Counter(div_l)
ans = [k for k, v in dict.items() if v >= n - 1]
print(max(ans))

### FIXED CODE ###

from fractions import gcd

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

left = [0 for _ in range(n + 1)]
right = [0 for _ in range(n + 1)]
for i in range(n):
    left[i + 1] = gcd(left[i], a[i])

for i in reversed(range(n)):
    right[i] = gcd(right[i + 1], a[i])

ans = 0
for i in range(n):
    l = left[i]
    r = right[i+1]
    ans = max(ans, gcd(l, r))

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

N,M=map(int,input().split())
H=[int(i) for i in input().split()]
A=[0]*M
B=[0]*M
for i in range(M):
    A[i],B[i]=map(int,input().split())
C=[i+1 for i in range(N)]

for i in range(M):

    if(H[A[i]-1]>H[B[i]-1]):
        d=[-1,B[i]]
        C=list(set(C)-set(d))

    elif(H[A[i]-1]<H[B[i]-1]):
        d=[-1,A[i]]
        C=list(set(C)-set(d))
    else:
        d=[-1,A[i]]
        dd=[-1,B[i]]
        C=list(set(C)-set(d)-set(dd))

print(len(C))


### FIXED CODE ###

N,M=map(int,input().split())
H=[int(i) for i in input().split()]
A=[0]*M
B=[0]*M
for i in range(M):
    A[i],B[i]=map(int,input().split())
D=[i+1 for i in range(N)]
C=[]
for i in range(M):

    if(H[A[i]-1]>H[B[i]-1]):

        C.append(B[i])

    elif(H[A[i]-1]<H[B[i]-1]):

        C.append(A[i])
    else:

        C.append(A[i])
        C.append(B[i])

G=list(set(D)-set(C))
print(len(G))
### BUGGY CODE ###

import bisect

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

l.sort()

ans = 0

for i in range(1, n - 1):
  for j in range(i + 1, n):
    if l[i] * 2 > l[j]:
      idx = bisect.bisect_left(l, l[j] - l[i] + 0.5)
      ans += max(i - idx, 0)

print(ans)

### FIXED CODE ###

import bisect

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

l.sort()

ans = 0

for i in range(1, n - 1):
  for j in range(i + 1, n):
    if l[i] * 2 > l[j]:
      idx = bisect.bisect_left(l, l[j] - l[i] + 0.5)
      ans += max(i - idx, 0)

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

import sys
N, K = list(map(int,input().split()))

ans = 1e+19

while True:
    N = abs(N-K)
    if N >= ans:
        break
    ans = N

print(ans)


### FIXED CODE ###

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

ans = min(N%K, K-(N%K))

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

import numpy as np

num = input()
num = int(num)

str = input()
list_in = str.split()

count_arr = np.zeros((num+1))
sum_arr = np.zeros((num+1))

for item in list_in:
    count_arr[int(item)] += 1

sum = 0
for i in range(len(count_arr)):
    tmp = count_arr[i]
    tmp = (tmp * (tmp -1))
    sum += tmp
    sum_arr[i] = tmp

for item in list_in:
    tmp = int(item)
    old_sum = sum_arr[tmp]
    tmp = count_arr[tmp] - 1
    tmp = (tmp * (tmp -1))
    result = (sum - old_sum + tmp)/2
    print(int(result))


### FIXED CODE ###

import numpy as np

num = input()
num = int(num)

str = input()
list_in = list(map(int, str.split()))

count_arr = [0]*num

for item in list_in:
    count_arr[item-1] += 1

sum = 0
for i in range(num):
    tmp = count_arr[i-1]
    tmp = (tmp * (tmp -1))//2
    sum += tmp

for item in list_in:
    tmp = count_arr[item-1]
    result = sum - (tmp - 1)
    print(result)
### BUGGY CODE ###

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

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

a = sorted(a)
f = sorted(f, reverse=True)

def judge(n):
    s = 0
    for x, y in zip(a, f):
        s += max(0, x - n // y)
    if s <= k:
        return True
    else:
        return False

low = 0
high = a[-1] * f[0]
while high - low > 0:
    mid = (high + low) // 2
    if judge(mid):
        high = mid
    else:
        low = mid + 1
print(high)

### FIXED CODE ###

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

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

a = sorted(a)
f = sorted(f, reverse=True)

def judge(n):
    s = 0
    for x, y in zip(a, f):
        s += max(0, x - n // y)
    if s <= k:
        return True
    else:
        return False

low = 0
high = a[-1] * f[0]
while high - low > 0:
    mid = (high + low) // 2
    if judge(mid):
        high = mid
    else:
        low = mid + 1
print(high)
### BUGGY CODE ###

from bisect import bisect_left
n = int(input())
x_d = []
for _ in range(n):
    x_d.append(tuple(map(int, input().split())))
x_d.sort(key=lambda t: t[0])
x = [t[0] for t in x_d]
xplusd = [t[0] + t[1] for t in x_d]
shortright = [bisect_left(x, xpdi) for xpdi in xplusd]
right = [t for t in shortright]
for i in range(n - 1, -1, -1):
    right[i] = max(right[i : right[i]])
dp = [None] * n
dp.append(1)
for i in range(n - 1, -1, -1):
    dp[i] = (dp[i + 1] + dp[right[i]]) % 998244353
print(dp[0])

### FIXED CODE ###

import sys
input = sys.stdin.readline
from bisect import bisect_left

class SegTree:
    def __init__(self, a):
        self.padding = -float('inf')
        self.n = len(a)
        self.N = 2 ** (self.n - 1).bit_length()
        self.data = [self.padding]*(self.N - 1) + a + [self.padding]*(self.N - self.n)
        for i in range(2 * self.N - 2, 0, -2):
            self.data[(i - 1) // 2] = max(self.data[i], self.data[i - 1])
    
    def __len__(self):
        return self.n
    
    def __getitem__(self, key):
        return self.data[self.N - 1 + key]

    def __setitem__(self, i, value):
        self._update(i, value)
    
    def _update(self, i, x):
        idx = self.N - 1 + i
        self.data[idx] = x
        while idx != 0:
            idx = (idx - 1) // 2
            self.data[idx] = max(self.data[2 * idx + 1], self.data[2 * idx + 2])
    
    def max(self, i, j):
        # [i, j)
        if i == j: #今回のみの措置
            return self.data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j # 閉区間にする
            result = self.padding
            while idx1 + 1 < idx2:
                if idx1 % 2 == 0: # idx1が偶数
                    result = max(result, self.data[idx1])
                if idx2 % 2 == 1: # idx2が奇数
                    result = max(result, self.data[idx2])
                    idx2 -= 1
                
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            
            if idx1 == idx2:
                result = max(result, self.data[idx1])
            else: # idx1 + 1 == idx2
                result = max(result, self.data[idx1], self.data[idx2])
            
            return result

n = int(input())
x_d = []
for _ in range(n):
    x_d.append(tuple(map(int, input().split())))
x_d.sort(key=lambda t: t[0])
x = [t[0] for t in x_d]
xplusd = [t[0] + t[1] for t in x_d]
shortright = [bisect_left(x, xpdi) for xpdi in xplusd]
right = SegTree([t for t in shortright])
for i in range(n - 1, -1, -1):
    right[i] = right.max(i, right[i])
dp = [None] * n
dp.append(1)
for i in range(n - 1, -1, -1):
    dp[i] = (dp[i + 1] + dp[right[i]]) % 998244353
print(dp[0])
### BUGGY CODE ###

K = int(input())

def gcd(m,n):
    x=max(m,n)
    y=min(m,n)
    if x%y==0:
        return y
    else:
        while x%y!=0:
            z=x%y
            x=y
            y=z
        return z

b_list=[]
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            a=gcd(i,j)
            b=gcd(a,k)
            b_list.append(b)
print(sum(b_list))

### FIXED CODE ###

K = int(input())
import math
b_list=[]
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            a=math.gcd(i,j)
            b=math.gcd(a,k)
            b_list.append(b)
print(sum(b_list))
### BUGGY CODE ###

N,Q=[int(s) for s in input().split()]
edge=[set() for _ in range(N)]
value=[0 for _ in range(N)]
for i in range(N-1):
  x,y=[int(s) for s in input().split()]
  edge[x-1].add(y-1)
  edge[y-1].add(x-1)
for i in range(Q):
  x,y=[int(s) for s in input().split()]
  value[x-1]+=y
stack=[0]
while stack:
  vrt=stack.pop(0)
  for to in edge[vrt].copy():
    stack.append(to)
    value[to]+=value[vrt]
    edge[vrt].discard(to)
    edge[to].discard(vrt)
print(*value)


### FIXED CODE ###

N,Q=[int(s) for s in input().split()]
#辺でつながれた場所をすべてリストアップ
con_list=[set() for s in range(N+1)]
for i in range(N-1):
  a,b=[int(s) for s in input().split()]
  con_list[a].add(b)
  con_list[b].add(a)

v_list=[0 for s in range(N+1)]
for i in range(Q):
  x,y=[int(s) for s in input().split()]
  v_list[x]+=y

position=1 #現在位置
counter=v_list[1] #カウンター
ans_list=[0 for s in range(N+1)] #答え
ans_list[1]=counter 
vertex_num=1 #訪れた場所の数
oya_list=[-1 for s in range(N+1)] #親に戻るためのリスト

while vertex_num<N:
  #まだ行っていない子があるか？
  if len(con_list[position])>0:
    x=con_list[position].pop()
    con_list[x].remove(position) #xの行先から親を消す
    oya_list[x]=position
    position=x
    counter+=v_list[position] #カウンターの更新
    ans_list[position]=counter
    vertex_num+=1
  else: #行き先がないなら戻る
    position=oya_list[position]
    counter=ans_list[position] #カウンターを戻す
print(*ans_list[1:])
### BUGGY CODE ###

A = input("")
num = 1
for i in range(len(A)-1):
	num += len(A[i+1:].replace(A[i],''))
print(num)

### FIXED CODE ###

def conbi(n):
	return int(n*(n-1)/2)

A = input("")
num = 1 + conbi(len(A)) #l_C_2
uniq = list(set(A))
for i in uniq:
	num -= conbi(A.count(i))
print(num)
### BUGGY CODE ###

N, K = map(int, input().split())
hlist = []
for i in range(N):
    hlist.append(int(input()))

import numpy as np
dlist = np.diff(np.sort(hlist))

ans = []
for i in range(len(dlist)-1):
    ans.append(sum(dlist[i:i+K-1]))
print(min(ans))

### FIXED CODE ###

N, K = map(int, input().split())
hlist = []
for i in range(N):
    hlist.append(int(input()))

import numpy as np
hlist = np.sort(hlist)

ans = 10**10
for i in range(N-K+1):
    ans = min(ans, hlist[i+K-1]-hlist[i])
print(ans)
### BUGGY CODE ###

import math
k=int(input())
ans=0

for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            d=math.gcd(i,j)
            ans+=math.gcd(d,l)
print(ans)

### FIXED CODE ###

import math
k=int(input())
ans=0

for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            d=math.gcd(i,j)
            ans+=math.gcd(d,l)
print(ans)
### BUGGY CODE ###

def main():
    S = input()
    Q = int(input())
    queries = [input() for _ in range(Q)]

    reverse = False

    for e in queries:
        if e[0] == '1':
            reverse = not reverse
        else:
            T, F, C = e.split()
            if F == '2': F = True
            else: F = False

            if reverse ^ F:
                # 末尾に追加
                S += C
            else:
                # 先頭に追加
                S = C + S
        # print(S)

    if reverse:
        S = S[::-1]

    print(S)



if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    S = input()
    Q = int(input())
    queries = [input() for _ in range(Q)]

    reverse = False
    front = ""

    for e in queries:
        if e[0] == '1':
            reverse = not reverse
        else:
            T, F, C = e.split()
            if F == '2': F = True
            else: F = False

            if reverse ^ F:
                # 末尾に追加
                S += C
            else:
                # continue
                # 先頭に追加，ここの計算がボトルネック
                front += C
        # print(S)

    if reverse:
        S = S[::-1]
        S = S + front
    else:
        S = front[::-1] + S

    print(S)
    

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

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

"""
A.sort(reverse=True)

for m in range(M):
    A[m] //= 2
    A.sort()
    #print(A)

print(sum(A))
"""

for i in range(M):
    m = A.index(max(A))
    A[m] //= 2
    #print(A)

print(sum(A))

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(A)

#print(A)

for _ in range(M):
    m = heapq.heappop(A)
    #print(m)
    heapq.heappush(A, -(-m // 2))
    #print(A)

print(-sum(A))