Harryxun/stf_run huggingface dataset:
#from fractions import gcd
#mod = 10 ** 9 + 7
#N = int(input())
#a = list(map(int,input().split()))
#a,b,c = map(int,input().split())
#ans = [0] * N
#math.ceilで切り上げ
#dp = [[0] * 4 for i in range(3)] #2次元配列初期化
#dp = [[[0] * 2 for i in range(3)] for j in range(5)]

import math
import string

def intinput():
    return int(input())

def listintinput():
    return list(map(int,input().split()))

def splitintinput():
    return map(int,input().split())

N = str(intinput())
K = intinput()
s = len(str(N))
flag = 0
dp = [[[0] * 2 for i in range(4)] for j in range(s+1)]
dp[0][0][0] = 1
dp[1][1][1] += int(N[0])-1
dp[2][2][1] += int(N[1])-1
dp[3][3][1] += int(N[2])-1
for h in range(1,s+1):
    dp[h][0][0] = 0
    dp[h][0][1] = 1
    for i in range(1,4):
        dp[h][i][0] += dp[h-1][i-1][0]
        dp[h][i][1] +=  dp[h-1][i-1][1] * 9 + dp[h-1][i][0] + dp[h-1][i][1]

print(dp[s][K][0]+dp[s][K][1])
            
                
                
 



### FIXED CODE ###

#from fractions import gcd
#mod = 10 ** 9 + 7
#N = int(input())
#a = list(map(int,input().split()))
#a,b,c = map(int,input().split())
#ans = [0] * N
#math.ceilで切り上げ
#dp = [[0] * 4 for i in range(3)] #2次元配列初期化
#dp = [[[0] * 2 for i in range(3)] for j in range(5)]

import math
import string

def intinput():
    return int(input())

def listintinput():
    return list(map(int,input().split()))

def splitintinput():
    return map(int,input().split())

N = str(intinput())
K = intinput()
s = len(str(N))
dp = [[[0] * 2 for i in range(4)] for j in range(s+1)]
dp[0][0][0] = 1
for h in range(1,s+1):
    dp[h][0][1] = 1
    for i in range(1,4):
        for j in range(0,2):
            if j == 1:      
                for k in range(0,10):
                    if int(N[h-1]) == 0:
                        dp[h][i][j] += dp[h-1][i][1] + dp[h-1][i-1][1]*9
                        break
                    if int(N[h-1]) > k:
                        if k == 0:
                            dp[h][i][j] += dp[h-1][i][0] + dp[h-1][i][1]
                        if k != 0:
                            dp[h][i][j] += dp[h-1][i-1][0] + dp[h-1][i-1][1]
                    if int(N[h-1]) <= k:
                        dp[h][i][j] += dp[h-1][i-1][1]
            if j == 0:
                if int(N[h-1]) == 0:
                    dp[h][i][j] += dp[h-1][i][0]
                else:
                    dp[h][i][j] += dp[h-1][i-1][0]

print(dp[s][K][0]+dp[s][K][1])
n = int(input())
a = list(map(int, input().split()))
A = list(set(a))
if A == (0):
    ans = "Yes"
elif len(A) == 2 and 0 in A:
    if a.count(A[1]) == (2*n // 3) :
        ans = "Yes"
elif len(A) == 3:
    if A[0]^A[1]^A[2] == 0:
        if a.count(A[0]) == n//3:
            if a.count(A[1]) == n//3:
                if a.count(A[2]) == n//3:
                    ans = "Yes"
else:
    ans = "No"

print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
A = list(set(a))
A.sort()
ans = "No"
if len(A) == 1:
    if A[0] == 0:
        ans = "Yes"
elif len(A) == 2:
    if A[0] == 0:
        if a.count(A[1]) == 2* (n // 3) :
            ans = "Yes"
elif len(A) == 3:
    if A[0]^A[1]^A[2] == 0:
        if a.count(A[0]) == n//3:
            if a.count(A[1]) == n//3:
                if a.count(A[2]) == n//3:
                    ans = "Yes"
print(ans)
from collections import deque
n = int(input())
e = [[] for _ in range(n)]
AB = [list(map(int, input().split())) for _ in range(n - 1)]
AB = [(a -1, b - 1) for a, b in AB]

for itr, (a, b) in enumerate(AB):
  e[a].append(b)
  e[b].append(b)
  
colors = [-1] * n

# ２色で塗分けする。
q = deque()
# 現在見ている頂点、親の色
q.append((0, 0))
while q:
  v, pcol = q.popleft()
  # 親と異なる色で塗る。
  if colors[v] == -1:
    col = not pcol
    colors[v] = col
    for i in e[v]:
      if colors[i] == -1:
        q.append((i, col))

m = [deque([i for i in range(1, n + 1) if i % 3 == j]) for j in range(3)]

# print(m)

def opop(n):
  if n == 1 or n == 2:
    if m[n]:
      return m[n].pop()
    else:
      if m[0]:
        return m[0].pop()
      else:
        return m[3-n].pop()
  else:
    if m[n]:
      return m[n].pop()
    else:
      if m[1]:
        return m[1].pop()
      else:
        return m[2].pop()


ans = [0] * n

if sum(colors) < n // 3:
  for itr, i in enumerate(colors):
    if i:
      ans[itr] = opop(0)
    else:
      ans[itr] = opop(1)
if sum(colors) > n - (n // 3):
  for itr, i in enumerate(colors):
    if not i:
      ans[itr] = opop(0)
    else:
      ans[itr] = opop(1)
else:
  for itr, i in enumerate(colors):
    if i:
      ans[itr] = opop(1)
    else:
      ans[itr] = opop(2)
print(*ans)

### FIXED CODE ###

from collections import deque
n = int(input())
e = [[] for _ in range(n)]
AB = [list(map(int, input().split())) for _ in range(n - 1)]
AB = [(a -1, b - 1) for a, b in AB]

for itr, (a, b) in enumerate(AB):
  e[a].append(b)
  e[b].append(a)
  
colors = [-1] * n

# ２色で塗分けする。
q = deque()
# 現在見ている頂点、親の色
q.append((0, 0))
while q:
  v, pcol = q.popleft()
  # 親と異なる色で塗る。
  if colors[v] == -1:
    col = not pcol
    colors[v] = col
    for i in e[v]:
      if colors[i] == -1:
        q.append((i, col))

# print(e)
# print(colors)
        
m = [deque([i for i in range(1, n + 1) if i % 3 == j]) for j in range(3)]

# print(m)

def opop(n, ne):
  if m[n]:
    p = m[n].pop()
  else:
    if n == 1 or n == 2:
      if m[ne]:
        p = m[ne].pop()
      else:
        p = m[0].pop()
    else:
      if m[1]:
        p = m[1].pop()
      else:
        p = m[2].pop()
  return p

ans = [0] * n

if sum(colors) <= len(m[0]):
  for itr, i in enumerate(colors):
    if i:
      ans[itr] = opop(0, 0)
    else:
      ans[itr] = opop(1, 2)
elif sum(colors) >= len(m[1]) + len(m[2]):
  for itr, i in enumerate(colors):
    if not i:
      ans[itr] = opop(0, 0)
    else:
      ans[itr] = opop(1, 2)
else:
  for itr, i in enumerate(colors):
    if i:
      ans[itr] = opop(1, 0)
    else:
      ans[itr] = opop(2, 0)
print(*ans)
a, op, b = input().split()

ans = int(a) op int(b)

print(ans)


### FIXED CODE ###

while 1:
    s=input()
    if '?' in s:break
    print(int(eval(s)))
import sys 
RESOURC_DICT = dict([(k,v) for k,v in zip(range(1,10),[2,5,5,4,5,6,3,7,6])])

def get_input():
    N,M = [ int(_) for _ in input().split()]
    A = [int(_) for _ in input().split()]
    return N,M,A


def solve(N,M,A):
    dp = [-1 for _ in range(N+1)]
    for i in range(N+1):
        fill(A,dp,i)
    return dp[N]


def count_digit(number,current=0):
    if number == 0:
        return current
    else:
        return count_digit(number//10,current=current+1)

def fill(A,dp,n):
    cand = []
    for number in A:
        weight = RESOURC_DICT[number]
        if n -weight>=0:
            if n- weight == 0:
                cand.append(number)
            else:
                if dp[n-weight] != -1:
                    cand.append(max(
                        10**count_digit(dp[n-weight])*number + dp[n-weight],
                        10 * dp[n-weight] +number  )
                        )
                else:
                    cand.append(-1)
        else:
            cand.append(-1)
    dp[n] = max(cand)


if __name__ =="__main__":
    N,M,A = get_input()
    ans = solve(N,M,A)
    print(ans)

### FIXED CODE ###

import sys 
RESOURCE_DICT = dict([(k,v) for k,v in zip(range(1,10),[2,5,5,4,5,6,3,7,6])])

def get_input():
    N,M = [ int(_) for _ in input().split()]
    A = [int(_) for _ in input().split()]
    return N,M,A


def solve(N,M,A):
    sorted_A = sorted(A)[::-1]
    dp = fill_dp(N,sorted_A)
    array = find_array(dp,N,sorted_A)
    return "".join(map(str,array))

def fill_dp(N,A):
    dp = [ -100*N for _ in range(N+1)]
    dp[0] = 0
    for i in range(1,N+1):
        fill(A,dp,i,N)
    return dp

def fill(A,dp,n,N):
    cand = [ dp[n-RESOURCE_DICT[num]]+1 for num in A if n - RESOURCE_DICT[num] >= 0 ]
    dp[n] = max(cand) if len(cand) > 0  else -100*N

def find_array(dp,N,sorted_A):
    array = []
    current_n = N
    for _ in range(dp[N]):
        for number in sorted_A:
            if current_n-RESOURCE_DICT[number] >= 0  and dp[current_n-RESOURCE_DICT[number]] == dp[current_n]-1:
                array.append(number)
                current_n -= RESOURCE_DICT[number]
                break
    return array


if __name__ =="__main__":
    N,M,A = get_input()
    ans = solve(N,M,A)
    print(ans)
import math
A, B, C, D = map(int, input().split())

def lcm(x,y):
    return ((x * y)//math.gcd(x, y))

C_comp = (B//C) - ((A-1)//C)
D_comp = (B//D) - ((A-1)//D)
CD_comp = (B//lcm(C,D)) - ((A-1)//lcm(C,D))

print((B - A + 1) - (C_comp + D_comp - CD_comp))


### FIXED CODE ###

import fractions
A, B, C, D = map(int, input().split())

def lcm(x,y):
    return ((x * y)//fractions.gcd(x, y))

C_comp = (B//C) - ((A-1)//C)
D_comp = (B//D) - ((A-1)//D)
CD_comp = (B//lcm(C,D)) - ((A-1)//lcm(C,D))

print((B - A + 1) - (C_comp + D_comp - CD_comp))
[N, K] = map(int, input().split())

num_of_perms = [1] * (K-1)
for i in range(1, K-1):
    num_of_perms[i] = num_of_perms[i-1] * ((K - 2) - i + 1)

Es = []
for _ in range(0, N-1):
    [a, b] = input().split()
    Es.append(int(a))
    Es.append(int(b))

res = K * (K-1)
res %= 1000000007
for i in range(0, N):
    j = i + 1
    c = Es.count(j)
    if c > K-1:
        res = 0
        break
    res *= num_of_perms[c-1]
    res %= 1000000007

print(res)


### FIXED CODE ###

from itertools import groupby

[N, K] = map(int, input().split())

num_of_perms = [1] * (K-1)
for i in range(1, K-1):
    num_of_perms[i] = num_of_perms[i-1] * ((K - 2) - i + 1) % 1000000007

Es = []
for _ in range(0, N-1):
    [a, b] = input().split()
    Es.append(int(a))
    Es.append(int(b))

if N == 1:
    res = K
else:
    res = K * (K-1)
    res %= 1000000007
    for g in groupby(sorted(Es)):
        c = len(list(g[1]))
        if c > K-1:
            res = 0
            break
        res *= num_of_perms[c-1]
        res %= 1000000007

print(res)
H,W=map(int,input())
h,w=map(int,input())

print(H*w+W*h-h*w)

### FIXED CODE ###

H,W=map(int,input().split())
h,w=map(int,input().split())

print(H*W-(H*w+W*h-h*w))
import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
a,b=map(int,input().split())
A,B=input().split("-")
if len(A)==a and len(B)==b:
	print("Yes")
else:
	print("No")

### FIXED CODE ###

import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
a,b=map(int,input().split())
S=input().split("-")
if len(S[0])==a and len(S[1])==b:
	print("Yes")
else:
	print("No")
# coding: utf-8
# Here your code !
x = input().split()
a = x[0]
b = x[1]
men = a*b
syu = a*2+b*2
print men,
print syu

### FIXED CODE ###

# coding: utf-8
# Here your code !
a,b = input().split()
m = int(a) * 2 + int(b) * 2
s = int(a) * int(b)
print(s,m)
import numpy as np

nums = []
sortedNums = [0,0,0,0,0]
sortedRemainders = [0,0,0,0,0]
for i in range(5):
	nums.append(int(input()))

remainders = [0,0,0,0,0]
for i in range(5):
	if nums[i] % 10 == 0:
		remainders[i] = 10
	else:
		remainders[i] = nums[i] % 10

sortedRemaindersIndex = np.ndarray.tolist(np.argsort(remainders))

for i in range(5):
	sortedNums[i] = nums[sortedRemaindersIndex[i]]

elapsedTime = 0
for i in range(4):
	if sortedNums%10 == 0:
		elapsedTime += sortedNums[i]
	else:
		elapsedTime += (sortedNums[i]/10 +1) * 10

elapsedTime += sortedNums[0]

print(elapsedTime)

### FIXED CODE ###

import numpy as np

nums = []
sortedNums = [0,0,0,0,0]
sortedRemainders = [0,0,0,0,0]
for i in range(5):
	nums.append(int(input()))

remainders = [0,0,0,0,0]
for i in range(5):
	if nums[i] % 10 == 0:
		remainders[i] = 10
	else:
		remainders[i] = nums[i] % 10

sortedRemaindersIndex = np.ndarray.tolist(np.argsort(remainders))

for i in range(5):
	sortedNums[i] = nums[sortedRemaindersIndex[i]]

elapsedTime = 0
for i in range(4):
	if sortedNums[i+1] % 10 == 0:
		elapsedTime += sortedNums[i+1]
	else:
		elapsedTime += sortedNums[i+1] + 10 - sortedNums[i+1] % 10

elapsedTime += sortedNums[0]

print(elapsedTime)
while True:
    x = str(input())
    if x==0:break
    sum=0
    for i in x:
        su=su+int(i)
    print(sum)

### FIXED CODE ###

while True:
    x = str(input())
    if x=='0':break
    sum=0
    for i in x:
        sum=sum+int(i)
    print(sum)
import heapq
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

if any(a>b for a,b in zip(A,B)):
    print(-1)
    exit()

cnt = 0
for a,b in zip(A,B):
    if a != b:
        cnt += 1
if cnt == 0:
    print(0)
    exit()

hq = [(-a,i) for i,a in enumerate(B)]
heapq.heapify(hq)

ans = 0
while hq or cnt:
    _,i = heapq.heappop(hq)
    l = B[(i-1)%N]
    r = B[(i+1)%N]
    if B[i]-l-r < A[i]: continue
    k = (B[i]-A[i]) // (l+r)
    ans += k
    B[i] -= k*(l+r)
    if A[i] == B[i]:
        cnt -= 1
        continue
    heapq.heappush(hq, (-B[i],i))

if all(a==b for a,b in zip(A,B)):
    print(ans)
else:
    print(-1)

### FIXED CODE ###

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

if any(a>b for a,b in zip(A,B)):
    print(-1)
    exit()

def pb(i):
    return i-1 if i-1 >= 0 else N-1
def nx(i):
    return i+1 if i+1 < N else 0

hq = []
for i,(a,b) in enumerate(zip(A,B)):
    if a <= b - B[pb(i)] - B[nx(i)]:
        hq.append((-b,i))
heapq.heapify(hq)

ans = 0
while hq:
    _,i = heapq.heappop(hq)
    if B[i] == A[i]: continue
    l = B[pb(i)]
    r = B[nx(i)]
    if B[i]-l-r < A[i]: continue
    k = (B[i]-A[i]) // (l+r)
    ans += k
    B[i] -= k*(l+r)
    ll = B[pb(pb(i))]
    rr = B[nx(nx(i))]
    if A[nx(i)] <= r - B[i] - rr:
        heapq.heappush(hq, (-r,nx(i)))
    if A[pb(i)] <= l - B[i] - ll:
        heapq.heappush(hq, (-l,pb(i)))

if all(a==b for a,b in zip(A,B)):
    print(ans)
else:
    print(-1)
n,a,b = map(int, input().split())
sum = 0
for i in range(10):
  for j in range(10):
    for k in range(10):
      for l in range(10):
   	    if 1000*i + 100*j + 10*k + l <= n and a<i+j+k+l and i+j+k+l<b :
   		  sum += 1000*i + 100*j + 10*k + l
print(sum)


### FIXED CODE ###

n,a,b = map(int, input().split())
total = 0
for i in range(1,n+1):
  array = list(map(int,str(i)))
  if a<= sum(array) and sum(array)<=b :
    total += i
print(total)
n=int(input())
a=map(int,input(),split())

ans=0
cur_max=0

for x in a:
  if cur_max>x:
    ans+=cur_max-x
  cur_max=max(cur_max,x)

print(ans)

### FIXED CODE ###

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

ans=0
cur_max=0

for x in a:
  if cur_max>x:
    ans+=cur_max-x
  cur_max=max(cur_max,x)

print(ans)
prev = 0
for i in range(len(N)):
  if 0 <= int(N[i]) + prev < 5:
    count += int(N[i]) + prev
    prev = 0
  elif 6 <= int(N[i]) + prev <= 9:
    count += 10 - (int(N[i]) + prev)
    prev = 1
  elif int(N[i]) + prev == 10:
    prev = 1
  else:
    if i < (len(N) - 1) and int(N[i+1]) < 5:
      count += 5
      prev = 0
    else:
      count += 5
      prev = 1
count = count + prev

### FIXED CODE ###

N = input()
count = 0
prev = 0
for i in range(len(N)):
  if 0 <= int(N[i]) + prev < 5:
    count += int(N[i]) + prev
    prev = 0
  elif 6 <= int(N[i]) + prev <= 9:
    count += 10 - (int(N[i]) + prev)
    prev = 1
  elif int(N[i]) + prev == 10:
    prev = 1
  else:
    if (i < (len(N) - 1) and int(N[i+1]) < 5) or i == len(N) - 1:
      count += 5
      prev = 0
    else:
      count += 5
      prev = 1
count = count + prev
print(count)
n,m=map(int,input().split())
def yak1(n,m):
  l=[]
  for i in range(1,min(int((m)**1/2),m//n)+1):
    if m%i==0:
      l.append(i)
      if m//(m//i)!=m/i and m//i<=m/n:
        l.append(m//i)
  return l
print(max(yak1(n,m)))     


### FIXED CODE ###

def make_divisors(n,m):
    divisors = []
    for i in range(1,min(int(m**(1/2))+1,int(m//n)+1)):
      if m % i == 0:
          divisors.append(i)
          if i != m // i and m//i<=m//n:
              divisors.append(m//i)
    return divisors
n,m=map(int,input().split())
print(max(make_divisors(n,m)))
h = int(input())
a = int(input())

return math.ceil(h/a)


### FIXED CODE ###

import math

val = input().split(' ')
h = float(val[0])
a = float(val[1])

print(math.ceil(h/a))
data = input().split(" ")
A = input().split(" ")
B = input().split(" ")
total = 0
a = 0
b = 0

for i in data:
    i = int(i)
for i in A:
    i = int(i)
for i in B:
    i = int(i)

for i in range(data[2]):
    data1 = input().split()
    for i in data1:
        i = int(i)
    data2 = A[data1[0]] + B[data[1]] - data1[2]
    if total > data2:
        total = data2

for i in A:
    if a > i:
        a = i
for i in B:
    if b > i:
        b = i

if total > a+b:
    total = a+b

print(total)

### FIXED CODE ###

data = input().split(" ")
A = input().split(" ")
B = input().split(" ")
total = 1000000
a = 1000000
b = 1000000
j = 0
for i in data:
    data[j] = int(i)
    j += 1
j = 0
for i in A:
    A[j] = int(i)
    j += 1
j = 0
for i in B:
    B[j] = int(i)
    j += 1


for i in range(data[2]):
    data1 = input().split()
    j = 0
    for i in data1:
        data1[j] = int(i)
        j += 1
    data2 = A[data1[0]-1] + B[data1[1]-1] - data1[2]
    if total > data2:
        total = data2

for i in A:
    if a > i:
        a = i
for i in B:
    if b > i:
        b = i

if total > a+b:
    total = a+b

print(total)
import math as m
import time
N=int(input())
ans=[0]*N
for x in range(1,int(m.sqrt(N-5))+1):
    for y in range(1,x+1):
        if x**2+y**2+x*y+x+y+1>N:
            break
        for z in range(1,y+1):
            if x**2+y**2+x*y+x*z+y*z+z**2>N:
                break
            if len(list(set([x,y,z])))==3:
                ans[x**2+y**2+x*y+x*z+y*z+z**2-1]+=6
            elif len(list(set([x,y,z])))==2:
                ans[x**2+y**2+x*y+x*z+y*z+z**2-1]+=3
            elif len(list(set([x,y,z])))==1:
                ans[x**2+y**2+x*y+x*z+y*z+z**2-1]+=1

for a in ans:
    print(a)


### FIXED CODE ###

import math as m
N=int(input())
ans=[0]*N
if N>5:
    for x in range(1,int(m.sqrt(N-5))+1):
        for y in range(1,x+1):
            if x**2+y**2+x*y+x+y+1>N:
                break
            for z in range(1,y+1):
                if x**2+y**2+x*y+x*z+y*z+z**2>N:
                    break
                if len(list(set([x,y,z])))==3:
                    ans[x**2+y**2+x*y+x*z+y*z+z**2-1]+=6
                elif len(list(set([x,y,z])))==2:
                    ans[x**2+y**2+x*y+x*z+y*z+z**2-1]+=3
                elif len(list(set([x,y,z])))==1:
                    ans[x**2+y**2+x*y+x*z+y*z+z**2-1]+=1

for a in ans:
    print(a)
N = input()
ans = 'No'
for i in range(len(N)):
    if N[i] == 7:
        global ans
        ans = 'Yes'
        break
    else:
        continue
print(ans)


### FIXED CODE ###

N = int(input())
a1 = N % 10
a2 = ((N % 100) - a1) / 10
a3 = N // 100
if a1 == 7 or a2 == 7 or a3 ==7:
    print('Yes')
else:
    print('No')
x, a = map(input()).split()

if x<a:
  print('10')
else:
  print('0')
  

### FIXED CODE ###

x,a = map(int,input().split())
if x<a:
    print('0')
else:
    print('10')
n=int(input())
A=list(map(int,input().split()))
Q=int(input())
BC=[list(map(int,input().split())) for _ in range(Q)]

cnt=[0]*(10**5)
for a in A:
  cnt[a]+=1
total=sum(A)
for b,c in BC:
  total+=c*cnt[b]
  total-=b*cnt[b]
  cnt[c]+=cnt[b]
  cnt[b]=0
  print(total)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
Q=int(input())
BC=[list(map(int,input().split())) for _ in range(Q)]

cnt=[0]*(10**5+1)
for a in A:
  cnt[a]+=1
total=sum(A)
for b,c in BC:
  total+=(c-b)*cnt[b]
  cnt[c]+=cnt[b]
  cnt[b]=0
  print(total)
n = int(input())
cumsum_w = [0]
for w in map(int, input().split()):
  cumsum_w.append(cumsum_w[-1] + w)
minimum = 100
for s in w[1:-1]:
  minimum = min(minimum, abs(w[-1] - 2 * s))
print(minimum)

### FIXED CODE ###

n = int(input())
cumsum_w = [0]
for w in map(int, input().split()):
  cumsum_w.append(cumsum_w[-1] + w)
minimum = 100
for s in cumsum_w[1:-1]:
  minimum = min(minimum, abs(cumsum_w[-1] - 2 * s))
print(minimum)
from bisect  import bisect_left

n = int(input())
a = list(map(int,input().split()))
a.sort()
b = [2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 
     131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 
     67108864, 134217728, 268435456, 536870912]

t = []
bIdx = 0
for aa in a :
    while b[bIdx] <= aa:
        bIdx += 1   
    t.append(b[bIdx]-aa)
t.sort(reverse=True)


u = [0 for i in range(len(t))]

#print(a)        
#print(t)
sum = 0
for i in range (len(a)-1,-1,-1):
    k = bisect_left(a,t[i])
    #print(t[i],k)a
    if a[k] == t[i] and k < i:
        #print(a[i],t[i],i)
        sum += 1
        a[k] -= 0.1
        a[i] += 0.1
        u[k] += 1
print(sum)

### FIXED CODE ###

from bisect  import bisect_left

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

sum = 0
for i in range (len(a)-1,-1,-1):

    b = 1
    while b <= a[i]:
        b = b<<1
    t = b - a[i]
    #print("2^",t)

    k = bisect_left(a,t)
    if a[k] == t and k < i:
        sum += 1
        a[k] -= 0.1
        a[i] += 0.1
print(sum)
num = int(input())

s1,s2 = input().split()

ans = ''

for i in range(num):
	ans = ans + s1[i]
    ans = ans + s2[i]

print(ans)

### FIXED CODE ###

num = int(input())
 
s1,s2 = input().split()
 
ans = ''
 
for i in range(num):
	ans = ans + s1[i]
	ans = ans + s2[i]
print(ans)
a,b=map(int,input().split())
if (a+b)%2 == 1:
  print('IMPOSSIBLE')
  else:
    print((a+b)//2)

### FIXED CODE ###

a,b=map(int,input().split())
if (a+b)%2 ==0:print((a+b)//2)
else:
  print('IMPOSSIBLE')
_,m=map(int,input().split())
a=list(map(int,input().split()))
cnt=0
temp=sum(a)
for v in a:
    if v>=a/(4*m): cnt+=1
if cnt>=m: print("Yes")
else: print("No")

### FIXED CODE ###

_,m=map(int,input().split())
a=list(map(int,input().split()))
cnt=0
temp=sum(a)
for v in a:
    if v>=temp/(4*m): cnt+=1
if cnt>=m: print("Yes")
else: print("No")
N = int(input())
X = int(input(), 2)

def rev(num, i):
  i = N - 1 - i
  return num ^ (1 << i)



def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f



for i in range(N):
  X = rev(X, i)
    
  fn = X
  cnt = 0
  
  while fn != 0:
    fn = fn % popcount(fn)
    cnt += 1
  print(cnt)
  
  X = rev(X, i)

      

### FIXED CODE ###

N = int(input())
X = input()

X_int = int(X, 2)
cnt1 = bin(X_int).count('1')
pcXi01 = cnt1 + 1
pcXi10 = cnt1 - 1
zero_idx = N + 5
if cnt1 == 1:
  for i in range(N):
    if X[i] == '1':
      zero_idx = i

if pcXi10 < 1:
  pcXi10 = 1
Xmod01 = X_int % pcXi01
Xmod10 = X_int % pcXi10

tmp01 = [1]
tmp10 = [-1]
for i in range(N - 1):
  tmp01.append(tmp01[i]*2 % pcXi01)
  tmp10.append(tmp10[i]*2 % pcXi10)

init_n = [0] * N
next_n = [0] * N
for i in range(N):
  if X[i] == '0':
    next_n[i] = (Xmod01 + tmp01[N - 1 - i]) % pcXi01
  else:
    next_n[i] = (Xmod10 + tmp10[N - 1 - i]) % pcXi10

for i in range(N):
  fn = 0
  if i == zero_idx:
    print(0)
    continue

  n = next_n[i]
  fn += 1
  while n != 0:
    n = n % bin(n).count('1')
    fn += 1
  
  print(fn)