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

# coding: utf-8
N,D,A=map(int,input().split())
XH=[]
for i in range(N):
    XH.append(list(map(int,input().split())))

XH.sort()

bombs=[]
damage=0
ans=0

for i in range(N):
    if bombs:
        while bombs[0][1]<XH[i][0]:
            b=bombs.pop(0)
            damage-=b[0]
            if not(bombs):
                break
    
    hp=XH[i][1]-damage
    num_b=-(-hp//A)
    num_b=max(num_b,0)
    bom_d=A*num_b
    bom_l=XH[i][0]+2*D
    if num_b>0:
        bombs.append([bom_d,bom_l])
        damage+=bom_d
    ans+=num_b

print(ans)




### FIXED CODE ###

# coding: utf-8
N,D,A=map(int,input().split())
XH=[]
for i in range(N):
    XH.append(list(map(int,input().split())))

XH.sort()

bombs=[]
damage=0
ans=0

for i in range(N):
    if bombs:
        while bombs[0][1]<XH[i][0]:
            b=bombs.pop(0)
            damage-=b[0]
            if not(bombs):
                break
    
    hp=XH[i][1]-damage
    num_b=-(-hp//A)
    num_b=max(num_b,0)
    bom_d=A*num_b
    bom_l=XH[i][0]+2*D
    if num_b>0:
        bombs.append([bom_d,bom_l])
        damage+=bom_d
    ans+=num_b

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

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = 100#sys.maxsize
mod = 10 ** 9 + 7

n, m = MAP()
s = [int(i) for i in STR()]
flag = False
cnt = 0
for i in range(n + 1):
    if s[i] == 1:
        cnt += 1
    else:
        cnt = 0
    if cnt >= m:
        print(-1)
        exit()
dp = [inf for _ in range(n + 1)] #i手で到達できる場所
dp[0] = 0
arr = [[inf for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    arr.append(0)
    if s[i] == 0:
        for j in range(1, m + 1):
            if 0 <= i - j <= n and s[i - j] == 0 and dp[i] >= dp[i - j] + 1:
                dp[i] = dp[i - j] + 1
                arr[i][dp[i - j] + 1] = j
ans = [inf for _ in range(dp[n])]
idx = n
for i in reversed(range(1, dp[n] + 1)):
    ans[i - 1] = arr[idx][i]
    idx -= arr[idx][i]
for i in range(dp[n]):
    ans[i] = str(ans[i])
print(' '.join(ans))


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, m = MAP()
s = [int(i) for i in STR()]
flag = False
cnt = 0
for i in range(n + 1):
    if s[i] == 1:
        cnt += 1
    else:
        cnt = 0
    if cnt >= m:
        print(-1)
        exit()
ans = []
hr = n
while hr > 0:
    for i in reversed(range(1, m + 1)):
        if 0 <= hr - i <= n and s[hr - i] == 0:
            ans.append(i)
            hr -= i
            break
ans = list(reversed(ans))
for i in range(len(ans)):
    ans[i] = str(ans[i])
print(' '.join(ans))
### BUGGY CODE ###

n,p=map(int,input().split())
s=input()
ans=0
if p == 2:
    for i in range(n):
        if s[i] in ["0","2","4","6","8"]:
            ans+=i+1
elif p == 5:
    for i in range(n):
        if s[i] in ["0","5"]:
            ans+=i+1
else:
    mod=[0]*p
    for i in range(n+1):
        if s[i:]=="":
            si=0
        else:
            si =int(s[i:])
        ip = int(si)%p 
        mod[ip]+=1
    ans = sum(m*(m-1)//2 for m in mod)
print(ans)

### FIXED CODE ###

#e
n,p=map(int,input().split())
s=input()
ans=0
if p == 2:
    for i in range(n):
        if s[i] in ["0","2","4","6","8"]:
            ans+=i+1
elif p == 5:
    for i in range(n):
        if s[i] in ["0","5"]:
            ans+=i+1
else:
    mod=[1] + [0]*(p-1)
    a=0
    for i in range(n):
        si = int( s[n-1-i] )
        a = si*pow(10,i,p) + a 
        mod[ a%p ]+=1
    ans =  sum(m*(m-1)//2 for m in mod)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
n,q = map(int, input().split())
e = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    e[a-1].append(b-1)
    e[b-1].append(a-1)
ans = [0]*n
for i in range(q):
	p,x = map(int,input().split()) 
	ans[p-1] += x

def dfs(i = 0, r = -1):
    for j in e[i]:
        if j != r:
            ans[j] += ans[i]
            dfs(j, i)
dfs()
print(*ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
n,q = map(int, input().split())
e = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    e[a-1].append(b-1)
    e[b-1].append(a-1)

ans = [0]*n

for i in range(q):
    p,x = map(int,input().split()) 
    ans[p-1] += x

def dfs(i = 0, r = -1):
    for j in e[i]:
        if j != r:
            ans[j] += ans[i]
            dfs(j, i)

dfs()

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

import sys
input = sys.stdin.readline

n = int(input())
b = list(map(int, input().split()))

from queue import Queue
q = Queue()
ans = Queue()

def bfs(b):
    q.put(b)

    while q.empty() == False:
        p = q.get()

        if p == []:
            break

        if ans.empty() == False:
            a = ans.get()
        else:
            a = []

        m = len(p)

        for i in range(m):
            if p[i] == (i+1):
                pp = p[:]
                pp.remove(i+1)
                q.put(pp)

                aa = a[:]
                aa.append(i+1)
                ans.put(aa)

    if p == []:
        a = ans.get()
        a = a[::-1]

        for aa in a:
            print(aa)
    else:
        print(-1)


bfs(b)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
b = list(map(int, input().split()))

from queue import Queue
q = Queue()
ans = Queue()

import numpy as np
n = np.array(n)


def bfs(b):
    q.put(b)
    ans.put([])

    while q.empty() == False:
        p = q.get()
        a = ans.get()

        if p == []:
            break

        if p[0] != 1:
            continue

        m = len(p)

        for i in range(m-1, -1, -1):
            if p[i] == i+1:
                q.put(p[:i]+p[i+1:])
                ans.put(a+[i+1])
                break


    if p == []:
        a = a[::-1]
        for aa in a:
            print(aa)
    else:
        print(-1)


bfs(b)
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

N,mod=map(int,input().split())
EDGE=[list(map(int,input().split())) for i in range(N-1)]

#N=10**5
#mod=10**8
#import random
#EDGE=[[i,random.randint(1,i-1)] for i in range(2,N+1)]

EDGELIST=[[] for i in range(N+1)]

for x,y in EDGE:
    EDGELIST[x].append(y)
    EDGELIST[y].append(x)

QUE=deque()
DPDICT=dict()

for i in range(1,N+1):
    if len(EDGELIST[i])==1:
        #DPDICT[(i,EDGELIST[i][0])]=2
        QUE.append(i)


def SCORE(point):
    ANS=1
    for to in EDGELIST[point]:
        ANS=ANS*DPDICT[(to,point)]%mod
    return ANS

def dp(x,y):
    if DPDICT.get((x,y))!=None:
        return DPDICT[(x,y)]

    ANS=1
    for to in EDGELIST[x]:
        if to==y:
            continue
        ANS=ANS*dp(to,x)%mod

    DPDICT[(x,y)]=ANS+1
    return ANS+1

while QUE:
    x=QUE.pop()
    for to in EDGELIST[x]:
        if DPDICT.get((x,to))==None:
            dp(x,to)
            QUE.append(to)


for i in range(1,N+1):
    print(SCORE(i))

### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

N,mod=map(int,input().split())
EDGE=[list(map(int,input().split())) for i in range(N-1)]

if N==1:
    print(1)
    sys.exit()

EDGELIST=[[] for i in range(N+1)]
for x,y in EDGE:
    EDGELIST[x].append(y)
    EDGELIST[y].append(x)

SCORELIST=[[-1]*len(EDGELIST[i]) for i in range(N+1)]
PRODLIST=[[-1]*len(EDGELIST[i]) for i in range(N+1)]
PRODLIST_rev=[[-1]*len(EDGELIST[i]) for i in range(N+1)]
EDICT=dict()

for i in range(1,N+1):
    for j in range(len(EDGELIST[i])):
        EDICT[(i,EDGELIST[i][j])]=j

def dp(x,y):
    if SCORELIST[y][EDICT[(y,x)]]!=-1:
        return SCORELIST[y][EDICT[(y,x)]]

    ANS=1
    for to in EDGELIST[x]:
        if to==y:
            continue
        ANS=ANS*dp(to,x)%mod

    SCORELIST[y][EDICT[(y,x)]]=ANS+1   
    return ANS+1

def dp2(x,y):
    if PRODLIST[x][0]==-1:
        PRODLIST[x][0]=(SCORELIST[x][0])%mod
        for i in range(1,len(EDGELIST[x])):
            PRODLIST[x][i]=PRODLIST[x][i-1]*SCORELIST[x][i]%mod

        PRODLIST_rev[x][-1]=SCORELIST[x][-1]
        for i in range(len(EDGELIST[x])-2,-1,-1):
            PRODLIST_rev[x][i]=PRODLIST_rev[x][i+1]*SCORELIST[x][i]%mod

    if len(EDGELIST[x])==1:
        ANS=1
    elif EDICT[(x,y)]==0:
        ANS=PRODLIST_rev[x][1]
    elif EDICT[(x,y)]==len(EDGELIST[x])-1:
        ANS=PRODLIST[x][EDICT[(x,y)]-1]
    else:
        ANS=PRODLIST[x][EDICT[(x,y)]-1]*PRODLIST_rev[x][EDICT[(x,y)]+1]%mod

    SCORELIST[y][EDICT[(y,x)]]=ANS+1

for to in EDGELIST[1]:
    dp(to,1)

QUE=deque([1])
check=[0]*(N+1)

while QUE:
    x=QUE.pop()
    if check[x]==1:
        continue
    for to in EDGELIST[x]:
        if check[x]==0 or check[to]==0:
            dp2(x,to)
            QUE.append(to)
    check[x]=1

for i in range(1,N+1):
    print(PRODLIST[i][-1])
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
for i in range(Q):
  res=0
  l,r=map(int,input().split())
  for j in range(r-l):
    if S[l+j-1]=="A" and S[l+j]=="C":
      res+=1
  print(res)

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
A=[0]
res=0
for i in range(N):
  if i !=0:
    if S[i-1]=="A" and S[i]=="C":
      res+=1
      A.append(res)
    else:
      A.append(res)
for i in range(Q):
  l,r=map(int,input().split())
  print(A[r-1]-A[l-1])
### BUGGY CODE ###

n=int(input())

lis=[]

for i in range(n):
  lis.append(sorted(list(input())))
co=0
for i in range(n):
  for j in range(i+1,n):
    if lis[i]==lis[j]:
      co+=1
print(co)

### FIXED CODE ###

n=int(input())
ans=0
lis=[]
def cnt(n):
  ret=0
  for i in range(1,n):
    ret+=i
  return ret
for i in range(n):
  lis.append(sorted(list(input())))
co=1
lis.sort()
bef=lis[0]

for i in lis[1:]:
  if bef!=i:
    ans+=cnt(co)
    co=1
    bef=i
  else:
    co+=1
ans+=cnt(co)
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
m_num = max(a)

for i in range(n):
  if a[i] >= m_num:
    b = a[i]
    del a[i]
    print(max(a))
    a.insert(i, b)
  else:
    print(m_num)

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
m_num = max(a)
m_index = [i for i, x in enumerate(a) if x == m_num]

if len(m_index) > 1:
  for i in range(n):
    print(m_num)
else:
  if len(a) == 1:
    print(a[0])
  else:
    m2_num = sorted(a)[-2]
    for i in range(n):
      if (i in m_index):
        print(m2_num)
      else:
        print(m_num)
### BUGGY CODE ###

from numba import jit

@jit(cache = True)
def solve(i,j,a):
    k=False
    sc=0
    for c in a:
        if c>j:
            break
        elif c>j//2 and c<j:
            continue
        elif c==j:
            sc+=1
            if sc>=2:
                k=True
                break
        else:
            if j%c==0:
                k=True
                break
    return k

n=int(input())
a=sorted(list(map(int,input().split())))
ans=0
for i,j in enumerate(a):
    if solve(i,j,a):
        continue
    else:
        ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
m=max(a)
cnt=[0 for _ in range(m+1)]
ans=0
for i in a:
    if cnt[i]>=1:
        cnt[i]+=1
        continue
    for j in range(2*i,m+1,i):
        cnt[j]+=1
    cnt[i]=1
for i in range(n):
    if cnt[a[i]]==1:
        ans+=1
print(ans)
### BUGGY CODE ###


N , M = [int(n) for n in input().split(' ')]

list_AC =[]
list_WAcount = [0] * N
sumWA = 0

for i in range(M):
    sp , S = input().split(' ')
    p = int(sp)
    
    if (p in list_AC):
        # 既にAC済みの場合は何もしない
        continue 
    else:
        # 最初に正解したときにそれまでのWA回数を加算
        if S == 'AC':
            list_AC.append(p)
            sumWA += list_WAcount[p-1]
        else:
            list_WAcount[p-1] += 1

print("{} {}".format(len(list_AC),sumWA))

### FIXED CODE ###


N , M = [int(n) for n in input().split(' ')]

list_AC = [0] * N
list_WAcount = [0] * N
sumAC = 0
sumWA = 0

for i in range(M):
    sp , S = input().split(' ')
    p = int(sp)
    
    if (list_AC[p-1] != 0):
        # 既にAC済みの場合は何もしない
        continue 
    else:
        # 最初に正解したときにそれまでのWA回数を加算
        if S == 'AC':
            sumAC += 1
            list_AC[p-1] = 1
            sumWA += list_WAcount[p-1]
        else:
            list_WAcount[p-1] += 1

print("{} {}".format(sumAC,sumWA))
### BUGGY CODE ###

N,K = map(int,input().split())
A = sorted(list(map(int,input().split())))

INF = 10**18+1
l = -INF
r = INF
while(l+1 < r):
  # 積がc未満となるペアの個数xを求める。
  # K番目の積は、それより小さい積の個数がK未満である席のうち最大のもの。
  c = (l+r)//2
  x = 0
  for a in A:
    if a >= 0:
      ll = -1
      rr = N
      while(ll+1 < rr):
        cc = (ll+rr)//2
        if a*A[cc] < c:
          ll = cc
        else:
          rr = cc
      x += ll+1
    else:
      ll = -1
      rr = N
      while (ll+1 < rr):
        cc = (ll+rr)//2
        if a*A[cc] < c:
          rr = cc
        else:
          ll = cc
      x += N-rr
    if a*a < c:
      x -=1
  x //= 2
  if x < K:
    l = c
  else:
    r = c
print(l)


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
  N,K = map(int,input().split())
  A = sorted(list(map(int,input().split())))
  
  AM = []
  AP = []
  for a in A:
    if a > 0:
      AP.append(a)
    elif a < 0:
      AM.append(a)

  INF = 10**18+1
  l = -INF
  r = INF
  while(l+1 < r):
    # 積がc未満となるペアの個数xを求める。
    # K番目の積は、それより小さい積の個数がK未満である席のうち最大のもの。
    c = (l+r)//2
    x = 0
    if c > 0:
      i = len(AP)-1
      for j in range(len(AP)):
        if j >= i:
          break
        while(j < i and AP[i]*AP[j] >= c):
          i -= 1
        x += i-j
      i = 0
      for j in range(len(AM)-1,-1,-1):
        if j <= i:
          break
        while (i < j and AM[i]*AM[j] >= c):
          i += 1
        x += j-i
      #print(c,x)
      x += len(AP)*len(AM)
      x += (len(AP)+len(AM))*(N-len(AP)-len(AM))
      if N-len(AP)-len(AM) > 1:
        x += (N-len(AP)-len(AM))*(N-len(AP)-len(AM)-1)//2
    elif c == 0:
      x += len(AP)*len(AM)
    else:
      i = 0
      for j in range(len(AM)):
        while(i < len(AP) and AP[i]*AM[j] >= c):
          i += 1
        x += len(AP)-i

    #print(l,r,c,x)
    if x < K:
      l = c
    else:
      r = c
  print(l)

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

def run(N, a):
    ans = -1
    cnt = 0
    idx = 0
    match = False
    for i in range(1, N+1):
        if idx > N - 1:
            break
        for ai in a[idx:]:
            idx += 1
            if ai == i:
                # print('match', i, ai, idx)
                match = True
                break
            else:
                # print('break', i, ai, idx)
                cnt += 1
    if match:
        ans = cnt
    return ans


def main():
    N = int(input())
    a = list(map(int, input().split()))
    print(run(N, a))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def run(N, a):
    ans = -1
    cnt = 0
    idx = 0
    i = 1
    match = False
    while idx < N:
        ai = a[idx]
        idx += 1
        if ai == i:
            # print('match', i, ai, idx)
            match = True
            i += 1
        else:
            # print('break', i, ai, idx)
            cnt += 1
    if match:
        ans = cnt
    return ans


def main():
    N = int(input())
    a = list(map(int, input().split()))
    print(run(N, a))


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

from math import sqrt

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

def main(n):
    f=[0]*n
    for i in range(1,n+1):
        sqrt2n=int(sqrt(2*i))+1
        #print(i,sqrt2n)
        for x in range(1,sqrt2n):
            for y in range(1,sqrt2n-x+1):
                if (x+y)**2>2*i:
                    break
                for z in range(1,sqrt2n-x+1):
                    v=(x+y)**2+(y+z)**2+(z+x)**2
                    if v>2*i:
                        break
                    #print(v)
                    if v==2*i:
                        f[i-1]+=1
                        #print('found')
                        #print(x,y,z,i)
    return f

if __name__=='__main__':
    n=readinput()
    ans=main(n)
    for f in ans:
        print(f)


### FIXED CODE ###

from math import sqrt

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

def main(n):
    f=[0]*n
    for i in range(1,n+1):
        sqrt2n=int(sqrt(2*i))+1
        #print(i,sqrt2n)
        for x in range(1,sqrt2n):
            for y in range(1,sqrt2n-x+1):
                if (x+y)**2>2*i:
                    break
                for z in range(1,sqrt2n-x+1):
                    v=(x+y)**2+(y+z)**2+(z+x)**2
                    if v>2*i:
                        break
                    #print(v)
                    if v==2*i:
                        f[i-1]+=1
                        #print('found')
                        #print(x,y,z,i)
    return f

def F(x,y,z):
    return ((x+y)**2+(y+z)**2+(z+x)**2)//2

def main2(n):
    sqrt2n=int(sqrt(2*n))+1
    cntbl=[0]*(10**4+1)
    for x in range(1,sqrt2n):
        for y in range(1,sqrt2n):
            for z in range(1,sqrt2n):
                v=F(x,y,z)
                if v>n:
                    break
                cntbl[v]+=1
    return cntbl


if __name__=='__main__':
    n=readinput()
    ans=main2(n)
    for i in range(1,n+1):
        print(ans[i])
### BUGGY CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]


h,w=map(int,input().split())
a=[list(map(int,input().split())) for i in range(h)]
b=[list(map(int,input().split())) for i in range(h)]

lst=[[0]*w for i in range(h)]

lst[0][0]={abs(a[0][0]-b[0][0]):1}
# print(lst)
for i in range(h):
    for j in range(w):
            tmp=lst[i][j].keys()
            if i+1<h:
                if lst[i+1][j]==0:
                    lst[i+1][j]={}
                ab=abs(a[i+1][j]-b[i+1][j])
                for k in tmp:
                    lst[i+1][j][k+ab]=1
                    lst[i+1][j][abs(k-ab)]=1

            # print(lst)
            if j+1<w:
                if lst[i][j+1]==0:
                    lst[i][j+1]={}
                ab=abs(a[i][j+1]-b[i][j+1])
                for k in tmp:
                    lst[i][j+1][k+ab]=1
                    lst[i][j+1][abs(k-ab)]=1
    # print(d)
    # print(lst)
anslst=list(lst[-1][-1].keys())
anslst.sort(key=lambda x: abs(x))
print(abs(anslst[0]))

### FIXED CODE ###

import sys

input = sys.stdin.buffer.readline

h, w = map(int, input().split())
AA = [list(map(int, input().split())) for _ in range(h)]
BB = [list(map(int, input().split())) for _ in range(h)]

kouho = [[0] * (w) for _ in range(h)]
delta = abs(AA[0][0] - BB[0][0])
kouho[0][0] |= 1 << delta
for y in range(h):
    for x in range(w):
        nx = x + 1
        ny = y
        if nx < w:
            delta = abs(AA[ny][nx] - BB[ny][nx])
            temp = 0
            for i in range(1, delta + 1):
                if (kouho[y][x] >> i) % 2:
                    temp |= 1 << (delta - i)
            # print(x,y,kouho[y][x],temp,delta)
            kouho[ny][nx] |= kouho[y][x] << delta
            kouho[ny][nx] |= kouho[y][x] >> delta
            kouho[ny][nx] |= temp

        nx = x
        ny = y + 1
        if ny < h:
            delta = abs(AA[ny][nx] - BB[ny][nx])
            temp = 0
            for i in range(1, delta + 1):
                if (kouho[y][x] >> i) % 2:
                    temp |= 1 << (delta - i)
            # print(x,y,kouho[y][x],temp,delta)
            kouho[ny][nx] |= kouho[y][x] << delta
            kouho[ny][nx] |= kouho[y][x] >> delta
            kouho[ny][nx] |= temp
# print(kouho)
for i in range(81):
    if (kouho[h - 1][w - 1] >> i) % 2:
        print(i)
        exit()
### BUGGY CODE ###

#AIsing2020 d
 
N = int(input())
X = input()
X10 = int(X,2)
X10_num1 = X.count('1')
X10_pulse = X10%(X10_num1+1)
X10_ninus = X10%(X10_num1-1) if X10_num1 >1 else 0


for i in range(N,0,-1):
    a = X10
    if (a>>(i-1) & 1) and X10_num1 >1:
        a -= 2**(i-1)
        amari = (X10_ninus - (2**(i-1))%(X10_num1-1))%(X10_num1-1)

    elif (a>>(i-1) & 1) and X10_num1 ==1:
        print(0)
        continue
    else:
        a += 2**(i-1)
        amari = (X10_pulse + (2**(i-1))%(X10_num1+1))%(X10_num1+1)
    nc = amari 
    if a ==0:
        co = 0
    else:
        co = 1
        while nc >0:
            bin_str = bin(nc)
            cou1 = bin_str.count('1')
            nc = nc%cou1
            co +=1
    
    print(co)


### FIXED CODE ###

#AIsing2020 d

def f(n):
        cnt = 0
        while n:
            cnt+= 1
            n = n%bin(n).count('1')
        return cnt

def main():
    N = int(input())
    X = input()
    X10 = int(X,2)
    X10_num1 = X.count('1')
    X10_pulse = X10%(X10_num1+1)
    X10_ninus = X10%(X10_num1-1) if X10_num1 >1 else 0


    for i in range(N,0,-1):
        j = N-i
        if (X[j] == '1') and X10_num1 >1:
            mod = X10_num1-1
            amari = (X10_ninus - pow(2,i-1,mod))%(mod) 
        elif (X[j] == '1') and X10_num1 ==1:
            print(0)
            continue
        else:
            mod = X10_num1+1
            amari = (X10_pulse + pow(2,i-1,mod))%(mod)

        print(1+f(amari))


main()
### BUGGY CODE ###

N = int(input()) # 奇数
inputs = [int(i) for i in input().split()]

double_inputs = list(map(lambda x: x * 2, inputs))
ans = [0 for _ in range(N)]
for i in range(N):
    total = sum(inputs)
    if i == 0:
        for j in range((N - 1) // 2):
            total -= double_inputs[(i+1+2*j)%N]
            ans[i] = total
    elif i == N - 1:
        ans[i] = double_inputs[-1] - ans[0]
    else:
        ans[i] = double_inputs[i-1] - ans[i-1]

print(' ' .join(map(str, ans)))


### FIXED CODE ###

N = int(input()) # 奇数
inputs = [int(i) for i in input().split()]

double_inputs = list(map(lambda x: x * 2, inputs))
ans = [0 for _ in range(N)]
for i in range(N):
    if i == 0:
        ans[i] = sum(inputs) - sum(double_inputs[1::2])
    elif i == N - 1:
        ans[i] = double_inputs[-1] - ans[0]
    else:
        ans[i] = double_inputs[i-1] - ans[i-1]

print(' ' .join(map(str, ans)))
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
a.extend(a)
for i in range(n):
    ans = 0
    k = 0
    for j in range(i,n+i):
        ans += a[j]*(-1)**k
        k += 1
    print(ans,end=" ")

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
a.extend(a)
ans = 0
k = 0
for i in range(n):
    ans += a[i]*(-1)**k
    k += 1
print(ans,end=" ")
for i in range(n-1):
    ans = 2*a[i]-ans 
    print(ans,end=" ")