Harryxun/stf_run huggingface dataset:
h, w = map(int, input().split())
g = [[0] * w for _ in range(h)]#白が1、黒が０
for i in range(h):
    s = list(input())
    for j in range(w):
        if s[j] == '.':
            g[i][j] = 1
INF = 10**9
dp = [[INF] * w for _ in range(h)]
if g[0][0] == 0:
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(h):
    for j in range(w):
        for dx, dy in ((1, 0), (0, 1)):
            nx = j + dx
            ny = i + dy
            if nx >= h or ny >= w:
                continue
            add = 0
            if g[ny][nx] == 0 and g[i][j]  == 1:
                add = 1
            dp[ny][nx] = min(dp[ny][nx], dp[i][j] + add)
            
print(dp[h-1][w-1])




### FIXED CODE ###

h, w = map(int, input().split())
g = [[0] * w for _ in range(h)]#白が1、黒が０
for i in range(h):
    s = list(input())
    for j in range(w):
        if s[j] == '.':
            g[i][j] = 1
INF = 10**9
dp = [[INF] * w for _ in range(h)]
if g[0][0] == 0:
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(h):
    for j in range(w):
        for dx, dy in ((1, 0), (0, 1)):
            nx = j + dx
            ny = i + dy
            if ny >= h or nx >= w:
                continue
            add = 0
            if g[ny][nx] == 0 and g[i][j]  == 1:
                add = 1
            dp[ny][nx] = min(dp[ny][nx], dp[i][j] + add)
            
print(dp[h-1][w-1])
x = input()
    def f(x):
      if x == "ABC":
        print("ARC")
      elif x == "ARC":
        print("ABC")
      else:
        print("invalid input")
     
    print(f(x))

### FIXED CODE ###

x = input()
def f(x):
    if x == "ABC":
        print("ARC")
    elif x == "ARC":
        print("ABC")
    else:
        print("invalid input")
f(x)
N=int(input())
X=input()
c=X.count('1')
r1=int(X,2)%(c-1)
r2=int(X,2)%(c+1)
d=[0]*(N+1)
for i in range(N):
    d[i+1]=d[(i+1)%bin(i+1).count('1')]+1
for i in range(N):
    if X[i]=='0':
        n=(r2+pow(2,N-i-1,c+1))%(c+1)
    else:
        if c==1:
            print(0)
            continue
        n=(r1-pow(2,N-i-1,c-1))%(c-1)
    print(d[n]+1)

### FIXED CODE ###

N=int(input())
X=input()
c=X.count('1')
r1=int(X,2)%(c-1) if c>1 else 0
r2=int(X,2)%(c+1)
d=[0]*(N+1)
for i in range(N):
    d[i+1]=d[(i+1)%bin(i+1).count('1')]+1
for i in range(N):
    if X[i]=='0':
        n=(r2+pow(2,N-i-1,c+1))%(c+1)
    else:
        if c==1:
            print(0)
            continue
        n=(r1-pow(2,N-i-1,c-1))%(c-1)
    print(d[n]+1)
D,N=map(int,input()split())

if N<100:
  print(pow(100,D)*N)
else:
  print(pow(100,D)*101)


### FIXED CODE ###

A,B=map(int,input().split())
if (A>8) or (B>8):
  print(":(")
else:
  print("Yay!")
d = int(input())
c = list(map(int,input().split()))
s = [[] for i in range(26)]
for i in range(d):
    s[i] = list(map(int,input().split()))
ans = 0
last = [0]*26
for i in range(d):
    t = int(input())-1
    ans += s[i][t]
    last[t] = i+1
    for j in range(26):
        ans -= c[j]*(i-last[j]+1)
    print(ans)


### FIXED CODE ###

n = 26
d = int(input())
c = list(map(int,input().split()))
s = [[] for i in range(d)]
for i in range(d):
    s[i] = list(map(int,input().split()))
a = 0
last = [0]*n
for i in range(d):
    t = int(input())-1
    a += s[i][t]
    last[t] = i+1
    for j in range(n):
        a -= c[j]*(i-last[j]+1)
    print(a)
if a==b: print(c)
elif a==c: print(b)
else: print(a)

### FIXED CODE ###

a, b, c = map(int,input().split())

if a==b: print(c)
elif a==c: print(b)
else: print(a)
a, b, c, d = map(int, input().split())
x = -(-c // b)
y = -(-a // d)
if x <= y:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

s, w = map(int, input().split())
if s <= w: print('unsafe')
else     : print('safe')
a = list(map(int,input().split()))
b = "".join(a)
if b % 4 == 0:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

a = list(map(int,input().split()))
b = a[0]*100 + a[1] *10 + a[2]
if b % 4 == 0:
  print("YES")
else:
  print("NO")
def nCk(n, k):
    ans = 1
    i = 0
    while i < k:
        ans *= n - i
        i += 1
    i = 1
    while i <= k:
        ans /= i
        i += 1
    return ans

def main():
    [N, P] = map(int, raw_input().split())
    even = 0
    odd = 0
    A = map(int, raw_input().split())
    i = 0
    while i < N:
        if 0 == A[i] & 1:
            even += 1
        else:
            odd += 1
        i += 1
    i = P
    k = 0
    while i <= odd:
        k += nCk(odd, i)
        i += 2
    print((2 ** even) * k)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def nCk(n, k):
    ans = 1
    i = 0
    while i < k:
        ans *= n - i
        i += 1
    i = 1
    while i <= k:
        ans /= i
        i += 1
    return ans

def main():
    [N, P] = map(int, raw_input().split())
    even = 0
    odd = 0
    A = map(int, raw_input().split())
    i = 0
    while i < N:
        if 0 == A[i] & 1:
            even += 1
        else:
            odd += 1
        i += 1
    i = P
    k = 0
    while i <= odd:
        k += nCk(odd, i)
        i += 2
    print((2 ** even) * k)

if __name__ == '__main__':
    main()
p, q, r = map(int, input().split())

total = soated(p, q, r)

print(total[0]+total[1])

### FIXED CODE ###

time = list(map(int, input().split()))

t = sorted(time)

print(t[0]+t[1])
N,D = map(int, input().split())

num = 0
for i in range(1,N):
    if (D*2+1)<=N:
        i += 1
        break
num=i
print(num)

### FIXED CODE ###

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

if n%(2*d+1)!=0:
  print(n//(2*d+1)+1)
else:
  print(n//(2*d+1))
N = int(input())
H = list(map(int,input.split()))
ANS = True
if N == 1:
    pass
else:
    for i in range(N-2,-1,-1):
        if (H[i] - H[i+1]) >= 2:
            ANS = False
            break
        elif (H[i] - H[i+1]) == 1:
            H[i] -= 1

print('Yes' if ANS else 'No')

### FIXED CODE ###

N = int(input())
H = list(map(int,input().split()))
ANS = True
if N == 1:
    pass
else:
    for i in range(N-2,-1,-1):
        if (H[i] - H[i+1]) >= 2:
            ANS = False
            break
        elif (H[i] - H[i+1]) == 1:
            H[i] -= 1

print('Yes' if ANS else 'No')
ans = float("inf")
for i in range(1<<d):
    count = 0
    sum = 0
    nokori = set(range(1, d+1))
    
    # ボーナスをもらえる解答のみでスコアを計算
    for j in range(d):
        if j & 1<<i:
            sum += pc[i][0]*(i+1)*100+pc[i][1]
            count += pc[i][0]
            nokori.discard(i+1)
            
    # スコアがG点に届かない場合
    if sum < g:
        use = max(nokori)
        n = min(pc[use-1][0], (g-sum)//(use*100))
        count += n
        sum += n*use*100
        
    # スコアがG点に届いた場合
    if sum >= g:
        ans = min(ans, count)
print(ans)

### FIXED CODE ###

d, g = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(d)]

ans = float("inf")

for bit in range(1 << d):
    count = 0
    sum = 0
    nokori = set(range(1, d + 1))

    for i in range(d):
        if bit & (1 << i):
            sum += pc[i][0] * (i + 1) * 100 + pc[i][1]
            count += pc[i][0]
            nokori.discard(i + 1)

    # G 点に満たなければ nokori のうち一番大きいものを解く
    if sum < g:
        use = max(nokori)
        n = min(pc[use - 1][0], -(-(g - sum) // (use * 100)))
        count += n
        sum += n * use * 100

    if sum >= g:
        ans = min(ans, count)

print(ans)
S = input()
T = input()
ans = 0
for i in range(len(S)):
  if S[i] != T[i]::
      ans += 1
print(ans)

### FIXED CODE ###

S = input()
T = input()
ans = 0
for i in range(len(S)):
  if S[i] != T[i]:
      ans += 1
print(ans)
n = int(input())
INF = 10**9
P = []
for i in range(n):
    p = map(int, input().split())
    P.append()
m = [[0]*n for in range(n)]

for l in range(2, n + 1):
    for i in range(n - l + 1):
        j = i + l - 1
        m[i][j] = INF
        for k in range(i, j):
            m[i][j] = min(m[i][j], m[i][k] + m[k + 1]m[j] + p[i - 1] * p[k] * p[j])

print(m[0][n - 1])

### FIXED CODE ###

n = int(input())
INF = 10**9
P = [list(map(int, input().split())) for i in range(n)]
m = [[0]*n for i in range(n)]

for l in range(2, n + 1):
    for i in range(n - l + 1):
        j = i + l - 1
        m[i][j] = INF
        for k in range(i, j):
            m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + P[i][0] * P[k][1] * P[j][1])

print(m[0][n - 1])
O=str(input())
E=str(input())
S=""
if len(O)==len(E):
  for i in range(len(O)):
    S=S+O[i]+E[i]
else:
  for i in range(len(O)-1):
    S=S+O[i]+E[i]
  S=S+O[len(O)]
print(S)

### FIXED CODE ###

O=str(input())
E=str(input())
S=""
if len(O)==len(E):
  for i in range(len(O)):
    S=S+O[i]+E[i]
else:
  for i in range(len(O)-1):
    S=S+O[i]+E[i]
  S=S+O[len(O)-1]
print(S)
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)

r1,c1,r2,c2=map(int,input().split())
n1=r2+c2+2
n2=r2+c1+1
n3=r1+c2+1
n4=r1+c1
l=[r2+1,r2+1,r1,r1]
p=10**9+7
buf=1
cnt=0
l=[0]*(10**6+10)
l2=[0]*20
inv=[0]*(10**6+10)
for i in range(2,n1+3,1):#n1+1
    l[i]=(l[i-1]*i)%p
print((((l[n1]*modinv(l[r2+1],p)*modinv(l[n1-r2-1],p))%p)-(l[n2]*modinv(l[r2+1],p)*modinv(l[n2-r2-1],p))-(l[n3]*modinv(l[r1],p)*modinv(l[n3-r1],p))+(l[n4]*modinv(l[r1],p)*modinv(l[n4-r1],p)))%p)

### FIXED CODE ###


import numpy as np

N=input()
K=input()
dp=np.zeros((len(str(N))+10,len(str(N))+10,2))
dp=dp.tolist()


x0=int(N[0])
dp[0][0][0]=1


for i in range(0,len(N),1):
    for j in range(0,4,1):
        for k in range(0,2,1):
            nd=int(N[i])
            for d in range(0,10,1):
                ni=i+1
                nj=j
                nk=k
                if not(d==0):
                    nj=nj+1
                if ((k==0)and(d<nd)):
                    nk=1
                if (not(nj>int(K)))and(not((k==0)and(d>nd))):
                    dp[ni][nj][nk]=dp[ni][nj][nk]+dp[i][j][k]


print(int(dp[len(N)][int(K)][0]+dp[len(N)][int(K)][1]))
from statistics import mode

n = int(input())
v = list(map(int, input.split()))
a = v[::1]
b = v[1::1]
slash = mode(a)
back_slash = mode(b)
a = [i for i in a if i == slash]
b = [j for j in b if j == back_slash]
print(len(a) + len(b))


### FIXED CODE ###

from collections import Counter

n = int(input())
v = list(map(int, input().split()))
v_odd = v[0::2]
v_even = v[1::2]
ans = 0
c_odd = Counter(v_odd)
c_even = Counter(v_even)
v_o, c_o = zip(*c_odd.most_common())
v_e, c_e = zip(*c_even.most_common())
if len(c_o) == 1:
    odd1 = 0
else:
    odd1 = c_o[1]
if len(c_e) == 1:
    even1 = 0
else:
    even1 = c_e[1]
if not v_o[0] == v_e[0]:
    print(sum(c_o) - c_o[0] + sum(c_e) - c_e[0])
else:
    ans = min(sum(c_o) - c_o[0] + sum(c_e) - even1, sum(c_o) - odd1 + sum(c_e) - c_e[0])
    print(ans)
A,B=map(int,input())

print(A*B)

### FIXED CODE ###

A, B=map(int, input().split())

print(A*B)
import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():

    N, K = NMI()
    A = NLI()
    
    left = 0
    shakutori = 0
    ans = 0
    
    for left in range(N):
        shakutori = 0
        right = left
        
        while shakutori < K and right <N:
            shakutori += A[right]
            right+= 1
            
        if shakutori >= K:
            ans += N-right+1
        else:
            break
        
    print(ans)
    


if __name__ == '__main__':
    main()

### FIXED CODE ###

X, A = map(int,input().split())

if X>=A:
  print(10)
else:
  print(0)
n=int(input())
v1=map(int,input().split())
v=list(v1)
#価値の低いものから順に平均をとっていけばよい
for i in range(n):
    for j in range(i+1,n):
        if v[i]>v[j]:
            a=v[i]
            v[i]=v[j]
            v[j]=a
for l in range(n-1):
    a=(v[0]+v[1])/2
    v=a+v[2,n-l]
print(v[0])


### FIXED CODE ###

n=int(input())
v1=map(int,input().split())
v=list(v1)
#価値の低いものから順に平均をとっていけばよい
for i in range(n):
    for j in range(i+1,n):
        if v[i]>v[j]:
            a=v[i]
            v[i]=v[j]
            v[j]=a
for l in range(n-1):
    v2=[]
    a=(v[0]+v[1])/2
    v2.append(a)
    v2=v2+v[2:n]
    v=v2
print(v[0])
k= int(input())
 
if k % 2 == 0 or k % 5 == 0:
    print("-1")
    
else:
    ans = 1
    s = ７
    while True:
        if s % k == 0:
            print(ans)
            break
        else:
            s = (s % k)*10 + 7
            ans += 1

### FIXED CODE ###

k= int(input())

if k % 2 == 0 or k % 5 == 0:
    print("-1")
    
else:
    ans = len(str(k))
    s = int(str(7)* ans)
    while True:
        if s % k == 0:
            print(ans)
            break
        else:
            s = (s % k)*10 + 7
            ans += 1
N = int(input())
ans = 0
for i in range(1, N+1):
  	if len(str(i)) % 2 == 1:
        ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1, N+1):
    if len(str(i)) % 2 == 1:
        ans += 1
print(ans)
N = input()
S = input()
ans = set()
num_count = [0]*10
i = 0
while i < len(S):
    s_num = int(S[i])
    if num_count[s_num] <= 3:
        num_count[s_num] += 1
        i += 1
    else:
        S.pop(i)
for i in range(len(S)-2):
    for j in range(i+1, len(S)-1):
        for k in range(j+1, len(S)):
            s = S[i]+S[j]+S[k]
            if s not in ans:
                ans.add(s)
print(len(ans))


### FIXED CODE ###

N = input()
S = list(input())
count = 0
num_count = [False]*10
for i in range(len(S)-2):
    s_i = int(S[i])
    if num_count[s_i]:
        continue
    num_count[s_i] = True
    num_count_2 = [False]*10
    for j in range(i+1, len(S)-1):
        s_j = int(S[j])
        if num_count_2[s_j]:
            continue
        num_count_2[s_j] = True
        num_count_3 = [False] * 10
        for k in range(j+1, len(S)):
            s_k = int(S[k])
            if num_count_3[s_k]:
                continue
            num_count_3[s_k] = True
            count += 1
print(count)
a,b = raw_input.split.map
print a*b

### FIXED CODE ###

a,b = map(int, raw_input().split())
print a*b, 2*(a+b)
def main():
    N = int(input())
    As = list(map(int, input().split()))

    query = (map(int, input().split()) for _ in range(N-1))

    tree = [[] for _ in range(N)]
    for u, v in query:
        tree[u-1].append(v-1)
        tree[v-1].append(u-1)

    inf = 10 ** 9 + 7
    dp = [inf] * N
    ans = [0] * N

    def dfs(node, parent):
        v = As[node]
        lb = binary_search(dp, v)
        old = dp[lb]
        dp[lb] = v
        ans[node] = lb + 1
        for child in tree[node]:
            if child == parent:
                continue
            dfs(child, node)
        dp[lb] = old

    dfs(0, 0)

    for k in range(N):
        print(ans[k])


def binary_search(seq, v):
    left = 0
    right = len(seq) - 1
    center = right // 2

    while center != right:
        if v < seq[center]:
            right = center
        else:
            left = center+1
        center = (right + left) // 2

    return center


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
readline = sys.stdin.readline

sys.setrecursionlimit(10**6)


def main():
    N = int(input())
    As = list(map(int, input().split()))

    query = (map(int, readline().strip().split()) for _ in range(N-1))

    tree = [[] for _ in range(N)]
    for u, v in query:
        tree[u-1].append(v-1)
        tree[v-1].append(u-1)

    inf = 10 ** 18
    dp = [inf] * (N+1)
    ans = [0] * N

    def dfs(node, parent):
        v = As[node]
        lb = binary_search(dp, v)
        old = dp[lb]
        dp[lb] = v
        ans[node] = binary_search(dp, inf)
        for child in tree[node]:
            if child == parent:
                continue
            dfs(child, node)
        dp[lb] = old

    dfs(0, 0)

    for k in range(N):
        print(ans[k])


def binary_search(seq, v):
    left = 0
    right = len(seq) - 1
    center = right // 2

    while left != right:
        if v <= seq[center]:
            right = center
        else:
            left = center+1
        center = (right + left) // 2

    return center


if __name__ == "__main__":
    main()
import numpy as np
    n=input()
    n=int(n)
    a=input().split()
    b=np.zeros(n)
    div=0
    num_8=0
    for i in range(n):
     a[i]=int(a[i])
     if a[i]<=399 and a[i]>=1:
      b[i]=0
     elif a[i]>=400 and a[i]<=799:
      b[i]=1
     elif a[i]>=800 and a[i]<=1199:
      b[i]=2
     elif a[i]>=1200 and a[i]<=1599:
      b[i]=3
     elif a[i]>=1600 and a[i]<=1999:
      b[i]=4
     elif a[i]>=2000 and a[i]<=2399:
      b[i]=5
     elif a[i]>=2400 and a[i]<=2799:
      b[i]=6
     elif a[i]>=2800 and a[i]<=3199:
      b[i]=7
     else:
      b[i]=8
      num_8=num_8+1
    for i in range(8):
     if i in b:
      div=div+1
    min=div
    max=div+num_8
    if min==0:
     min=1
    print(min,max)

### FIXED CODE ###

import numpy as np
n=input()
n=int(n)
a=input().split()
b=np.zeros(n)
div=0
num_8=0
for i in range(n):
 a[i]=int(a[i])
 if a[i]<=399 and a[i]>=1:
  b[i]=0
 elif a[i]>=400 and a[i]<=799:
  b[i]=1
 elif a[i]>=800 and a[i]<=1199:
  b[i]=2
 elif a[i]>=1200 and a[i]<=1599:
  b[i]=3
 elif a[i]>=1600 and a[i]<=1999:
  b[i]=4
 elif a[i]>=2000 and a[i]<=2399:
  b[i]=5
 elif a[i]>=2400 and a[i]<=2799:
  b[i]=6
 elif a[i]>=2800 and a[i]<=3199:
  b[i]=7
 else:
  b[i]=8
  num_8=num_8+1
for i in range(8):
 if i in b:
  div=div+1
min=div
max=div+num_8
if min==0:
 min=1
print(min,max)
from collections import deque

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

cards = deque()

for i in range(N):
    cards.append(i+1)


for i in range(M):
    Li, Ri = map(int, input().split())
    L = cards.popleft()
    if Li <= L:
        cards.appendleft(L)
    else:
        while Li > L + 1 and len(cards) > 0:
            L = cards.popleft()

    R = cards.pop()
    if Ri >= R:
        cards.append(R)
    else:
        while Ri < R - 1 and len(cards) > 0:
            R = cards.pop()

print(len(cards))


### FIXED CODE ###

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

maxL=0
minR=N

for i in range(M):
    L, R = map(int, input().split(" "))
    
    if minR < L or R < maxL:
        print("0")
        exit()
    
    maxL=max(maxL, L)
    minR=min(minR, R)


print(minR-maxL+1)
a,b,c=int(input().splot())
if a == b:
    if a != c:
        print('yes')
    else:
        print("no")
elif a == c:
    if a != b:
        print('yes')
    else:
        print("no")
else:
    print("no")


### FIXED CODE ###

a,b,c=input().split()
if a == b:
    if a != c:
        print('Yes')
    else:
        print("No")
elif a == c:
    if a != b:
        print('Yes')
    else:
        print("No")
elif b == c:
    if b != a:
        print('Yes')
    else:
        print("No")
else:
    print("No")
N,Mmap(int,input())
e=[[] for i in range(N)]
tester=[None]*M
for i in range(M):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  e[a].append(b)
  e[b].append(a)
  tester[i]=set(a,b)
  
ans=0
seen=[0 for i in range(N)]
for test in tester:
  stack=[]
  stack.append([0,-1])
  while stack:
    node=stack.pop()
    v=node[0]
    parent=node[1]
    if seen[v]==1:
      continue
    seen[v]=1
    childs=e[v]
    for child in childs:
      if child==parent:
        continue
      if len(test&set([v,child]))==2:
        continue
      stack.append([child,v])
      
  if sum(seen)!=N:
    ans+=1
print(ans)
    
    
      




### FIXED CODE ###

N,M=map(int,input().split())
e=[[] for i in range(N)]
tester=[None]*M
for i in range(M):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  e[a].append(b)
  e[b].append(a)
  tester[i]=set([a,b])
  
ans=0
for test in tester:
  stack=[]
  stack.append([0,-1])
  seen=[0 for i in range(N)]
  while stack:
    node=stack.pop()
    v=node[0]
    parent=node[1]
    if seen[v]==1:
      continue
    seen[v]=1
    childs=e[v]
    for child in childs:
      if child==parent:
        continue
      if test==set([v,child]):
        continue
      stack.append([child,v])
      
  if sum(seen)!=N:
    ans+=1
print(ans)
N = int(input())
a = list(map(int, input()))
r = 'APPROVED'
for i in range(N):
  if a[i] % 2 ==0:
    if a[i] % 3 != 0 and a[i] % 5 != 0:
      r = 'DENIED'
      break
print(r)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
r = 'APPROVED'
for i in range(N):
  if a[i] % 2 ==0:
    if a[i] % 3 != 0 and a[i] % 5 != 0:
      r = 'DENIED'
      break
print(r)
N,M = map(int,input()split())
lis = list(map(lambda x: -int(x),input().split()))

import heapq
heapq.heapify(lis)
for _ in range(M):
    tmp = -heapq.heappop(lis)
    tmp //= 2
    heapq.heappush(lis,-tmp)

print(-sum(lis))


### FIXED CODE ###

N,M = map(int,input().split())
lis = list(map(lambda x: -int(x),input().split()))

import heapq
heapq.heapify(lis)
for _ in range(M):
    tmp = -heapq.heappop(lis)
    tmp //= 2
    heapq.heappush(lis,-tmp)

print(-sum(lis))
x = input()
    a = x.split()[0]
    b = x.split()[1]

    if a > b:
        print('a > b')
    elif a < b:
        print('a < b')
    else:
        print('a == b')


### FIXED CODE ###

line = int(input())

h = int(line / 3600)

m = int(line % 3600 / 60)

s = int(line % 3600 % 60)

print(str(h) + ':' + str(m) + ':' + str(s))
n, m = map(int, input().split())

memo = [-1] * (n + 1)
memo[0] = 1
memo[1] = 1
for i in range(m):
  memo[int(input())] = 0

def fib(x):
  if memo[x] > -1:
    return memo[x]
  else:
    memo[x] = fib(x-1) + fib(x-2)
    return memo[x]

# print(fib(n))
# print(memo)
print(fib(n) % 1000000007)


### FIXED CODE ###

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

memo = [-1] * (n + 1)
memo[0] = 1
memo[1] = 1
for i in range(m):
  memo[int(input())] = 0

def fib(x):
  if memo[x] == -1:
    memo[x] = fib(x-1) + fib(x-2)
  return memo[x]

def fib2(x):
  if x <= 1:
    return memo[x]
  else:
    for i in range(x - 1):
      if memo[i + 2] == 0:
        continue
      memo[i + 2] = memo[i] + memo[i + 1]
    return memo[x]

# print(fib2(n))
# print(memo)
print(fib2(n) % 1000000007)
d,n=input().split()
d=int(d)
n=int(n)

if d=0:
	print(d)
elif d=1:
	print(n*10)
else:
	print(n*10000)

### FIXED CODE ###

d,n=input().split()
d=int(d)
n=int(n)

if d==0:
	if n==100:
		print(101)
	else:
		print(n)
elif d==1:
	if n==100:
		print(10100)
	else:
		print(n*100)
else:
	if n==100:
		print(1010000)
	else:
		print(n*10000)
import math
# from collections import defaultdict
import time
def steps(n,p):
  c = 0
  while n:
    c += 1
    n = n%p
    p = bin(n).count('1')
  return c

# n = 200000
# x = "1"*n
n = int(input())
x = input()
incs = 1
decs = 1
p = x.count('1')
ans = []
num = int(x,2)
inc = num%(p+1)
dec = num%(p-1)
start = time.time()
k = -1
for i in range(n-1,-1,-1):
  cp = p
  if x[i] == '0':
    cp += 1
    new = (inc+incs)%cp
  else:
    cp -= 1
    new = (dec-decs)%cp
  k -= 1
  incs = (incs*2)%(p+1)
  decs = (decs*2)%(p-1)
  sol = steps(new,cp)
  if sol==0:
    sol=1
  ans.append(sol)
  # steps(new,cp)
# print(time.time()-start)
ans = ans[::-1]
for x in ans:
  print(x)

### FIXED CODE ###

import math
# from collections import defaultdict
import time
def steps(n,p):
  c = 0
  while n:
    c += 1
    n = n%p
    p = bin(n).count('1')
  return c

# n = 200000
# x = "1"*n
n = int(input())
x = input()
p = x.count('1')
ans = []
num = int(x,2)
if p==1:
  for i in range(n-1,-1,-1):
    if x[i]=='1':
      ans.append(0)
    else:
      if i==n-1 or x[n-1]=='1':
        ans.append(2)
      else:
        ans.append(1)
else:
  incs = 1
  decs = 1
  inc = num%(p+1)
  dec = num%(p-1)
  start = time.time()
  k = -1
  for i in range(n-1,-1,-1):
    cp = p
    if x[i] == '0':
      cp += 1
      new = (inc+incs)%cp
    else:
      cp -= 1
      new = (dec-decs)%cp
    k -= 1
    incs = (incs*2)%(p+1)
    decs = (decs*2)%(p-1)
    sol = steps(new,cp)
    if sol==0:
      sol=1
    ans.append(sol)
    # steps(new,cp)
  # print(time.time()-start)
ans = ans[::-1]
for x in ans:
  print(x)