Harryxun/stf_run huggingface dataset:
n, m = map(int, input().split())


a = [[],[],[]]
for i in range(m):
    s, c = map(int, input().split())
    if not c in a[s-1]:
        a[s-1].append(c)
    
ans = 0
if m==0:
    if n==3:
        print(100)
    elif n==2:
        print(10)
    else :
        print(0)
elif (len(a[0]) > 1) or (len(a[1]) > 1) or (len(a[2]) > 1):
    print(-1)
else:
    if (n==3 or n==2) and len(a[0]) == 0:
        a[0][0]=1
    if (n==3 or n==2) and a[0][0] == 0:
        print(-1)
    else:
        for i in range(n):
            if len(a[i]) == 1:
                ans += a[i][0] * (10**(n-1-i))
        print(ans)








### FIXED CODE ###

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


a = [[],[],[]]
for i in range(m):
    s, c = map(int, input().split())
    if not c in a[s-1]:
        a[s-1].append(c)
    
ans = 0
if m==0:
    if n==3:
        print(100)
    elif n==2:
        print(10)
    else :
        print(0)
elif (len(a[0]) > 1) or (len(a[1]) > 1) or (len(a[2]) > 1):
    print(-1)
else:
    if (n==3 or n==2) and len(a[0]) == 0:
        a[0].append(1)
    if (n==3 or n==2) and a[0][0] == 0:
        print(-1)
    else:
        for i in range(n):
            if len(a[i]) == 1:
                ans += a[i][0] * (10**(n-1-i))
        print(ans)
start = 0
for l in input():
    if start == 0:
        start += 1
    else:        
        l = list(map(int, input().split()))
        break
count = 0
print(l)
for i in l:
    while True:
        if i%2 == 0:
            count += 1
            i = i/2
        else:
            break
print(count)

### FIXED CODE ###

import sys

start = 0
for l in sys.stdin:
    if start == 0:
        start += 1
    else:
        list1 = list(map(int, l.split()))
        break
count = 0
for i in list1:
    while True:
        if i%2 == 0:
            count += 1
            i = i/2
        else:
            break
print(count)
import math

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

def combinations_count(a, b):
    return math.factorial(a)//(math.factorial(a-b)*math.factorial(b))

if n==k:
    print(1)
    for i in range(2,k+1):
        print(0)
            
else:
    for i in range(1,k+1):
        #print(k-1,i-1)    
        #青のグループ分けの組合せ
        b_num = combinations_count(k-1,i-1)
        #赤を並べて，そこに青のグループを置く組合せ
        a_num = combinations_count(n-k+1,i)
        #出力
        print((b_num*a_num)%(10**9+7))

### FIXED CODE ###

import math

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

def combinations_count(a, b):
    return math.factorial(a)//(math.factorial(a-b)*math.factorial(b))


blue = k
#両端を除いた隙間の数
blue_sp = k-1
red = n-k
#両端を含む隙間の数
red_sp = red+1


#青をグループに分けて，赤の隙間に入れる組合せを考える
#1から
for i in range(1,blue+1):
    #print(blue_sp,i-1,":",red_sp,i)        

    #出力
    #青のグループ数が赤の隙間より多い場合
    if i > red_sp:
        print(0)
    else:       
        #青のグループ分けの組合せ(両端を除いた隙間，選択する数)
        b_num = combinations_count(blue_sp,i-1)
        #赤を並べて，そこに青のグループを置く組合せ
        a_num = combinations_count(red_sp,i)
        print((b_num*a_num)%(10**9+7))
# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# MOD = 10 ** 9 + 7
#

import sys

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

D = dict()
# 1から9の数値:必要なマッチの本数
for a in A:
    D[a] = min(D.get(a, 999), B[a])

L = []
# (必要なマッチの本数, 1～10の数値)
for k, v in D.items():
    L.append((v, k))
L.sort()


# 残りn本のマッチ、現在の値val
# 戻り値：その最大値
def f(n, val):
    if n < 0:
        return 0
    elif n == 0:
        ret = list(str(val))
        ret.sort(reverse=True)
        print("".join(ret))
        sys.exit(0)
        return 0

    ret = 0
    for l in L:
        ret = max(ret, f(n - l[0], val * 10 + l[1]))
    return ret


ans = f(N, 0)

### FIXED CODE ###

# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# MOD = 10 ** 9 + 7
# メモ化再起
from functools import lru_cache
import sys

sys.setrecursionlimit(100000000)

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
match = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]



@lru_cache(maxsize=1000000)
def f(n):
    maxval = -float('inf')
    for a in A:
        tmp = n - match[a]
        if tmp == 0:
            maxval = max(maxval, a)
        elif tmp > 0:
            # maxval = max(maxval, f2(f(n - match[a]) * 10 + a))
            maxval = max(maxval, f(n - match[a]) * 10 + a)
    return maxval

@lru_cache(maxsize=1000000)
def f2(n):
    if n < 0:
        return 0
    n = list(str(n))
    n.sort(reverse=True)
    return int("".join(n))

ans = f(N)
print(f2(ans))
N=int(input())
sisterN=[]
SISTERn=[]
SIStern=[]
for n in range(N):
    _=int(input())
    if _<30000:
        _s= _
        if sisterN.count(_s)==1:
            sisterN.remove(_s)
        else:
            sisterN.append(_s)
    elif 30001<_<80000:
        _m= _
        if SISterN.count(_m)==1:
            SISterN.remove(_m)
        else:
            SISterN.append(_m)
    else:
        _b= _
        if SISTERn.count(_b)==1:
            SISTERn.remove(_b)
        else:
            SISTERn.append(_b)
print(len(sisterN)+len(SISTERn)+len(SIStern))

### FIXED CODE ###

N=int(input())
S=set()

for n in range(N):
    _=int(input())
    if _ in S:
        S.remove(_)
    else:
        S.add(_)

print(len(S))
def f(n):
    if n<2:
        return 1
    return n*f(n-2)

N = int(input())
if N%2==1:
    print(0)
    exit(1)
ans = 0
for i in range(1, len(str(N))):
    # if i != len(str(N))-1:
    #     ans+=(10**(i))
    ans += N//5//2
    N //= 10
ans = list(str(ans))
ans2 = []
for i in range(len(ans)):
    i = int(i)
    if i==len(ans)-1:
        res = 0
    elif i==len(ans)-2:
        res = 1
    elif i==len(ans)-3:
        res = 3
    elif i==0:
        res = 4
    else:
        res = 8
    ans2.append(str(res+int(ans[i])))
ans2.reverse()
ans2 = int(''.join(ans2))
print(ans2)

### FIXED CODE ###

N = int(input())
if N%2==1:
    print(0)
    exit(0)
ans = 0
tmp = N
for i in range(1, 100):
    ans += tmp//pow(5, i)//2
print(ans)
import queue
import sys
sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
XYZ = []
for _ in range(M):
    XYZ.append(tuple(map(int, input().split())))

G=[[] for _ in range(N+1)]
for el in XYZ:
    G[el[0]].append(el[1])
    G[el[1]].append(el[0])
#print(G)

not_seen=list(range(1,N+1))
todo=queue.Queue()
def dfs(n):
    if n in not_seen:
        not_seen.remove(n)
    for nxt in G[n]:
        if nxt in not_seen:
            todo.put(nxt)
    if todo.empty():
        return None
    else:
        dfs(todo.get())


cnt=0
while not_seen:
    cnt+=1
    dfs(not_seen[0])
print(cnt)
import queue
import sys
sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
XYZ = []
for _ in range(M):
    XYZ.append(tuple(map(int, input().split())))

G=[[] for _ in range(N+1)]
for el in XYZ:
    G[el[0]].append(el[1])
    G[el[1]].append(el[0])
#print(G)

not_seen=list(range(1,N+1))
todo=queue.Queue()
def dfs(n):
    if n in not_seen:
        not_seen.remove(n)
    for nxt in G[n]:
        if nxt in not_seen:
            todo.put(nxt)
    if todo.empty():
        return None
    else:
        dfs(todo.get())


cnt=0
while not_seen:
    cnt+=1
    dfs(not_seen[0])
print(cnt)


### FIXED CODE ###

import queue
import sys
sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
XYZ = []
for _ in range(M):
    XYZ.append(tuple(map(int, input().split())))

G=[[] for _ in range(N+1)]
for el in XYZ:
    G[el[0]].append(el[1])
    G[el[1]].append(el[0])
#print(G)

seen=[False]*(N+1)
todo=queue.Queue()
def bfs(n):
    seen[n]=True
    for nxt in G[n]:
        if seen[nxt]==False:
            bfs(nxt)


cnt=0
for check in range(1, N+1):
    if seen[check]==False:
        cnt+=1
        bfs(check)
print(cnt)
n = int(input())
a = []
for i in range(n):
    _ = list(map(int, input().split()))
    a.append(_)
if n == 1:
    print(str(a[0][0]) + ' ' + str(a[0][1]) + ' ' + str(a[0][2])) 
else:    
    check = False
    for i in range(101):
        for j in range(101):
            b = 0
            while b < n-1:
                if b == 0:
                    h = abs(i - a[b][0]) + abs(j - a[b][1]) + a[b][2]
                    b +=1
                else:
                    de = max(h - abs(i - a[b][0]) - abs(j - a[b][1]),0)
                    if de == a[b][2]:
                        b+=1
                    else:
                        break
            if b == n-1:
                ans = str(i) + ' ' + str(j) + ' ' +str(h)
                check = True
            if check:
                break
        if check:
            break
    print(ans)

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
    _ = list(map(int, input().split()))
    a.append(_)
a = sorted(a, key=lambda x:x[2],reverse = True)

check = False
    
for i in range(101):
    for j in range(101):
        b = 0
        while b < n:
            if b == 0:
                h = abs(i - a[b][0]) + abs(j - a[b][1]) + a[b][2]
                b +=1
            else:
                de = max(h - abs(i - a[b][0]) - abs(j - a[b][1]),0)
                if de == a[b][2]:
                    b+=1
                else:
                    break
        if b == n:
            ans = str(i) + ' ' + str(j) + ' ' +str(h)
            check = True
        if check:
            break
    if check:
        break
print(ans)
import collections
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

H, W, *S = open(0).read().split()
H, W = [int(_) for _ in [H, W]]
A = []
B = []
C = []
for i in range(H * W):
    x, y = divmod(i, W)
    if S[x][y] == '.':
        for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            nx, ny = x + dx, y + dy
            if not (0 <= nx < H and 0 <= ny < W):
                continue
            if S[nx][ny] == '.':
                A += [i]
                B += [nx * W + ny]
                C += [1]
print(int(np.max(floyd_warshall(csr_matrix((C, (A, B)), shape=(H*W, H*W))))))


### FIXED CODE ###

import copy, collections, itertools
H, W = [int(_) for _ in input().split()]
S_ = [['#'] * (W + 2)] + [['#'] + list(input()) + ['#']
                          for _ in range(H)] + [['#'] * (W + 2)]
ans = 0
for i, j in itertools.product(range(1, H + 1), range(1, W + 1)):
    if S_[i][j] == '.':
        S = copy.deepcopy(S_)
        S[i][j] = '#'
        q = collections.deque([(i, j, 0)])
        while q:
            x, y, d = q.popleft()
            for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                if S[x + dx][y + dy] == '.':
                    X, Y = x + dx, y + dy
                    S[X][Y] = '#'
                    q += [(X, Y, d + 1)]
        ans = max(d, ans)
print(ans)
N = int(input())
S = str(input())
if S[0:N/2] * 2 = S:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

N = int(input())
S = str(input())
if S[0:N//2] * 2 == S:
    print("Yes")
else:
    print("No")
import itertools

n = int(input())
a = tuple(map(int,input().split()))
ans = 0
for l in itertools.product([-1,0,1],n):
  t = 1
  for i in range(n):
    t*=(a[i]+l[i])
  if t%2==0:
    ans+=1
print(ans)

### FIXED CODE ###

import itertools

n = int(input())
a = tuple(map(int,input().split()))
ans = 0
for l in itertools.product([-1,0,1],repeat=n):
  t = 1
  for i in range(n):
    t*=(a[i]+l[i])
  if t%2==0:
    ans+=1
print(ans)
import math 

x = int(input())
a = []
if x == 1:
  print(1)
for i in range(1,x):
  for j in range(2,32):
    if math.log(i,j).is_integer() == True:
      a.append(i)
print(max(a))

### FIXED CODE ###

x = int(input())
a = []
for i in range(1,32):
  for j in range(2,9):
    if i ** j <= x:
      a.append(i**j)
print(max(a))
import collections as cl
from math import factorial

def comb(n, r):
  if n >= r:
    return int(factorial(n) / factorial(r) / factorial(n - r))
  elif n == 1:
      return 1:
  else:
    return 0
  
n = int(input())
a = list(map(int, input().split()))

clc = cl.Counter(a)

# 1. 数字が等しいペアを選ぶ総数
npair = 0
for (k, v) in clc.items():
  npair += comb(v, 2)

# 2. (取り除いた数字と同じ数字を選ぶ総数) - (1)
for a_ in a:
  print(npair - (clc[a_] - 1))

### FIXED CODE ###

#!/usr/bin/env python3
import collections as cl
from math import factorial

def comb(n, r):
    if n >= r:
        return factorial(n) // (factorial(n - r) * factorial(r))
    else:
        return 0
  
n = int(input())
a = list(map(int, input().split()))

clc = cl.Counter(a)

# 1. 数字が等しいペアを選ぶ総数
npair = 0
for (k, v) in clc.items():
    npair += comb(v, 2)

# 2. (取り除いた数字と同じ数字を選ぶ総数) - (1)
for a_ in a:
    print(npair - (clc[a_] - 1))
a,w=map(int,input().split())
b,y=map(int,input().split())
n=int(input())
if w=y:
  print(”NO")
else:
  print("YES") if abs(a-b)/(w-y)<=n else print("NO")

### FIXED CODE ###

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

b,y=map(int,input().split())

n=int(input())

if w<=y:

  print("NO")

else:

  print("YES") if abs(a-b)/(w-y)<=n else print("NO")
a, b = map(input(), split())

if a*b % 2 == 0
     print('Odd')
else
    print('even')

### FIXED CODE ###

a, b = map(int, input().split())
if a*b % 2 :
    print('Odd')
else :
    print('Even')
N, K = map(int, input().split())
H = list(map(int, input().split()))
H.sort(reverse=True)
if K <= N and K != 0:
    H.remove(H[:K])
elif K > N and K != 0:
    H.clear()
print(sum(H))

### FIXED CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
H.sort()
if K == 0:
    pass
elif K > N:
    H.clear()
else:
    H = H[:-K]
print(sum(H))
mod=7+10**9
n=int(input())
c=[int(input()) for _ in [0]*n]
data=[0]*n+[1]
def dp(k,l):
    if data[k]>0:
        return data[k]
    if k>=n-1:
        return 1
    ans=0
    i=0
    while i<len(l):
        if l[i]==l[0]:
            j=i
            while j<len(l) and l[j]==l[0]:
                j+=1
            ans+=dp(j,l[j:])
            ans%=mod
            i=j
        i+=1
    data[k]=ans%mod
    return data[k]
print(dp(c))

### FIXED CODE ###

mod=7+10**9
n=int(input())
c=['$']+[int(input()) for _ in [0]*n]
data=[1]+[0]*n
s={}

for i in range(1,n+1):
  if c[i] in s.keys():
    if c[i]!=c[i-1]:
      s[c[i]]+=data[i-1]
      s[c[i]]%=mod
  else:
    s[c[i]]=data[i-1]
  data[i]=s[c[i]]%mod
        
print(data[n])
import math

a,b = map(input().split())
a = int(a)
b = int(b[0])*100+int(b[2]+b[3])
print((a*b)//100)

### FIXED CODE ###

a = input().split()
s1 = a[0]
s2 = a[1]
num1 = int(s1)
num2 = int(s2[0])*100 + int(s2[2]+s2[3])

print((num1*num2)//100)
a,b=map(int,input().split())
if a<b
 print('a<b')
 elif a>b
 print('a>b')
 else:
 print('a==b')

### FIXED CODE ###

a, b = map(int,input().split())
 
if a > b:
    print('a > b')
elif a < b:
    print('a < b')
else:
    print('a == b')
def make_divisors(n,m):
    divisors = []
    for i in range(1, int(n)):
        if n % i == 0 and m % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors
n,m,k = map(int,input().split())
if n <= m:
    c = make_divisors(n,m)
else:
    c = make_divisors(m,n)
print(c[-1+k]

### FIXED CODE ###

def make_divisors(n,m):
    divisors = []
    for i in range(1,n+1):
        if n % i == 0 and m % i == 0:
            divisors.append(i)
    divisors.sort()
    return divisors
n,m,k = map(int,input().split())
if n <= m:
    c = make_divisors(n,m)
else:
    c = make_divisors(m,n)
c.reverse()
print(c[k-1])
# -*- coding: utf-8 -*-
import sys


input = sys.stdin.readline


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

dp = [[0 for _ in range(3)] for _ in range(N + 1)]

or i in range(N):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + DATA[i][k])

res = 0

for v in range(3):
    res = max(res, dp[N][v])

print(res)


### FIXED CODE ###

import sys

input = sys.stdin.readline

vacation = int(input())
lst_happiness = [list(map(int, input().split())) for i in range(vacation)]

dp = [[0 for i in range(3)] for j in range(vacation+1)]
def chmax(a, b):
    if a > b:
        return a
    else:
        return b

for i in range(vacation):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i+1][k] = chmax(dp[i+1][k], dp[i][j] + lst_happiness[i][k])
ans = 0
for i in range(3):
    ans = chmax(ans, dp[vacation][i])
print(ans)
import sys

def comb(n, r):
    r = min(r, n - r)
    if r == 0: return 1
    if r == 1: return n
    numerator = list(range(n-r+1, n+1))
    denominator = list(range(1, r+1))
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result

n, k = map(int, sys.stdin.read().split())

def solve(n, k):
    p = int(str(n)[0])
    l = len(str(n))

    if k == 1:
        return 9 * (l - 1) + p
    
    elif k == 2:
        res = 0
        for i in range(1, l-1):
            res += comb(i, 1) * 9 * 9
        res += comb(l-1, 1) * 9 * (p - 1)
        res += solve(int(str(n)[1:]), 1)
        return res
    
    elif k == 3:
        res = 0
        for i in range(2, l-1):
            res += comb(i, 2) * 9 ** 2 * 9
        res += comb(l-1, 2) * 9 ** 2 * (p - 1)
        res += solve(int(str(n)[1:]), 2)
        return res

def main():
    return solve(n, k)

if __name__ == '__main__':
    ans = main()
    print(ans)

### FIXED CODE ###

import sys

def comb(n, r):
    if r > n or r < 0: return 0
    r = min(r, n - r)
    if r == 0: return 1
    if r == 1: return n
    numerator = list(range(n-r+1, n+1))
    denominator = list(range(1, r+1))
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result

n, k = map(int, sys.stdin.read().split())

def solve(n, k):
    p = int(str(n)[0])
    l = len(str(n))

    if k == 1:
        return 9 * (l - 1) + p
    
    elif k == 2:
        if l <= 1:
            return 0
        res = 0
        for i in range(1, l-1):
            res += comb(i, 1) * 9 * 9
        res += comb(l-1, 1) * 9 * (p - 1)
        res += solve(int(str(n)[1:]), 1)
        return res
    
    elif k == 3:
        if l <= 2:
            return 0
        res = 0
        for i in range(2, l-1):
            res += comb(i, 2) * 9 ** 2 * 9
        res += comb(l-1, 2) * 9 ** 2 * (p - 1)
        res += solve(int(str(n)[1:]), 2)
        return res

def main():
    return solve(n, k)

if __name__ == '__main__':
    ans = main()
    print(ans)
k,s=map(int,input().split())
x=[0]*k
for i in range(0,k):
  x[i]=i
x.append(k)
a=int(s/3)-1
count=0
for i in range(0,len(x)):
  stemp=s-x[i]
  for j in range(0,stemp+1):
    if s-x[i]-x[j] in x:
      count=count+1
print(count)


### FIXED CODE ###

k,s=map(int,input().split())
temp=[1 for y in range(k+1) for x in range(k+1) if 0<=s-x-y<=k]
print(len(temp))
N,K=map(int,input().split())
a=[int(i) for i in input().split()]
S=[0 for i in range(N+1)]
for i in range(1,N+1):
    S[i]=S[i-1]+a[i-1]
L=[]
for i in range(N+1):
    for j in range(i):
        L.append(S[i]-S[j])
X=[0 for i in range(35)]
for i in L:
    X[(len(bin(i))-2)]+=1
#print(X)
j=35
for i in range(34,-1,-1):
    if X[i]>=K:
        j=i
        break
R=[]
for i in L:
    if len(bin(i))==j+2:
        R.append(i)
R.sort(reverse=True)
ans=R[0]
#print(sorted(L,reverse=True))
#print(R,j)
for i in range(1,K):
    ans=ans&R[i]
print(ans)


### FIXED CODE ###

N,K=map(int,input().split())
a=[int(i) for i in input().split()]
S=[0 for i in range(N+1)]
for i in range(1,N+1):
    S[i]=S[i-1]+a[i-1]
List=[]
for i in range(N+1):
    for j in range(i):
        List.append(S[i]-S[j])
List.sort(reverse=True)
def program(Y,L):
    #print(L)
    M=len(L)
    t=[bin(i)[2:][::-1] for i in L]
    b=[i+"0"*(Y-len(i)) for i in t]
    X=[[] for i in range(Y)]
    for i in b:
        for j in range(Y):
            if i[j]=="1":
                X[j].append(i)
    #print("X",X)
    l=Y
    for i in range(Y-1,-1,-1):
        if len(X[i])>=K:
            l=i
            break
    if l==Y:
        return 0
    #print(X[l])
    R=[]
    for i in X[l]:
        if i[:l]=="":
            R.append(0)
            continue
        R.append(int(i[:l][::-1],2))
    R.sort(reverse=True)
    return program(l,R)+2**l
#print(K,N)
print(program(42,List))
import numpy as np

N = int(input())
X = str(input())
num_one = X.count("1")

dp = [-1] * N
dp[0] = 0
def dfs(n):
    if dp[n] == -1:
        dp[n] = 1 + dfs(n % bin(n).count('1'))
    return dp[n]

num_one = X.count("1")
bool_arr = np.array([True if X[N-i-1] == "1" else False for i in range(N)])
zero_ver = np.array([pow(2,  i, num_one + 1) for i in range(N)])
zero_ver_sum = sum(zero_ver[bool_arr])

one_ver = -1
flag = False
if num_one != 1:
    one_ver = np.array([pow(2,  i, num_one - 1) for i in range(N)])
else:
    flag = True
one_ver_sum = sum(one_ver[bool_arr])
for i in range(1,N+1):
    start = 0
    if bool_arr[N-i] == False:
        start = (zero_ver_sum + pow(2, N - i, num_one + 1)) % (num_one + 1)
        print(dfs(start)+1)
    else:
        if flag:
            print(0)
        else:
            start = (one_ver_sum - pow(2, N - i, num_one - 1))  %  (num_one - 1)
            print(dfs(start)+1)


### FIXED CODE ###

import numpy as np

N = int(input())
X = str(input())
num_one = X.count("1")

dp = [-1] * N
dp[0] = 0
def dfs(n):
    if dp[n] == -1:
        dp[n] = 1 + dfs(n % bin(n).count('1'))
    return dp[n]

num_one = X.count("1")
bool_arr = np.array([True if X[N-i-1] == "1" else False for i in range(N)])
zero_ver = np.array([pow(2,  i, num_one + 1) for i in range(N)])
zero_ver_sum = sum(zero_ver[bool_arr])

one_ver = -1
one_ver_sum = 0
flag = False
if num_one != 1:
    one_ver = np.array([pow(2,  i, num_one - 1) for i in range(N)])
    one_ver_sum = sum(one_ver[bool_arr])
else:
    flag = True
for i in range(1,N+1):
    start = 0
    if bool_arr[N-i] == False:
        start = (zero_ver_sum + pow(2, N - i, num_one + 1)) % (num_one + 1)
        print(dfs(start)+1)
    else:
        if flag:
            print(0)
        else:
            start = (one_ver_sum - pow(2, N - i, num_one - 1))  %  (num_one - 1)
            print(dfs(start)+1)
A,B,C=input().split()
print(A[0].upper+B[0].upper+C[0].upper)

### FIXED CODE ###

A, B, C = input().split()
print(A[0].upper()+B[0].upper()+C[0].upper())