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

from collections import Counter
import itertools

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

n, x, y = map(int, input().split())
d = [[n]*n for i in range(n)] 

for i in range(n-1):
    d[i][i+1] = 1
    d[i+1][i] = 1
d[x-1][y-1] = 1
d[y-1][x-1] = 1
for i in range(n):
    d[i][i] = 0
warshall_floyd(d)
D = Counter(list(itertools.chain.from_iterable(d)))
for i in range(1, n):
    print(D[i]//2)

### FIXED CODE ###

import collections
n, x, y = map(int, input().split())
d = [[0]*(i+1) for i in range(n)]
x -= 1
y -= 1
for i in range(n):
    for j in range(i+1):
        d[i][j] = min(i-j, abs(x-j)+abs(y-i)+1)
L = []
for i in range(n):
    for dd in d[i]:
        L.append(dd)
C = collections.Counter(L)
for i in range(1, n):
    print(C[i])
### BUGGY CODE ###

n=int(input())
c=list(map(int,input().split()))
for i in range(1,n):
    print(c.count(i))
print(0)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
d = dict()
for i in range(n):
    d[i] = 0
for e in a:
    d[e-1] += 1
for i in range(n):
    print(d[i])
### BUGGY CODE ###

import sys
import math


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    L = [[] for _ in range(K)]
    for t in range(K):
        l, r = map(int, input().split())
        for j in range(l, r + 1):
            L[t].append(j)

    lc = [0] * K
    mod = 998244353

    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(1,N+1):

        for k in range(K):
            CL =L[k]
            if len(CL)==1:
                lc[k]=dp[i-CL[0]]
            else:
                if CL[-1] > i:
                    lc[k] = sum(dp[:max(0,1+ i-CL[0])]) %mod
                else:
                    lc[k] =( lc[k] + dp[i - L[k][0]] - dp[i - L[k][-1]-1] )%mod
            dp[i] += lc[k]



    print(dp[N - 1]%mod)


if __name__ == "__main__":
    main()

# \n


### FIXED CODE ###

import sys
import math


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    L = [[] for _ in range(K)]
    for t in range(K):
        l, r = map(int, input().split())
        for j in range(l, r + 1):
            L[t].append(j)

    lc = [0] * K
    mod = 998244353

    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(1,N+1):

        for k in range(K):
            CL =L[k]
            if len(CL)==1:
                lc[k]=dp[i-CL[0]] %mod
            else:
                if CL[-1] > i:
                    lc[k] = lc[k] %mod +dp[i-L[k][0]] %mod
                else:
                    lc[k] =( lc[k] + dp[i - L[k][0]] - dp[i - L[k][-1]-1] )%mod
            dp[i] += lc[k]



    print(dp[N - 1]%mod)


if __name__ == "__main__":
    main()

# \n
### BUGGY CODE ###

# 木上の累積和

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


from collections import defaultdict

N, Q = read_ints()
tree = defaultdict(lambda: [])
for _ in range(N - 1):
    a, b = read_ints()
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)
cnt = [0] * N
for _ in ra(Q):
    q, x = read_ints()
    cnt[q - 1] += x

# dfsでcntに木に沿った累積和をsetしていく


def dfs(c, u, p):  # uは現在のノード、pは親のノード、cはuは含まない累積のスコア
    cnt[u] += c
    for nv in tree[u]:
        if nv == p:
            continue
        dfs(cnt[u], nv, u)


dfs(0, 0, -1)

print(*cnt)


### FIXED CODE ###

# https://atcoder.jp/contests/abc138/tasks/abc138_d
# 下に数を最初に合計してから深さ優先探索なり、幅優先探索なりで下にカウンターを伝播させていけば良い。
# 累積和の木構造バージョン


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


# 再帰の上限を緩和する(引数は適当)
import sys
sys.setrecursionlimit(1 << 25)
from collections import defaultdict

N, Q = read_ints()
child = defaultdict(lambda: [])  # ノード0は存在しない
score = [0] * (N + 1)
for _ in range(N - 1):
    a, b = read_ints()
    child[a].append(b)
    child[b].append(a)
for _ in range(Q):
    p, x = read_ints()
    score[p] += x

# 木を走査しながらscoreを合計していく
ans = [0] * (N + 1)


def dfs(p, u, s):  # ノードuの親pにおけるスコアs
    s += score[u]
    ans[u] = s
    for c in child[u]:
        if p == c:
            continue
        dfs(u, c, s)


dfs(-1, 1, 0)
print(*ans[1:])
### BUGGY CODE ###

H,W = map(int, input().split())
field = [list(input()) for _ in range(H)]
dy = [1,-1,0,0]
dx = [0,0,1,-1]


queues = []
# sy,sx = 0,0
# gy,gx = H-1,W-1
seen = [[0 for i in range(W)] for j in range(H)]
for i in range(H):
    for j in range(W):
        if field[i][j] == '#':
            seen[i][j] = 1
            queues.append([[i,j]])
# queue = [[sy,sx]]
flag = False
count = 0
while flag == False:
    count += 1
    for ix, queue in enumerate(queues):
        if queue == []:
            continue
        h,w = queue.pop(0)
        for i in range(4):
            nh = h + dy[i]
            nw = w + dx[i]
            # if (nh == gy) and (nw == gx):
            #     count = before+1
            #     flag = True
            if (0<=nh<H) and (0<=nw<W):
                if field[nh][nw] != '#':
                    if seen[nh][nw] == 0:
                        seen[nh][nw] = 1
                        queue.append([nh,nw])
        queues[ix] = queue
    has_zero = False
    for i in range(H):
        for j in range(W):
            if seen[i][j] == 0:
                has_zero = True
                break
        if has_zero:
            break
    if has_zero == False:
        flag = True
    
        # if flag:
        #     break
print(count-1)

### FIXED CODE ###

from collections import deque
import copy

def main():
    h, w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]


    # スタート地点をqueueに追加
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))

        if nque:
            que = copy.copy(nque)
        else:
            break

    print(count - 1)

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

a, b, k = map(int, input().split())
for i in range(k):
    if a >= 1:
        a -= 1
    elif b >= 1:
        b -= 1
    else:
        pass
print(a, b)

### FIXED CODE ###

a, b, k = map(int, input().split())
a1 = a
b1 = b
if k <= a:
    a1 -= k
elif k <= a + b:
    a1 = 0
    b1 -= k - a
else:
    a1 = 0
    b1 = 0
print(a1, b1)
### BUGGY CODE ###

n=int(input())
p=[int(x) for x in input().split()]


result=0

for pp in p:
    flag=True
    buf=p[0:pp]
    for bb in buf:
        if bb < p[pp-1]:
            flag=False
            break
    if flag==True:
        result+=1
        
print(result)
    

### FIXED CODE ###

n=int(input())
p=[int(x) for x in input().split()]


result=0

mm = 10**11

for pp in p:
    if pp <= mm:
        mm=pp
        result+=1

print(result)
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    xy = [list(map(int, input().split())) for i in range(N)]
    # 座標圧縮
    xs = []
    ys = []
    xy = sorted(xy, key=lambda x: x[0])
    for i in range(N):
        xs.append(xy[i][0])
        xy[i][0] = i+1
    xy = sorted(xy, key=lambda x: x[1])
    for i in range(N):
        ys.append(xy[i][1])
        xy[i][1] = i+1
    # 2次元累積和
    sum_ = np.zeros((N+1, N+1), dtype=int)
    for i in range(N):
        x, y = xy[i]
        sum_[y][x] = 1
    for i in range(1, N+1):
        sum_[i] += sum_[i-1]
    for i in range(1, N+1):
        sum_[:,i] += sum_[:,i-1]
    # 全探索
    ans = int(1e20)
    for l in range(1, N+1):
        no_three = True
        for r in range(N, l, -1):
            no_two = True
            for d in range(1, N+1):
                no_one = True
                for u in range(N, d, -1):
                    tmp = sum_[u][r] - sum_[d-1][r] - sum_[u][l-1] + sum_[d-1][l-1]
                    if tmp >= K:
                        tmp = (xs[r-1] - xs[l-1]) * (ys[u-1] - ys[d-1])
                        ans = min(ans, tmp)
                        no_one = False
                    else:
                        break
                if no_one:
                    break
                else:
                    no_two = False
            if no_two:
                break
            else:
                no_three = False
        if no_three:
            break
                

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    xy = [list(map(int, input().split())) for i in range(N)]
    # 座標圧縮
    xs = []
    ys = []
    xy = sorted(xy, key=lambda x: x[0])
    for i in range(N):
        xs.append(xy[i][0])
        xy[i][0] = i+1
    xy = sorted(xy, key=lambda x: x[1])
    for i in range(N):
        ys.append(xy[i][1])
        xy[i][1] = i+1
    # 2次元累積和
    sum_ = np.zeros((N+1, N+1), dtype=int)
    for i in range(N):
        x, y = xy[i]
        sum_[y][x] = 1
    for i in range(1, N+1):
        sum_[i] += sum_[i-1]
    for i in range(1, N+1):
        sum_[:,i] += sum_[:,i-1]
    # 全探索
    ans = int(1e20)
    for l in range(1, N+1):
        no_three = True
        for r in range(N, l, -1):
            no_two = True
            for d in range(1, N+1):
                no_one = True
                for u in range(d+1, N+1):
                    tmp = sum_[u][r] - sum_[d-1][r] - sum_[u][l-1] + sum_[d-1][l-1]
                    if tmp >= K:
                        tmp = (xs[r-1] - xs[l-1]) * (ys[u-1] - ys[d-1])
                        ans = min(ans, tmp)
                        no_one = False
                        break
                if no_one:
                    break
                else:
                    no_two = False
            if no_two:
                break
            else:
                no_three = False
        if no_three:
            break
                

    print(ans)

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

n, m = map(int, input().split())
mod = 1000000007
d = 1
divisor = []
while d * d <= m:
    if m % d == 0:
        divisor.append(d)
        if d != m // d:
            divisor.append(m // d)
    d += 1
divisor = sorted(divisor)
l = len(divisor)
matrix = [[0] * l for _ in range(l)]
for i in range(l):
    for j in range(l):
        matrix[i][j] = 1 if divisor[i] % divisor[j] == 0 else 0

dp = [1] * l
t = n - 1
while t > 0:
    if t % 2 == 1:
        newdp = [0] * l
        for i in range(l):
            for j in range(l):
                newdp[i] = (newdp[i] + matrix[i][j] * dp[j]) % mod
        dp = newdp
    newmatrix = [[0] * l for _ in range(l)]
    for i in range(l):
        for j in range(l):
            newmatrix[i][j] = sum(matrix[i][k] * matrix[k][j] for k in range(l)) % mod
    matrix = newmatrix
    t //= 2

print(dp[-1])


### FIXED CODE ###

n, m = map(int, input().split())
mod = 1000000007

def cmb(n, k):
    ret = 1
    for i in range(k):
        ret *=  n - i
        ret //= i + 1
    return ret % mod

primes = [2]
for p in range(3, 1000):
    if all(p % q for q in primes):
        primes.append(p)

ret = 1
for p in primes:
    q = 0
    while m % p == 0:
        m //= p
        q += 1
    if q > 0:
        ret = (ret * cmb(n + q - 1, q)) % mod
if m > 1:
    ret = (ret * cmb(n, 1)) % mod

print(ret)
### BUGGY CODE ###

def divisible(n):
    ans = 0
    while n%2 == 0:
        n /=2
        ans +=1
    return ans

N = int(input())

a = []

for i in range(N):
    a.append(divisible(i))
    
print(max(a))

### FIXED CODE ###

def divisible(n):
 ans = 0
 while n%2 == 0:
  n /= 2
  ans += 1
 return ans
 
N = int(input())
 
b = 0

c = 1
 
for i in range(1,N+1):
    if(divisible(i) > b):
      b = divisible(i)
      c = i
    
print(c)
### BUGGY CODE ###

s = input()
K = int(input())
n = len(s)
char_list = []
for i in range(n):
    if s[i] not in char_list:
        char_list.append(s[i])
char_list.sort()
# print(char_list)

cnt = 0
str_list = []
for i in range(len(char_list)):
    for j in range(n):
        if s[j] == char_list[i]:
            for k in range(j, n + 1):
                str_list.append(s[j:k + 1])
    if len(list(set(str_list))) < K:
        continue
    else:
        str_list = list(set(str_list))
        str_list.sort()
        print(str_list[K - 1])
        # print(str_list)
        exit()


### FIXED CODE ###

s = input()
K = int(input())
str_list = []
for i in range(len(s)):
    for j in range(K):
        str_list.append(s[i:i + j + 1])
str_list = sorted(list(set(str_list)))
# print(str_list)
ans = str_list[K - 1]
print(ans)
### BUGGY CODE ###

N = int(input())
P = [list(map(int, input().split())) for _ in range(N)]

P.sort(key=lambda x: x[0]+x[1])

leave = []
for i in range(N):
    # ロボットpiが既に残すと決めたロボットに重ならないことをチェック
    # print('Checking Robot P{}: {}'.format(i, P[i])) 
    # print('S:{} P:{} T:{}'.format(P[i][0]-P[i][1], P[i][0] , P[i][0]+P[i][1]))
    
    if len(list([leave_ for leave_ in leave if leave_[0] + leave_[1] > P[i][0] - P[i][1]])) == 0:
        leave.append(P[i])
        #print(leave)
    else:
        #print('Not Added')
        #print(leave)
        continue

print(len(leave))

### FIXED CODE ###

N = int(input())
P = [list(map(int, input().split())) for _ in range(N)]

P.sort(key=lambda x: x[0]+x[1])

leave = [P[0]]
for i in range(1, N):
    # leaveの最大を取得
    leave_max = leave[-1][0] + leave[-1][1]
    p_min = P[i][0] - P[i][1]
    if leave_max <= p_min:
        leave.append(P[i])
    else:
        continue
        
print(len(leave))
### BUGGY CODE ###

N = int(input())

a_dict = {}

for i in range(1, N+1):
	a_dict[i] = int(input())

answer = 0
now_point = 1
check_list = [1]

for i in range(N):
	now_point = a_dict[now_point]
	answer += 1
	if now_point == 2:
		break

	if now_point in check_list:
		answer = -1
		break
	check_list.append(now_point)

print(answer)

### FIXED CODE ###

N = int(input())

a_dict = {}

for i in range(1, N+1):
	a_dict[i] = int(input())

answer = 0
now_point = 1

for i in range(N):
	now_point = a_dict[now_point]
	answer += 1
	if now_point == 2:
		print(answer)
		break

if now_point != 2:
	print(-1)
### BUGGY CODE ###

from collections import Counter
n = int(input())
str_list = [input() for i in range(n)]
ans = 0
for i in range(n):
  for j in range(n-i-1):
    if Counter(str_list[i])==Counter(str_list[j+i+1]):
      ans +=1
print(ans)

### FIXED CODE ###

from collections import Counter
import sys

input = sys.stdin.readline
n = int(input())
str_list = [''.join(sorted(input().rstrip())) for i in range(n)]
ans = 0
count_list = list(Counter(str_list).values())
for i in count_list:
  sum = 0
  for j in range(int(i)):
    sum += j
  ans +=sum
print(ans)
### BUGGY CODE ###

n = int(input())
s = list(input())
m = n
for i in range(n + 1):
    counts = s[:i].count("#") + s[i:].count(".")
    if m > counts:
        m = counts
        
print(m)

### FIXED CODE ###

n = int(input())
s = list(input())
m = n
counts = s[:].count(".")
m = min(n,counts)
for i in range(n):
    counts += s[i].count("#") - s[i].count(".")
    if m > counts:
        m = counts
        
print(m)
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline
N, M = [int(x) for x in input().split()]
I = []
for _ in range(M):
    I.append([int(x) for x in input().split()])
s_1 = []
s_N = []
for i in I:
    if i[0] == 1 and i[1] == N:
        print("POSSIBLE")
        sys.exit()
    if i[0] == 1:
        s_1.append(i[1])
    if i[1] == N:
        s_N.append(i[0])
for j in s_1:
    if j in s_N:
        print("POSSIBLE")
        sys.exit()
print("IMPOSSIBLE")
    



### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline
N, M = [int(x) for x in input().split()]
I = []
for _ in range(M):
    I.append([int(x) for x in input().split()])
s_1 = set()
s_N = set()
for i in I:
    if i[0] == 1 and i[1] == N:
        print("POSSIBLE")
        sys.exit()
    if i[0] == 1:
        if i[1] in s_N:
            print("POSSIBLE")
            sys.exit()
        s_1.add(i[1])
    if i[1] == N:
        if i[0] in s_1:
            print("POSSIBLE")
            sys.exit()
        s_N.add(i[0])
for j in s_1:
    if j in s_N:
        print("POSSIBLE")
        sys.exit()
print("IMPOSSIBLE")
### BUGGY CODE ###

import re
s=input()
m=0
s1 = re.compile(r'01|10')
l1 = re.compile(r'000111|111000|00001111|11110000|0000011111|1111100000')
for i in range(len(s)//2):
  dst = re.sub(s1, "", s)
  dst = re.sub(l1, "", dst)
  if dst == s:
    break
  m += len(s) - len(dst)
  s=dst
print(m)

### FIXED CODE ###

s=input();print(min(s.count("0"), s.count("1"))*2)
### BUGGY CODE ###

from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def main():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]

    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            required = True
            for k in range(N):
                if k == i or k == j:
                    continue
                if A[i][j] > A[i][k] + A[k][j]:
                    print(-1)
                    return
                if A[i][j] == A[i][k] + A[k][j]:
                    required = False
                    break
            if required:
                ans += A[i][j]

    print(ans)

    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def main():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]

    ans = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if A[i][j] > A[i][k] + A[k][j]:
                    print(-1)
                    return

    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            if all(A[i][j] < A[i][k] + A[k][j] for k in range(N) if k != i and k != j):
                ans += A[i][j]

    print(ans)

    return


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

import math
from functools import reduce
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
K = int(input())
sum = 0
for i in range(1, K+1):
  for j in range(1, K+1):
    for k in range(1, K+1):
      sum += gcd(i,j,k)
print(sum)

### FIXED CODE ###

import math
K=int(input())
ans=0
for i in range(1,K+1):
    for j in range(1,K+1):
        tmp=math.gcd(i,j)
        for k in range(1,K+1):
            ans+=math.gcd(tmp,k)         
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200000)
n = int(input())
li = list(map(int,input().split()))
a = li[0]
del li[0]

def f(num1,num2,l):
  t = num1^num2
  if len(l) == 1 and t in l:
    return True
  else:
    if t in l:
      l.remove(t)
      return f(num2,t,l)
    else:
      return False

for i in li:
  if not a^i in li:
    continue
  else:
    if f(i,a,li[:]):
      print("Yes")
      exit()
    else:continue
print("No")

### FIXED CODE ###

n=int(input())
*a,=map(int,input().split())
s=list(set(a))
s.sort()
ans="No"
if len(s)==1:
  if 0 in s:
    ans="Yes"
elif len(s)==2:
  if a.count(0)*2==a.count(s[1]):
    ans="Yes"
elif len(s)==3 and a.count(s[0])==a.count(s[1])==a.count(s[2]) and s[0]^s[1]^s[2]==0:
  ans="Yes"
print(ans)
### BUGGY CODE ###

import bisect
import math

def dfs(v,visited):
  for u in m2[v]:
    if u in visited:
      continue
    visited.add(u)
    if(n2[u]==-1 or dfs(n2[u],visited)):
      n2[u]=v
      return True
  return False

n=int(input())
a=list(map(int,input().split()))
a.sort()
b=[]
kari=[]
ma=[]
m2=[]
n2=[]
vt=[]
vp=[]
visited=[]
ans=0
for i in range(n):
  kari=[]
  for j in range(20):
    for k in range(bisect.bisect_left(a,2**j-a[i]),bisect.bisect_right(a,2**j-a[i])):
      if(k==i):
        continue
      kari.append(k)
  ma.append(kari)
for i in range(n):
  kari=[]
  for j in ma[i]:
    kari.append(j+n)
  m2.append(kari)
for i in range(2*n):
  n2.append(-1)
print(sum(dfs(s,set())for s in range(n))//2)


### FIXED CODE ###

import collections
import math
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
c=collections.Counter(a)
ans=0
for i in a:
  j=int(math.log2(i))+1
  k=2**j-i
  if k in c.keys():
    if i==k and c[i]>1:
      c[i]-=2
      ans+=1
    elif i!=k and c[i]>0 and c[k]>0:
      c[i]-=1
      c[k]-=1
      ans+=1
print(ans)
### BUGGY CODE ###

import numpy as np

n, k = [int(i) for i in input().split()]
s = input()

ones = [len(x) for x in s.replace('0', ' ').split()]
zeros = [len(x) for x in s.replace('1', ' ').split()]

if s[0]=='0':
  ones = [0] + ones
if s[-1]=='0':
  ones = ones + [0]

if k >= len(zeros):
  result = n
else: 
  result = [
    np.sum(ones[i:i+k+1]) + np.sum(zeros[i:i+k])
    for i in range(len(zeros)) if i+k+1 <= len(ones)]
  result = max(result)

print(result)

### FIXED CODE ###

import numpy as np

n, k = [int(i) for i in input().split()]
s = input()

ones = [len(x) for x in s.replace('0', ' ').split()]
zeros = [len(x) for x in s.replace('1', ' ').split()]

if s[0]=='0':
  ones = [0] + ones
if s[-1]=='0':
  ones = ones + [0]
  
ones = np.array(ones)
zeros = np.array(zeros)

if k >= len(zeros):
  result = n
else: 
  result = [
    np.sum(ones[i:i+k+1]) + np.sum(zeros[i:i+k])
    for i in range(len(zeros)-k+1)]
  result = max(result)

print(result)
### BUGGY CODE ###

#132_E

import queue
import sys
sys.setrecursionlimit(300000)
 
n,m=map(int,input().split())

edges=[[] for i in range(n)]
for _ in range(m):
    u,v=map(int,input().split())
    edges[u-1].append(v-1)
edges_3=[[] for i in range(n)]
for i in range(n):
    for x in edges[i]:
        for y in edges[x]:
            for z in edges[y]:
                edges_3[i].append(z)
    
s,t=map(int,input().split())
s,t=s-1,t-1
    
def bfs(s,t):
    que=queue.Queue()
    que.put(s)
    d[s]=0
    visit[s]=True
    while not que.empty():
        q=que.get()
        if q==t:
            return d[t]
        for z in edges_3[q]:
            if visit[z]==False:
                que.put(z)
                d[z]=d[q]+1
                visit[z]=True
    return d[t]
                
visit=[False for _ in range(n)]
d=[-1 for _ in range(n)]

print(bfs(s,t))

### FIXED CODE ###

#### 132_E

import queue
import sys
sys.setrecursionlimit(300000)
 
n,m=map(int,input().split())

edges=[[] for i in range(3*n)]
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    u0,u1,u2=u,u+n,u+2*n
    v0,v1,v2=v,v+n,v+2*n
    edges[u0].append(v1)
    edges[u1].append(v2)
    edges[u2].append(v0)
    
s,t=map(int,input().split())
s,t=s-1,t-1
    
def bfs(s,t):
    que=queue.Queue()
    que.put(s)
    d[s]=0
    visit[s]=True
    while not que.empty():
        q=que.get()
        if q==t:
            return d[t]
        for z in edges[q]:
            if visit[z]==False:
                que.put(z)
                d[z]=d[q]+1
                visit[z]=True
    return d[t]
                
visit=[False for _ in range(3*n)]
d=[-1 for _ in range(3*n)]

print(bfs(s,t)//3)
### BUGGY CODE ###

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

for _ in range(M):
  mx = max(A)
  idx =  A.index(max(A))
  A[idx] = mx/2
  
for i in range(N):
  A[i] = int(A[i])

print(sum(A))

### FIXED CODE ###

import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
 
for i in range(N):
  A[i] = -A[i]
  
heapq.heapify(A)
 
for _ in range(M): 
    hoge = -heapq.heappop(A)
    hoge = hoge // 2
    heapq.heappush(A, -hoge)
 
print(-sum(A))