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

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

magic = [list(map(int, input().split())) for _ in range(N)]
inf = float('inf')
dp = [inf] * (H + 1)
dp[0] = 0
for i in range(H):
    if dp[i] == inf:
        continue
    currCost = dp[i]
    for dmg, cost in magic:
        totalDmg = i + dmg
        if totalDmg > H:
            totalDmg = H
        totalCost = currCost + cost
        if totalCost < dp[totalDmg]:
            dp[totalDmg] = totalCost
print(dp[H])

### FIXED CODE ###

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

magic = [list(map(int, input().split())) for _ in range(N)]
inf = float('inf')
dp = [inf] * (H + 1)
dp[0] = 0
for i in range(H):
    if dp[i] == inf:
        continue
    currCost = dp[i]
    for dmg, cost in magic:
        totalDmg = i + dmg
        if totalDmg > H:
            totalDmg = H
        totalCost = currCost + cost
        if totalCost < dp[totalDmg]:
            dp[totalDmg] = totalCost
print(dp[H])
### BUGGY CODE ###

def g(field,x,y,h,w,ans):
     cnt = 1
     if x == 0:
          if y == 0:
               flag = h+w+1
          else:
               flag = 1+ans[y-1][x]
     if y == 0:
          flag = flag = 1+ans[y][x-1]
     else:
          flag = min(ans[y][x-1],ans[y-1][x]) + 1
     while cnt < flag:
          for i in range(0,cnt+1):
               j = cnt - i
               if i == 0:
                    search = [[x,y+j]]
               elif j == 0:
                    search = [[x+i,y]]
               else:
                    search = [[x+i,y+j],[x-i,y+j]]
               for p in search:
                    if (0<=p[0]) and (p[0]<=w-1) and (0<=p[1]) and (p[1]<=h-1):
                         if field[p[1]][p[0]] == "#":
                              return cnt
          cnt += 1
     return flag


def f():
     answer = 0
     h,w = map(int,input().split())
     field = []
     for i in range(h):
          field.append(list(input()))
     ans = [[h+w+1]*w for i in range(h)]
     
     for i in range(0,h):
          for j in range(0,w):
               if field[i][j] == "#":
                    ans[i][j] = 0
               elif field[i][j] == ".":
                    ans[i][j] = g(field,j,i,h,w,ans)
                    answer = max(answer,ans[i][j])
     print(answer)
     #print(ans)
     return
f()

### FIXED CODE ###

def f():
     h,w = map(int,input().split())
     field = []
     for i in range(h):
          field.append(list(input()))
          
     que = []
     for i in range(h):
          for j in range(w):
               if field[i][j] == "#":
                    que.append([i,j])
     if que == []:
          print(0)
          return
     cnt = 0
     while que != []:
          que1 = []
          for p in que:
               for v in [[1,0],[0,1],[-1,0],[0,-1]]:
                    newx,newy = p[1]+v[1],p[0]+v[0]
                    if (0<=newx) and (newx<w) and (0<=newy) and (newy<h):
                         if field[newy][newx] == ".":
                              field[newy][newx] = "#"
                              que1.append([newy,newx])
          que = que1
          cnt += 1
     print(cnt-1)
     return
f()
### BUGGY CODE ###

import sys
#import time
import copy
#from collections import deque, Counter, defaultdict
#from fractions import gcd
#import bisect
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**20
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))
n = ri()
a = rl()
ans=1
for i in a:
    ans*=i
    
if ans>10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import sys
#import time
import copy
#from collections import deque, Counter, defaultdict
#from fractions import gcd
#import bisect
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**20
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))
n = ri()
a = rl()
ans=1
flag=False
for i in a:
    ans*=i
    if ans>10**18:
        flag=True
        break
   
zero=False
for i in a:
    if i==0:
        zero=True
        break
if zero:
    print(0)    
elif flag:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import numpy as np
n = int(input())
l = np.array(list(map(int, input().split())))
l = np.sort(l)
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        ans += l[j+1:][l[j+1:] < l[i] + l[j]].size
print(ans)

### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(n):
    for j in range(i+1, n):
        ans += bisect.bisect_left(l, l[i] + l[j]) - j - 1
print(ans)
### BUGGY CODE ###

s = input()
K = int(input())

S = set([])
for i in range(len(s)):
    for j in range(i + 1, len(s) + 1):
        # print(f'{s[i:j]=}')
        S.add(s[i:j])
# print(f'{S=}')
# print(f'{sorted(S)=}')
ans = sorted(S)[K - 1]
print(ans)


### FIXED CODE ###

s = input()
K = int(input())

S = set([])
for i in range(len(s)):
    for j in range(i + 1, i + 1 + K):
        # print(f'{s[i:j]=}')
        S.add(s[i:j])
# print(f'{S=}')
# print(f'{sorted(S)=}')
ans = sorted(S)[K - 1]
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
data = [[int(e) for e in input().split()] for _ in range(n)]
d1 = {}
for i in range(n):
  a, b = data[i]
  if a not in d1:
    d1[a] = []
  d1[a].append(b)
result = 0
d2 = {}
maxb = -1
for i in range(1, m + 1):
  if i in d1:
    for j in d1[i]:
      if j not in d2:
        d2[j] = 0
      d2[j] += 1
      if j > maxb:
        maxb = j
  else:
    if len(d2) == 0:
      continue
  result += maxb
  if d2[maxb] == 1:
    del d2[maxb]
    if len(d2) == 0:
      maxb = 0
    else:
      maxb = max(d2.keys())
  else:
    d2[maxb] -= 1
print(result)


### FIXED CODE ###

n, m = map(int, input().split())
d1 = {}
for _ in range(n):
  a, b = map(int, input().split())
  if a in d1:
    d1[a].append(b)
  else:
    d1[a] = [b]
result = 0
d2 = {}
maxb = -1
for i in range(1, m + 1):
  if i in d1:
    for j in d1[i]:
      if j not in d2:
        d2[j] = 0
      d2[j] += 1
      if j > maxb:
        maxb = j
  else:
    if len(d2) == 0:
      continue
  result += maxb
  if d2[maxb] == 1:
    del d2[maxb]
    if len(d2) == 0:
      maxb = 0
    else:
      maxb = max(d2.keys())
  else:
    d2[maxb] -= 1
print(result)
### BUGGY CODE ###

import math
import sys
import bisect

N = int(input())

A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

A = sorted(A)
B = sorted(B)
C = sorted(C)

BAcnt = [0] * N

for i in range(N):
    BAcnt[i] = bisect.bisect_left(A, B[i])

ret = 0
for i in range(N):
    csize = C[i]
    for j in range(N):
        bsize = B[j]
        if bsize < csize:
            ret += BAcnt[j]

print(ret)


### FIXED CODE ###

import math
import sys
import bisect

N = int(input())

A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

A = sorted(A)
B = sorted(B)
C = sorted(C)

BAcnt = [0] * N


for i in range(N):
    BAcnt[i] = bisect.bisect_left(A, B[i])

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

ret = 0
for i in range(N):
    j = bisect.bisect_left(B, C[i]) - 1
    if len(BAruiseki) > j and j>=0:
        ret += BAruiseki[j]


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

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

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

s=0
#maxについて
for i in range(k-1,n):
	s+=a[i]*cmb(i,k-1)
	s%=10**9+7
for i in range(n-k+1):
	s-=a[i]*cmb(n-i-1,k-1)
	s%=10**9+7
print(s)

### FIXED CODE ###

def cmb(n, k, mod, fac, ifac):
    """
    nCkを計算する
    """
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def make_tables(mod, n):
    """
    階乗テーブル、逆元の階乗テーブルを作成する
    """
    fac = [1, 1] # 階乗テーブル・・・(1)
    ifac = [1, 1] #逆元の階乗テーブル・・・(2)
    inverse = [0, 1] #逆元テーブル・・・(3)

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac
    
n,k=map(int,input().split())
a=sorted(list(map(int, input().split())))
MOD=10**9+7

fac, ifac=make_tables(MOD,n)

s=0
for i in range(k-1,n):
	s+=(a[i]-a[n-i-1])*cmb(i,k-1,MOD,fac,ifac)
	s%=10**9+7
print(s)
### BUGGY CODE ###

import sys
import collections

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def main():
    n, m = MI()
    G = [set() for _ in range(n+1)]
    for _ in range(m):
        a, b =MI()
        G[a].add(b)
        G[b].add(a)
    for i in range(n+1):
        G[i] = list(G[i])
    num = [-1]*(n+1)
    seen = [False]*(n+1)
    stack = []
    for i in range(1, n+1):
        if not seen[i]:
            stack.append(i)
            while stack:
                vertex = stack.pop(-1)
                seen[vertex] = True
                num[vertex] = i
            
                for j in range(len(G[vertex])):
                    neighbor = G[vertex][j]
                    if not seen[neighbor]:
                        stack.append(neighbor)
    c = collections.Counter(num)
    print(c.most_common()[0][1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import collections

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def main():
    n, m = MI()
    G = [set() for _ in range(n+1)]
    for _ in range(m):
        a, b =MI()
        G[a].add(b)
        G[b].add(a)
    for i in range(n+1):
        G[i] = list(G[i])
    num = [-1]*(n+1)
    seen = [False]*(n+1)
    stack = []
    for i in range(1, n+1):
        if not seen[i]:
            stack.append(i)
            while stack:
                vertex = stack.pop(-1)
                seen[vertex] = True
                num[vertex] = i
            
                for j in range(len(G[vertex])):
                    neighbor = G[vertex][j]
                    if not seen[neighbor]:
                        stack.append(neighbor)
    c = collections.Counter(num)
    print(c.most_common()[0][1])

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

from collections import deque
ans=deque()
ans.append(str(input()))
q=int(input())
l=[list(map(str,input().split())) for i in range(q)]
#print(l)
c=0
for i in range(q):
	if l[i][0]=='1':
		c+=1
	else:
		if c%2==0:
			if l[i][1]=='1':
				ans.appendleft(l[i][2])
			else:
				ans.append(l[i][2])
		else:
			if l[i][1]=='2':
				ans.appendleft(l[i][2])
			else:
				ans.append(l[i][2])
#print(list(ans))
A=''
for i in range(len(ans)):
	A+=ans[i]
if c%2==1:
	print(A[::-1])
else:
	print(A)





### FIXED CODE ###

from collections import deque
ans=deque()
ans.append(str(input()))
q=int(input())
l=[list(map(str,input().split())) for i in range(q)]
#print(l)
c=0
for i in range(q):
	if l[i][0]=='1':
		c+=1
	else:
		if c%2==0:
			if l[i][1]=='1':
				ans.appendleft(l[i][2])
			else:
				ans.append(l[i][2])
		else:
			if l[i][1]=='2':
				ans.appendleft(l[i][2])
			else:
				ans.append(l[i][2])
A="".join(map(str,list(ans)))
if c%2==1:
	print(A[::-1])
else:
	print(A)
### BUGGY CODE ###

import functools
import operator

N = int(input())
v = ((map(int, input().split())))
answer = functools.reduce(operator.mul,v)
answer = answer if answer <= 1000000000000000000 else -1
print(answer)

### FIXED CODE ###

N = int(input())
v = list(map(int, input().split()))
limit = 10 ** 18

answer = 1
if 0 in v:
  answer = 0
else:
  for i in v:
    answer = answer * i
    if answer <= limit:
      continue
    else:
      answer = -1
      break
print(answer)
### BUGGY CODE ###

N, X, Y = [int(n) for n in input().split(" ")]

X = X - 1
Y = Y - 1

D = {}
for i in range(N):
    D[i] = []

for i in range(N):
    if i != N - 1:
        D[i].append(i + 1)
        if i != 0:
            D[i].append(i - 1)
    else:
        D[i].append(i - 1)

D[X].append(Y)
D[Y].append(X)


def search(start):
    queue = [start]
    depth = 0
    dic = {start: 0}

    while len(queue) > 0:
        depth += 1
        nextQueue = []
        while len(queue) > 0:
            now = queue[0]
            del(queue[0])
            neighbors = D[now]
            for n in neighbors:
                if n not in dic:
                    nextQueue.append(n)
                    dic[n] = depth
        queue = nextQueue
    return dic
    
lenD = []
for i in range(N):
    d = search(i)
    lenD.append(d)

kcounter = [0 for _ in range(N - 1)]

for i in range(N):
    for j in range(i + 1, N):
        k = lenD[i][j]
        kcounter[k - 1] += 1

for k in kcounter:
    print(k)

### FIXED CODE ###


def search(start, N, X, Y):
    dist = [0 for _ in range(N)]
    if start <= X:
        for i in range(X):
            dist[i] = abs(start - i)
        for i in range(Y, N):
            dist[i] = (X - start) + 1 + (i - Y)
        for i in range(X, (Y - X) // 2 + X + 1):
            dist[i] = (i - start)
        for i in range((Y - X) // 2 + X + 1, Y):
            dist[i] = (X - start) + 1 + (Y - i)
    elif start >= Y:
        for i in range(Y, N):
            dist[i] = abs(start - i)
        for i in range(X):
            dist[i] = (start - Y) + 1 + (X - i)
        for i in range(X, (Y - X) // 2 + X):
            dist[i] = (start - Y) + 1 + (i - X)
        for i in range((Y - X) // 2 + X, Y):
            dist[i] = (start - i)
    else:
        toX = min(start - X, Y - start + 1)
        toY = min(Y - start, start - X + 1)
        dist[start] = 0
        for i in range(X):
            dist[i] = (X - i) + toX
        for i in range(Y, N):
            dist[i] = toY + (i - Y)
        for i in range(X, start):
            dist[i] = min(start - i, Y - start + 1 + i - X)
        for i in range(start + 1, Y):
            dist[i] = min(i - start, start - X + 1 + Y - i)
    return dist


def main():
    N, X, Y = [int(n) for n in input().split(" ")]
    #N, X, Y = 10, 3, 8

    X = X - 1
    Y = Y - 1

    lenD = []
    for i in range(N):
        d = search(i, N, X, Y)
        lenD.append(d)

    kcounter = [0 for _ in range(N - 1)]

    for i in range(N):
        for j in range(i + 1, N):
            k = lenD[i][j]
            kcounter[k - 1] += 1

    for k in kcounter:
        print(k)

main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

N,Q = map(int,input().split())
node = [[]for i in range(0,N+1,1)]
for i in range(0,N-1,1):
    a,b = map(int,input().split())
    node[a].append(b)
    node[b].append(a)
node_score = [0]*(N+1)#スコア
for i in range(0,Q,1):
    p,x = map(int,input().split())
    node_score[p] += x

ans = [0]*(N+1)
def bfs(n,preN):
    ans[n] = ans[preN]+node_score[n]
    for to in node[n]:
        if to != preN:
            bfs(to,n)
bfs(1,0)
print(" ".join(list(map(str,ans[1:N+1]))))
        



### FIXED CODE ###

from collections import deque 
#スタック
s = deque([])

N,Q = map(int,input().split())
node = [[]for i in range(0,N+1,1)]
for i in range(0,N-1,1):
    a,b = map(int,input().split())
    node[a].append(b)
    node[b].append(a)
node_score = [0]*(N+1)#スコア
for i in range(0,Q,1):
    p,x = map(int,input().split())
    node_score[p] += x

ans = [0]*(N+1)

s.append([1,0])
while len(s) > 0:
    n,preN = s.pop()
    ans[n] = ans[preN]+node_score[n]
    for to in node[n]:
        if to != preN:
            s.append([to,n])

print(" ".join(list(map(str,ans[1:N+1]))))
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
H,W,N=map(int,input().split())
d=[]
for i in range(N):
    a,b=map(int,input().split())
    for j in range(-1,2):
        if not 1<a+j<H:
            continue
        for k in range(-1,2):
            if not 1<b+k<W:
                continue
            t=(a+j,b+k)
            d.append(t)
d.sort()
l=[0]*10
t=0
c=0
for i in d:
    if i==t:
        c+=1
    else:
        l[c]+=1
        t=i
        c=1
l[c]+=1
l[0]=(H-2)*(W-2)-sum(l)+1
print(*l,sep="\n")

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
H,W,N=map(int,input().split())
d={}
for i in range(N):
    a,b=map(int,input().split())
    for j in range(-1,2):
        if not 1<a+j<H:
            continue
        for k in range(-1,2):
            if not 1<b+k<W:
                continue
            t=(a+j,b+k)
            if t in d:
                d[t]+=1
            else:
                d[t]=1
l=[0]*10
for i in d.values():
    l[i]+=1
l[0]=(H-2)*(W-2)-sum(l)
print(*l,sep="\n")
### BUGGY CODE ###

import sys,math,copy
import numpy as np
input = sys.stdin.readline
S = [int(x) if x != '?' else -1 for x in input().strip()]
N = len(S)

dp = np.zeros((13), dtype=int)
dp_ = np.zeros((13), dtype=int)
mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
divisor = 10 ** 9 + 7
dp_[0] = 1
mod = 1
for i, s in enumerate(S[::-1], start=1):
    if s == -1:
        for d in range(10):
            m = mod13_list[(d * mod)]
            for pm in range(13):
                dp[mod13_list[(pm+m)]] = (dp[mod13_list[(pm+m)]] + dp_[pm]) % (10 ** 9 + 7)

    else:
        m = mod13_list[(s * mod)]
        for pm in range(13):
            dp[mod13_list[(pm+m)]] = (dp[mod13_list[(pm+m)]] + dp_[pm]) % (10 ** 9 + 7)
    dp_ = dp % divisor
    dp = dp * 0 # np.zeros((13), dtype=int)
    mod = mod13_list[(mod * 10)]
print(dp_[5] % (10 ** 9 + 7))

### FIXED CODE ###

import sys,math,copy

def main():
    # import numpy as np
    input = sys.stdin.readline
    S = ''.join(reversed(input().strip()))

    # dp = np.zeros((13), dtype=int)
    # dp_ = np.zeros((13), dtype=int)
    dp = [0] * 13
    dp_ = [0] * 13
    mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
    list10 = list(range(10))
    list13 = list(range(13))
    divisor = 10 ** 9 + 7
    dp_[0] = 1
    mul = 1
    for i in range(len(S)):
        s = S[i]
        if s == '?':
            for d in list10:
                m = mod13_list[(d * mul)]
                for pm in list13:
                    dp[mod13_list[(pm+m)]] += dp_[pm]

        else:
            si = int(s)
            m = mod13_list[(si * mul)]
            for pm in list13:
                dp[mod13_list[(pm+m)]] = dp_[pm]

        # dp_ = dp % divisor
        # dp = dp * 0 # np.zeros((13), dtype=int)
        for j in list13:
            dp_[j] = dp[j] % divisor
            dp[j] = 0
        mul = mod13_list[(mul * 10)]
    print(dp_[5])

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

import sys

class segment_():
    def __init__(self, init_val, n, segfunc):
        self.ide_ele = 10**9+1
        # num: n以上の最小の2のべき乗
        self.num = 1 << (n - 1).bit_length()
        self.seg = [self.ide_ele]*2*self.num
        self.segfunc = segfunc
        # set_val
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]
        # built
        for i in range(self.num-2, -1, -1):
            self.seg[i] = self.segfunc(self.seg[2*i+1], self.seg[2*i+2])

    def update(self, k, x):
        k += self.num - 1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[2*k+1], self.seg[2*k+2])

    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num - 1
        q += self.num - 2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, x = map(int,sys.stdin.readline().split())
    A = list(map(int,sys.stdin.readline().split()))

    seg_ = segment_(A, n, lambda a, b: min(a, b))
    ans = 10**18
    for k in range(n):
        t = 0
        for i in range(n):
            if k <= i:
                t += seg_.query(i-k, i+1)
            else:
                t += min(seg_.query(0, i+1), seg_.query(n-(k-i), n))
        ans = min(t+k*x, ans)
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

n, x = map(int,sys.stdin.readline().split())
A = list(map(int,sys.stdin.readline().split()))

ans = 10**18
mins = [a for a in A]
for k in range(n):
    for i in range(n):
        if k <= i:
            mins[i] = min(A[i-k], mins[i])
        else:
            mins[i] = min(A[n-(k-i)], mins[i])
    ans = min(sum(mins)+k*x, ans)
print(ans)
### BUGGY CODE ###

def main():
  import sys
  i=0
  L=list(input())
  N=len(L)
  if N==1:
    print(0)
    sys.exit()
  for j in range(N):
    i=0
    S=len(L)
    if S==1 or S==0:
      break
    while True:
      if L[i]!=L[i+1]:
        L.pop(i)
        L.pop(i)
        if L==[]:
          print(N)
          sys.exit()
      i+=1
      if i>len(L)-2:
        break
    if S==len(L):
      break
  print(N-len(L))
main()

### FIXED CODE ###

S=input()
a=S.count("1")
b=S.count("0")
print(min(a,b)*2)
### BUGGY CODE ###

def readinput():
    n=int(input())
    x=input()
    return n,x

def popcount(x):
    return bin(x).count('1')

ftbl=[0]*(2*10**5+1)
def f(x):
    global ftbl

    if ftbl[x]!=0:
        return ftbl[x]
    
    #print('f(x), x: {}'.format(x))
    if x==0:
        return 0
    else:
        ans=f(x%popcount(x))+1
        #print(ans)
        ftbl[x]=ans
        return ans    

def main(n,x):
    m=x.count('1')
    #print('m: {}'.format(m))
    xint=int(x,2)
    #print('xint: {}'.format(xint))
    if m!=1:
        xmodm1=xint%(m-1)
    else:
        xmodm1=1
    xmodp1=xint%(m+1)
    ans=[]
    b=2**(n-1)
    for i in range(n):
        if x[i]=='1':
            if m==1:
                ans.append(0)
            else:
                xx=( xmodm1 + (m-1) -b%(m-1) )%(m-1)
                ans.append(f(xx)+1)
        else:
            xx=( xmodp1 + b%(m+1) )%(m+1)
            ans.append(f(xx)+1)
        b=b//2
    return ans

if __name__=='__main__':
    n,x=readinput()
    ans=main(n,x)
    for a in ans:
        print(a)



### FIXED CODE ###

def readinput():
    n=int(input())
    x=input()
    return n,x

poptbl=[0]*(2*10**5+1)
def popcount(x):
    global poptbl
    if poptbl[x]!=0:
        return poptbl[x]
    
    poptbl[x]=bin(x).count('1')
    return poptbl[x]

ftbl=[0]*(2*10**5+1)
def f(x):
    global ftbl

    if ftbl[x]!=0:
        return ftbl[x]
    
    #print('f(x), x: {}'.format(x))
    if x==0:
        return 0
    else:
        ans=f(x%popcount(x))+1
        #print(ans)
        ftbl[x]=ans
        return ans    

def main():
    n=int(input())
    x=input()
    m=x.count('1')
    #print('m: {}'.format(m))
    xint=int(x,2)
    #print('xint: {}'.format(xint))
    if m!=1:
        xmodm1=xint%(m-1)
    else:
        xmodm1=1
    xmodp1=xint%(m+1)
    pow2mod1=[0]*n
    pow2mod2=[0]*n
    pow2mod1[0]=1
    pow2mod2[0]=1
    for i in range(1,n):
        if m!=1:
            pow2mod1[i]=pow2mod1[i-1]*2 % (m-1)
        pow2mod2[i]=pow2mod2[i-1]*2 % (m+1)

    ans=[]
    #b=2**(n-1)
    for i in range(n):
        if x[i]=='1':
            if m==1:
                a=0
                ans.append(a)
            else:
                xx=( xmodm1 + (m-1) -pow2mod1[n-i-1] )%(m-1)
                #ans.append(f(xx)+1)
                a=f(xx)+1
                ans.append(a)
        else:
            xx=( xmodp1 + pow2mod2[n-i-1] )%(m+1)
            #ans.append(f(xx)+1)
            a=f(xx)+1
            ans.append(a)
        #b=b//2
        print(a)
    return ans

if __name__=='__main__':
    #n,x=readinput()
    ans=main()
    #for a in ans:
    #    print(a)