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

import math


N = int(input())
X_bin = input()

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    if next_int == 0:
        return 0
    '''
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    '''
    cnt = 0
    n = int(math.log2(next_int))
    for i in range(n, -1, -1):
        if next_int >= 2**i:
            next_int -= 2**i
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_int == 0:
        return 0
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))


### FIXED CODE ###

N = int(input())
X_bin = input()
#N = 10**5
#X_bin = '1' * N

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    if next_int == 0:
        return 0
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_cnt == 0:
        return 0
    if next_int == 0:
        return 1
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
f_p = X_int % (X_cnt+1)
if X_cnt-1 == 0:
    f_m = 0
else:
    f_m = X_int % (X_cnt-1)
for i in range(N):
    if X_bin[i] == '1':
        next_cnt = X_cnt - 1
        if next_cnt == 0:
            next_int = 0
        else:
            next_int = f_m - pow(2, (N-i-1), next_cnt)  # マイナスでも正しく求まる？
    else:
        next_cnt = X_cnt + 1
        next_int = f_p + pow(2, (N-i-1), next_cnt)
    print(calc_ans(next_int, next_cnt))
    #calc_ans(next_cnt, next_cnt)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
c = 0
for i in range(0,n-1):
  for j in range(i+1,n):
    c += a[i]*a[j]%(10**9+7)
    c %= (10**9+7)
print(c)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
left = 0
right = 0
for i in range(n):
  left += a[i]
  left %= (10**9+7)
for j in range(n):
  right += a[j]
  right %= (10**9+7)
c = (left*right)%(10**9+7)
l = [(k**2)%(10**9+7) for k in a]
print(((c+(10**9+7)-sum(l)%(10**9+7))*pow(2, 10**9+5, 10**9+7))%(10**9+7))
### BUGGY CODE ###

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

f = 0
for i in range(N):
    if A[i] != 0:
        ans *= A[i]
    else:
        print(0)
        exit()

    if ans > pow(10,18):
        f = 1

if f == 1:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

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

limit = pow(10,18)

f = 0
for i in range(N):
    if A[i] != 0 and f == 0:
        ans *= A[i]
    elif A[i] != 0:
        pass
    else:
        print(0)
        exit()

    if ans > limit:
        f = 1

if f == 1:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

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

ans = []
for i in range(n - k + 1):
    temp = 0
    for j in range(i, i + k):
        temp += (p[j] * (p[j] + 1) / 2) / p[j]

    ans.append(temp)

ans.sort(reverse=True)
print(ans[0])

### FIXED CODE ###

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

p_dash = []
for i in range(n):
    p_dash.append((p[i] + 1) / 2)

ans_max = 0
for i in range(k):
    ans_max += p_dash[i]

temp = ans_max
for i in range(k, n):
    temp = temp - p_dash[i - k] + p_dash[i]
    if(temp > ans_max):
        ans_max = temp

print(ans_max)
### BUGGY CODE ###

n=int(input())
p=list(map(int, input().split()))
ans=1
l=[p[0]]
for i in range(1,n):
    l.append(p[i])
    if p[i]==min(l):
        ans+=1
    else:
        continue
print(ans)

### FIXED CODE ###

n=int(input())
p=list(map(int, input().split()))
ans=1
l=[p[0]]
buf=p[0]
for i in range(1,n):
    l.append(p[i])
    if p[i]<=buf:
        ans+=1
        buf=p[i]
print(ans)
### BUGGY CODE ###

N, M = [int(x) for x in input().split()]
LR = [[int(x) for x in input().split()] for i in range(M)]
LR = [list(range(x,y+1)) for (x,y) in LR]
res = set(LR[0])
for x in LR[1:]:
    # print(res)
    # print(x)
    res = res.intersection(set(x))
    # print(res)
print(len(res))

### FIXED CODE ###

N, M = [int(x) for x in input().split()]
L = 1
R = N
for i in range(M):
    L_,R_ = [int(x) for x in input().split()]
    L = max(L, L_)
    R = min(R, R_)

print(max((R-L + 1), 0))
### BUGGY CODE ###

s = input()
q = int(input())
revflag = 1
for i in range(q):
	tfc = list(map(str, input().split()))
	if tfc[0] == '1':
		revflag *= -1
	elif tfc[1] == '1':
		if revflag > 0:
			s = tfc[2] + s
		else:
			s = s + tfc[2]
	else:
		if revflag > 0:
			s += tfc[2]
		else:
			s = tfc[2] + s
if revflag > 0:
	print(s)
else:
	print(s[::-1])

### FIXED CODE ###

from collections import deque

s = input()
q = int(input())
revflag = 1
d = deque(s)
for i in range(q):
	tfc = list(map(str, input().split()))
	if tfc[0] == '1':
		revflag *= -1
	elif tfc[1] == '1':
		if revflag > 0:
			d.appendleft(tfc[2])
		else:
			d.append(tfc[2])
	else:
		if revflag > 0:
			d.append(tfc[2])
		else:
			d.appendleft(tfc[2])
if revflag > 0:
	print(''.join(d))
else:
	print(''.join(reversed(d)))
### BUGGY CODE ###

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

A.sort()
B.sort()
C.sort()

BClist = []
for i in range(N):
    for j in range(N):
        if(B[i] < C[j]):
            BClist.append(N-j)
            break

ans = 0
for k in range(N):
    for i in range(N):
        if(A[k] < B[i]):
            ans += sum(BClist[i:])
            break
            
print(ans)

### FIXED CODE ###

import bisect

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = 0
a.sort()
b.sort()
c.sort()

for j in range(n):
    ans += bisect.bisect_left(a,b[j])*(n-bisect.bisect_right(c,b[j]))
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

N, Q = map(int, input().split())
v = [[] for _ in range(N)]
for _ in range(N-1) :
    a, b = map(int, input().split())
    v[a-1].append(b-1)
    v[b-1].append(a-1)
    
visited = [False] * N
visited[0] = True
parent = [[] for _ in range(N)]

def bfs(cur, par) :
    parent[cur] = [cur] + par
    for nex in v[cur] :
        if not visited[nex] :
            visited[nex] = True
            bfs(nex, parent[cur])

bfs(0, [])

pq = [0 for _ in range(N)]
for _ in range(Q) :
    p, q = map(int, input().split())
    pq[p-1]  += q

ret = []
for i in range(N) :
    s = 0
    for j in parent[i] :
        s += pq[j]

    ret.append(s)
    
print(*ret)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N, Q = map(int, input().split())
v = [[] for _ in range(N)]
for _ in range(N-1) :
    a, b = map(int, input().split())
    v[a-1].append(b-1)
    v[b-1].append(a-1)
    
pq = [0 for _ in range(N)]
for _ in range(Q) :
    p, q = map(int, input().split())
    pq[p-1] += q
    
visited = [False] * N
visited[0] = True

ret = [0] * N
def bfs(cur, score) :
    ret[cur] = score + pq[cur]
    for nex in v[cur] :
        if not visited[nex] :
            visited[nex] = True
            bfs(nex, ret[cur])

bfs(0, 0)
    
print(*ret)
### BUGGY CODE ###

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

l = 0
r = k

result = 0.0
while r != len(p)+1:
  this_res = 0.0
  for pi in p[l:r]:
    this_res += pi / 2 + 1/2
  result = max(result, this_res)
  l += 1
  r += 1

print(result)

### FIXED CODE ###

from itertools import accumulate
n, k = map(int, input().split())
p = list(map(int, input().split()))

pp = [0] + list(accumulate(p))

m = 0
for i in range(n - k + 1):
  m = max(m,pp[i + k] - pp[i])
print((m+k)/2)
### BUGGY CODE ###

'''
1枚抜いてDPをN枚についてやれば良い, がこれでは間に合わない
そこで必要不要の境界を二分探索で探す
するとO(N^2K)→O(NKlogN)となって間に合う

もう1つの方法は分からない
'''

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    N,K = map(int, input().split())
    a = list(map(int, input().split()))
    a = sorted(a)
    a = a[:bisect_left(a, K)]
    n = len(a)
    def dp(num):
        dp = [[0]*(K) for _ in range(n)]
        dp[0][0] = 1
        b = a[:num]+a[num+1:] #N-1個
        for i in range(n-1):
            for j in range(K):
                if b[i]<=j:
                    dp[i+1][j] = dp[i][j-b[i]] or dp[i][j]
                else:
                    dp[i+1][j]=dp[i][j]
        return any(dp[n-1][K-a[num]:])

    left = 0
    right = n-1
    while left<=right:
        mid = (left+right)//2
        if dp(mid):
            right = mid-1
        else:
            left = mid+1
    print(right+1)

if __name__ == '__main__':
    main()


### FIXED CODE ###

'''
1枚抜いてDPをN枚についてやれば良い, がこれでは間に合わない
そこで必要不要の境界を二分探索で探す
するとO(N^2K)→O(NKlogN)となって間に合う

もう1つの方法は分からない
'''

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    N,K = map(int, input().split())
    a = list(map(int, input().split()))
    a = sorted(a)
    a = a[:bisect_left(a, K)]
    n = len(a)


    import numpy as np
    def dp(omit):
        dp = np.zeros((n+1, K), dtype=np.bool)
        dp[0,0] = 1
        for i in range(n):
            # まとめて遷移
            dp[i+1] |= dp[i]
            if i != omit and a[i] < K:
                dp[i+1,a[i]:] |= dp[i,:K-a[i]]
        # 今回の値A[omit]を足してKに到達できるような部分和があれば、これは必要
        for j in range(max(0, K-a[omit]), K):
            if dp[n,j]:
                return True
        # なければ不要
        return False


    # def dp(num):
    #     dp = [[0]*(K) for _ in range(n)]
    #     dp[0][0] = 1
    #     b = a[:num]+a[num+1:] #N-1個
    #     for i in range(n-1):
    #         for j in range(K):
    #             if b[i]<=j:
    #                 dp[i+1][j] = dp[i][j-b[i]] or dp[i][j]
    #             else:
    #                 dp[i+1][j]=dp[i][j]
    #     return any(dp[n-1][K-a[num]:])

    left = 0
    right = n-1
    while left<=right:
        mid = (left+right)//2
        if dp(mid):
            right = mid-1
        else:
            left = mid+1
    print(right+1)

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

import sys

n,m = map(int, input().split())
adj_list = [[] for i in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    adj_list[l-1].append((r-1, d))
    adj_list[r-1].append((l-1, -d))
def search(start):
    q = [[start]]
    q_d = [0]
    q_d = [0]
    dist_all = [None for i in range(n)]
    while(len(q) > 0):
        path = q.pop(0)
        dist = q_d.pop(0)
        w = path[len(path) - 1]
        for x in adj_list[w]:
            if x[0] not in path:
                new_path = path[:]
                new_path.append(x[0])
                if dist_all[x[0]] is None:
                    dist_all[x[0]] = dist + x[1]
                elif dist_all[x[0]] != dist + x[1]:
                    return False
                q.append(new_path)
                q_d.append(dist + x[1])
    return True
for i in range(n):
    if not search(i):
        print('No')
        exit(0)
print('Yes')


### FIXED CODE ###

import sys
from collections import deque

n,m = map(int, input().split())
adj_list = [[] for i in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    adj_list[l-1].append((r-1, d))
    adj_list[r-1].append((l-1, -d))
def search(start, dist_all):
    q = deque([start])
    dist_all[i] = 0
    while(len(q) > 0):
        w = q.popleft()
        for x in adj_list[w]:
            if dist_all[x[0]] is None:
                dist_all[x[0]] = dist_all[w] + x[1]
                q.append(x[0])
            elif dist_all[x[0]] != dist_all[w] + x[1]:
                return False
    return True
dist_all = [None for i in range(n)]
for i in range(n):
    if dist_all[i] is None:
        if not search(i, dist_all):
            print('No')
            exit(0)
print('Yes')
### BUGGY CODE ###

from collections import deque
n=int(input())
a=deque(list(map(int,input().split())))
c=deque([1 if i%2==0 else -1 for i in range(n)])

ans=[]
for loop in range(n):
    t=sum([i*j for i,j in zip(a,c)])
    ans.append(str(t))
    c.rotate(1)


print(" ".join(ans))

### FIXED CODE ###

from collections import deque
n=int(input())
a=deque(list(map(int,input().split())))
c=deque([1 if i%2==0 else -1 for i in range(n)])

ans=[]
for loop in range(n):
    if loop==0:
        t=sum([i*j for i,j in zip(a,c)])
    else:
        t=2*a[loop-1]-t
    ans.append(str(t))


print(" ".join(ans))
### BUGGY CODE ###

import numpy as np

n=int(input())
l=np.array(list(map(int , input().split())))
#尺取り法
l.sort()
s=0
for i in range(n):
  if i+2<n:
    k=i+2
  else:
    break
  for j in range(i+1,n):
    while (k<n and l[k]<l[i]+l[j]):
      k+=1
    s+=k-(j+1)
print(s)

### FIXED CODE ###


n=int(input())
l=list(map(int , input().split()))
#尺取り法
l.sort()
s=0
for i in range(n):
  if i+2<n:
    k=i+2
  else:
    break
  for j in range(i+1,n):
    while (k<n and l[k]<l[i]+l[j]):
      k+=1
    s+=k-(j+1)
print(s)
### BUGGY CODE ###

n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
ans=10**18*4
for i1 in range(n):
    i1_sub=n-i1
    x_sub1=x[i1][0]
    for l1 in range(i1_sub,1,-1):
        x_sub2=x[i1+l1-1][0]
        for i2 in range(n):
            i2_sub=n-i2
            y_sub1=y[i2][0]
            x_subsub=x_sub2-x_sub1
            for l2 in range(i2_sub,1,-1):
                y_sub2=y[i2+l2-1][0]
                z=0
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z+=1
                    if z>=k:
                        ans=min(x_subsub*(y_sub2-y_sub1),ans)
                        break
                else:
                    break
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import math

N, M = map(int, input().split())
start = []
goal = []
for i in range(M):
    l1, l2 = map(int, input().split())
    if (l1 == 1):
        start.append([l1, l2])
    if (l2 == N):
        goal.append([l1, l2])

def check(st, go):
    for i in st:
        if ([i[1], N] in go):
            return(True)
    return(False)

if (check(start, goal)):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')


### FIXED CODE ###

# -*- coding: utf-8 -*-

import math

N, M = map(int, input().split())
start = [False] * N
goal = [False] * N
for i in range(M):
    a1, a2 = map(int, input().split())
    if (a1 == 1):
        start[a2 - 1] = True
    if (a2 == N):
        goal[a1 - 1] = True

def check():
    for i in range(N):
        if (start[i] & goal[i]):
            return('POSSIBLE')
    return('IMPOSSIBLE')

print(check())
### BUGGY CODE ###

S = input()
l = len(S)
for k in range(1,l):
    if S[k-1:k+1] == "BC":
        S = S[:k-1] + "D" + S[k+1:]
        l -= 1
S = "".join(S)
S = S.replace("B","C")
L = list(S.split("C"))

def keisan(s):
    if len(s) == 0:
        return 0
    l = len(s)
    t = 1
    ret = 0
    for k in range(len(s)):
        if s[k] == "A":
            ret += l-k-t
            t += 1
    return ret

ans = 0
for s in L:
    ans += keisan(s)
print(ans)


### FIXED CODE ###

S = input()
l = len(S)
A = ""
k = 0
while k < l-1:
    if S[k:k+2] == "BC":
        A += "D"
        k += 2
    else:
        A += S[k]
        k += 1
S = A
S = S.replace("B","C")
L = list(S.split("C"))

def keisan(s):
    if len(s) == 0:
        return 0
    l = len(s)
    t = 1
    ret = 0
    for k in range(len(s)):
        if s[k] == "A":
            ret += l-k-t
            t += 1
    return ret

ans = 0
for s in L:
    ans += keisan(s)
print(ans)
### BUGGY CODE ###

#! python3
# dictionary.py

# ハッシュ法, チェイン法, 開番地法, etc
# オープンアドレス法で実装する

M = 113131

def getkey(text):
    dic = {'A': 1, 'T': 2, 'G': 3, 'C': 4}
    sum = 0
    p = 1
    for c in text:
        sum += p*dic[c]
        p *= 5
    return sum

def h1(key):
    return key % M

def h2(key):
    return 1 + (key %(M-1))

def h3(key, i):
    return (h1(key) + i*h2(key)) % M

dict = {}
def find(text):
    global dict
    key = getkey(text)
    i = 0
    while i < M:
        h = h3(key, i)
        if dict.get(h) == None:
            break
        elif dict[h] == text:
            return True
        i += 1
    return False

def insert(text):
    global dict
    key = getkey(text)
    i = 0
    while i < M:
        j = h3(key, i)
        if dict.get(j) == None:
            dict[j] = text
            break
        else:
            i += 1

n = int(input())
for i in range(n):
    op, text = input().split(' ')
    if op == 'insert':
        insert(text)
    elif op == 'find':
        rst = find(text)
        if rst:
            print('yes')
        else:
            print('no')


### FIXED CODE ###

import sys

M = 1046527
def h1(key):
    return key % M

def h2(key):
    return 1 + (key %(M-1))

def h3(key, i):
    return (h1(key) + i*h2(key)) % M

word_dic = {'A': 1, 'T': 2, 'G': 3, 'C': 4}
def getkey(text):
    sum = 0
    p = 1
    for c in text:
        sum += p*word_dic[c]
        p *= 5
    return sum

dict = [None for i in range(M)]
def find(text):
    key = getkey(text)
    i = 0
    while i < M:
        h = h3(key, i)
        if dict[h] == None:
            break
        elif dict[h] == text:
            return True
        i += 1
    return False

def insert(text):

    key = getkey(text)
    i = 0
    while i < M:
        j = h3(key, i)
        if dict[j] == None:
            dict[j] = text
            break
        else:
            i += 1

n = int(input())
operations = sys.stdin.readlines()
for ope in operations:
    op, text = ope.rstrip().split(' ')
    if op == 'insert':
        insert(text)
    elif op == 'find':
        rst = find(text)
        if rst:
            print('yes')
        else:
            print('no')
### BUGGY CODE ###

from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import deque
from copy import deepcopy

h,w=nii()
s=[list(input()) for i in range(h)]

def BFS(sy,sx,ans):
  temp_s=deepcopy(s)

  que=deque()
  que.append((sy,sx))

  while que:
    y,x=que.popleft()
    for dy,dx in [[-1,0],[0,-1],[1,0],[0,1]]:
      ny=y+dy
      nx=x+dx
      if 0<=ny<h and 0<=nx<w:
        if (temp_s[y][x]=='#' and temp_s[ny][nx]=='.') or \
           (temp_s[y][x]=='.' and temp_s[ny][nx]=='#'):
          que.append((ny,nx))
          if temp_s[ny][nx]=='.':
            ans.add(((sy,sx),(ny,nx)))
            ans.add(((y,x),(ny,nx)))
          if temp_s[y][x]=='#':
            s[y][x]=='D'
    temp_s[y][x]='D'

  return ans

ans=set()
for i in range(h):
  for j in range(w):
    if s[i][j]=='#':
      ans=BFS(i,j,ans)

print(len(ans))

### FIXED CODE ###

from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import deque

h,w=nii()
s=[list(input()) for i in range(h)]

def BFS(sy,sx,ans):
  s[sy][sx]='B'

  que=deque()
  que.append((sy,sx))

  b_cnt=1
  w_cnt=0

  while que:
    y,x=que.popleft()
    for dy,dx in [[-1,0],[0,-1],[1,0],[0,1]]:
      ny=y+dy
      nx=x+dx
      if 0<=ny<h and 0<=nx<w:
        if s[y][x]=='B' and s[ny][nx]=='.':
          w_cnt+=1
          s[ny][nx]='W'
          que.append((ny,nx))
        if s[y][x]=='W' and s[ny][nx]=='#':
          b_cnt+=1
          s[ny][nx]='B'
          que.append((ny,nx))

  ans+=b_cnt*w_cnt
  return ans

ans=0
for i in range(h):
  for j in range(w):
    if s[i][j]=='#':
      ans=BFS(i,j,ans)

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

N, M = map(int, input().split())
ans_list = list(range(1,N+1))
HList = list(map(int, input().split()))
rootList = []

for i in range(M):
  a, b = map(int, input().split())
  H_a = HList[a-1]
  H_b = HList[b-1]
  if(a in ans_list):
    if(H_b > H_a or H_b == H_a):
      ans_list.remove(a)
  if(b in ans_list):
    if(H_a > H_b or H_b == H_a):
      ans_list.remove(b)

print(len(ans_list))


### FIXED CODE ###

N, M = map(int, input().split())
keyList = list(range(1,N+1))
values = [True] * N
dic = dict(zip(keyList, values))
HList = list(map(int, input().split()))
ans = []

for i in range(M):
  a, b = map(int, input().split())
  H_a = HList[a-1]
  H_b = HList[b-1]
  if(H_a == H_b):
    dic[a] = False
    dic[b] = False
  elif(H_b > H_a):
    dic[a] = False
  elif(H_a > H_b):
    dic[b] = False


for i in range(1, len(dic.values())+1):
  if(dic[i] == True):
    ans.append(dic[i])
print(len(ans))
### BUGGY CODE ###

import heapq
N,M = map(int,input().split())
Alist = list(map(int,input().split()))
newA = list(map(lambda x: x*(-1),Alist))
for i in range(M):
    heapq.heapify(newA)
    current = -heapq.heappop(newA)
    heapq.heappush(newA,-(current//2))

cost = 0
for i in range(N):
    cost += newA[i]
print(-cost)

### FIXED CODE ###

import heapq
N,M = map(int,input().split())
Alist = list(map(int,input().split()))
newA = list(map(lambda x: x*(-1),Alist))
heapq.heapify(newA)
for i in range(M):
    current = -heapq.heappop(newA)
    heapq.heappush(newA,-(current//2))
cost = 0
print(-sum(newA))