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

from collections import deque

N = int(input())

T = [[] for i in range(N)]
for i in range(N-1) :
    u,v,c = map(int,input().split())
    u -= 1
    v -= 1
    T[u].append([v,c])
    T[v].append([u,c])

Q,K = map(int,input().split())
K -= 1

L = []

for i in range(Q) :
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    L.append([u,v])

dist = [0]*N

q = deque([[K,0]])

explored = [0]*N

C = []
while q :
    now,c = q.pop()
    
    if not explored[now] :
        C.append(c)
        dist[now] = sum(C)
        explored[now] = 1
    
    flg = 1
    
    while T[now] :
        to, c = T[now].pop(0)
        if explored[to] :
            continue
        
        q.append([now, 0])
        q.append([to, c])
        flg = 0
        break
    if flg :
        if len(T[now]) == 0 :
            C.pop(-1)
    
    #print("now:", now, "C:", C)
        
ans = []

for i in range(Q) :
    u,v = L[i]
    calc = dist[u] + dist[v]
    ans.append(calc)

print(*ans, sep="\n")


### FIXED CODE ###

from collections import deque

N = int(input())

L = [[] for i in range(N)]

for i in range(N-1) :
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    L[a].append([b,c])
    L[b].append([a,c])
    

Q,K = map(int,input().split())

K -= 1

DISTANCE = [float("inf") for i in range(N)]

DISTANCE[K] = 0

q = deque([K])

while q :
    from_ = q.popleft()
    for to_, weight in L[from_] :
        dist = DISTANCE[from_] + weight
        if dist < DISTANCE[to_] :
            DISTANCE[to_] = dist
            q.append(to_)
            
ans = []

for i in range(Q) :
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    
    calc = DISTANCE[x] + DISTANCE[y]
    ans.append(calc)

print(*ans, sep="\n")
### BUGGY CODE ###

from collections import Counter
n = int(input())
a = [int(item) for item in input().split()]
cnt = Counter(a)

key_num = len(cnt.keys())
rank = [0] * key_num 
keys = list(cnt.keys())
keys.sort(reverse=True)
for i, key in enumerate(keys):
    rank[i] = cnt[key]
cur = [0] * key_num 
cur[0] = 1
for i in range(n):
    tmp = cur[:]
    for j in range(key_num-1):
        par = tmp[j]
        for k in range(j+1, key_num):
            if rank[k] < cur[k] + par and par > 0:
                cur[k] = rank[k]
                par -= rank[k] - cur[k]
            else:
                cur[k] += par
                par = 0
                break
if sum(cur) == 2**n:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

from collections import Counter
n = int(input())
a = [int(item) for item in input().split()]
cnt = Counter(a)

key_num = len(cnt.keys())
rank = [0] * key_num 
keys = list(cnt.keys())
keys.sort(reverse=True)
for i, key in enumerate(keys):
    rank[i] = cnt[key]
cur = [0] * key_num 
cur[0] = 1
for i in range(n):
    tmp = cur[:]
    free = 0
    for j in range(key_num):
        if rank[j] > cur[j] and free > 0:
            if cur[j] + free > rank[j]:
                free -= rank[j] - cur[j]
                cur[j] = rank[j]
            else:
                cur[j] += free
                free = 0
        free += tmp[j] 
if sum(cur) == 2**n:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import sys

input = sys.stdin.readline

def main():
    n = int(input())
    sl = list(input())
    sl.pop()

    q = int(input())
    kl = tuple(map(int,input().split()))

    for k in kl:
        # i文字目までのdとmとdmの数

        d = m = dm = ans = 0
        for i in range(n):
            if i - k >= 0:
                if sl[i-k] == "D":
                    d -= 1
                    dm -= m
                if sl[i-k] == "M":
                    m -= 1
            if sl[i] == "D":
                d += 1
            if sl[i] == "M":
                m += 1
                dm += d
            if sl[i] == "C":
                ans += dm

        print(ans)

if __name__ == "__main__":
    main()







### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    S = input()
    Q = int(input())
    x = tuple(map(int,input().split()))
    for k in x:
        d,m,dm,dmc = 0,0,0,0
        for i in range(N):
            if S[i] == "D":
                d += 1
            elif S[i] == "M":
                m += 1
                dm += d
            elif S[i] == "C":
                dmc += dm
            if i >= k-1:
                if S[i-k+1] == "D":
                    dm -= m
                    d -= 1
                elif S[i-k+1] == "M":
                    m -= 1
        print(dmc)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
sorted(a)
for i in range(n):
  if a[i]==sorted(a)[-1]:print(sorted(a)[-2])
  else:print(sorted(a)[-1])

### FIXED CODE ###

import heapq
n=int(input())
a=[int(input()) for i in range(n)]
b=list(map(lambda x:x*(-1), a))
heapq.heapify(b)
max1=heapq.heappop(b)*(-1)
max2=heapq.heappop(b)*(-1)

for i in range(n):
  if a[i]==max1:print(max2)
  else:print(max1)
### BUGGY CODE ###

from collections import deque

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

F=[[] for i in range(N)]
B=[[] for i in range(N)] 

for i in range(M):
    a,b=map(int,input().split())
    F[a-1].append(b-1)
    F[b-1].append(a-1)

for i in range(K):
    a,b=map(int,input().split())
    B[a-1].append(b-1)
    B[b-1].append(a-1)

q=deque([])
cnt=[0]*N

for i in range(N):
    visited=[0]*N
    visited[i]=1
    for j in F[i]:
        if visited[j]==0:
            visited[j]=1
            q.append(j)
    while q:
        c=q.popleft()
        if c in F[i]: 
            for j in F[c]:
                if visited[j]==0:
                    visited[j]=1
                    q.append(j)
            continue
        if c not in B[i]: 
            cnt[i]+=1
        for j in F[c]:
            if visited[j] == 0:
                visited[j]=1
                q.append(j)



for i in cnt:
    print(str(i),end=" ")


### FIXED CODE ###

from collections import deque

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

F=[[] for _ in range(N)]
B=[[] for _ in range(N)]


for i in range(M):
    a,b=map(int,input().split())
    F[a-1].append(b-1)
    F[b-1].append(a-1)

for i in range(K):
    a,b=map(int,input().split())
    B[a-1].append(b-1)
    B[b-1].append(a-1)

q=deque([])
G=[]
visited=[0]*N
group=[-1]*N
idx=0
for i in range(N):
    if visited[i]==1:continue
    visited[i]=1
    group[i]=idx
    q.append([i,[i]])
    while q:
        n,c=q.pop()
        for j in F[n]:
            if visited[j]==0:
                c.append(j)
                visited[j]=1
                group[j]=idx
                q.append([j,c])
    G.append(c)
    idx+=1

cnt=[0]*N
for g in G:
    for i in g:
        for b in B[i]:
            if  group[i]==group[b]:
                cnt[i]+=1

ans=[0]*N

for g in G:
    for i in g:
        ans[i]=len(g)-len(F[i])-cnt[i]-1

for i in ans:
    print(str(i),end=" ")
### BUGGY CODE ###

from numpy import *

N = int(input())

A = zeros(N, dtype=int)
B = zeros(N, dtype=int)

al = []
bl = []

count = 0
for i in range(N):
    A[i] = i + 1
    al.append( str(A[i]) )

    a_s = (al[i])[0]
    a_e = (al[i])[len(al[i]) - 1]

    for j in range(N):
        B[j] = j + 1
        bl.append( str(B[j]) )

        b_s = (bl[j])[0]
        b_e = (bl[j])[len(bl[j]) - 1]

        if a_e == b_s and a_s == b_e:
            count += 1

print(count)

### FIXED CODE ###

from numpy import *

N = int(input())

l = zeros((10, 10), dtype=int)

for i in range(N):
    a = int( str(i + 1)[0] )
    b = int( str(i + 1)[-1] )
    l[a][b] += 1

count = 0
for i in range(1, 10):
    for j in range(1, 10):
        count += l[i][j] * l[j][i]


print(count)
### BUGGY CODE ###

import itertools
import functools
import math
from collections import Counter
from itertools import combinations
import re

def main_chk():
    N=int(input())
    C=input()

    chk = N - 1
    cnt = 0

    for i in range(N):
        if C[i] == 'W':
            for x in range(N):
                if C[chk-x] == 'R':
                    chk = chk - x
                    break
            if chk <= i:
                break
            else:
                cnt = cnt + 1
                chk = chk - 1

    print(cnt)

main_chk()

### FIXED CODE ###

import itertools
import functools
import math
from collections import Counter
from itertools import combinations
import re

def main_chk():
    N=int(input())
    C=input()

    chk = N - 1
    cnt = 0

    for i in range(N):
        if C[i] == 'W':
            p = chk
            chk = i
            for x in range(N-i):
                if C[p-x] == 'R':
                    chk = p - x
                    break
            if chk <= i:
                break
            else:
                cnt = cnt + 1
                chk = chk - 1
                if chk <= i + 1:
                    break

    print(cnt)

main_chk()
### BUGGY CODE ###

from functools import reduce

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

ans = reduce(lambda x, y: x * y, A)
if ans > 10**18:
    ans = -1
print(ans)

### FIXED CODE ###

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

x = 10**18
ans = 1
for a in A:
    if ans != -1:
        ans *= a
    if ans > x:
        ans = -1
    if a == 0:
        ans = 0
        break
print(ans)
### BUGGY CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

N=int(input())
Flist=factorization(N)
F_list=[]
for i in Flist:
    F_list+=[i[0]]*i[1]
F_list.sort()
data=[[1,1] for i in range(2**len(F_list))]
for i in range(2**len(F_list)):
    for m,s in enumerate("0"*(len(F_list)-len(bin(i)[2:]))+bin(i)[2:]):
        if int(s):data[i][0]*=F_list[m]
        else     :data[i][1]*=F_list[m]
data2=data[[i[0]-i[1] for i in data].index(min([abs(i[0]-i[1]) for i in data]))]
print(data2[0]+data2[1]-2)


### FIXED CODE ###

N=int(input())
print(min([sum([i-1,round(N/i)-1]) for i in range(1,int(N**0.5)+1) if N%i==0]))
### BUGGY CODE ###

ni,ki = [int(i) for i in input().split()]
arri = [int(i) for i in input().split()]

dif = lambda x,y: abs(x-y)

def getRes(arr,n,k):
    dp = [0]*n
    for i in range(1,n):
        H = arr[i]
        dp[i] = min([dp[j]+dif(arr[j],H) for j in range(max(0,i-k),i)])
    return dp[-1]

print(getRes(arri,ni,ki))


### FIXED CODE ###

ni,ki = [int(i) for i in input().split()]
arri = [int(i) for i in input().split()]
    
def getRes(arr,n,k):
    dp = [0]*n
    for i in range(1,n):
        H = arr[i]
        dp[i] = min([dp[j]+abs(arr[j]-H) for j in range(max(0,i-k),i)])
    return dp[-1]

print(getRes(arri,ni,ki))
### BUGGY CODE ###

K,S = map(int, input().split())
cnt=0

for x in range(K+1):
    for y in range(K+1):
         for z in range(K+1):
            if S== x+y+z:
                cnt +=1
            else:
                continue

print(cnt)

### FIXED CODE ###

K,S = map(int, input().split())
cnt=0

for x in range(K+1):
    for y in range(K+1):
            if K>=S-(x+y)>=0:
                cnt +=1
            else:
                continue

print(cnt)
### BUGGY CODE ###

N,A,B = map(int,input().split())
h = [0]*N
for i in range(N):
    h[i] = int(input())

# x回で全モンスター倒せるかどうかをにぶちゃん(にぱー)

left = -1
right = 10**9+7

def check(x):
    for i in range(N):
        res = h[i] - B*x
        if res >= (A-B)*x:
            return False
    return True

while abs(right-left) > 1:
    center = (right+left)//2
    
    if check(center) == True:
        right = center
    elif check(center) == False:
        left == center
        
print(center)

### FIXED CODE ###

N,A,B = map(int,input().split())
h = [0]*N
for i in range(N):
    h[i] = int(input())

# x回で全モンスター倒せるかどうかをにぶちゃん(にぱー)

import math

def check(x):
    count = 0
    for i in range(N):
        count += math.ceil(max(h[i] - B * x, 0) / (A - B))
           
    if count <= x:
        return True
    else:
        return False
    
def solve():
    
    left = -1
    right = 10**9+1
    
    while abs(right-left) > 1:
    
        center = (right+left)//2
    
        if check(center) == True:
            right = center
        elif check(center) == False:
            left = center
        
    return right
    
print(solve())
### BUGGY CODE ###

(n, m) = map(int, input().split())
counts = [0 for _ in range(n)]
for _ in range(m):
    gate_i = list(map(int, input().split()))
    for i in range(gate_i[0] - 1, gate_i[1]):
        counts[i] += 1
counts.sort()
ans = 0
for count in counts:
    ans += 1 if m == count else 0
print(ans)


### FIXED CODE ###

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


def intersect(lhs, rhs):
    if lhs[1] < rhs[0] or rhs[1] < lhs[0]:
        return [0, 0]
    min_value = lhs[0] if lhs[0] > rhs[0] else rhs[0]
    max_value = lhs[1] if lhs[1] < rhs[1] else rhs[1]
    return [min_value, max_value]


ans = [-1, 2 * 10 ** 5]
for _ in range(m):
    ans = intersect(ans, list(map(int, input().split())))
    if 0 == ans[0] and 0 == ans[1]:
        print(0)
        exit(0)
print(ans[1] - ans[0] + 1)
### BUGGY CODE ###

import copy
n=input()
n=int(n)
A=[]
for i in range(n):
  A.append(input())
a=[int(j) for j in A]
a_copy=copy.deepcopy(a)
answer=[]
for i in range(n):
  a.pop(i)
  answer.append(max(a))
  a=copy.deepcopy(a_copy)
for k in range(n):
  print(answer.pop(0))

### FIXED CODE ###

import copy
n=int(input())
a=[int(input()) for i in range(n)]
a_copy=copy.deepcopy(a)
a_copy=sorted(a_copy)
max_num=a_copy[-1]
sec_num=a_copy[-2]
answer=[]
for j in range(len(a)):
  if a[j]==max_num:
    answer.append(sec_num)
  else:
    answer.append(max_num)
for k in range(len(answer)):
  print(answer[k])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(500000)

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

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


class X:
    def __init__(self, K, A, B, N, M):
        self.A = A
        self.B = B
        self.K = K
        self.N = N
        self.M = M
        self.ret = 0

    def helper(self, i, j, time, num_a, num_b):
        if time > self.K:
            return

        self.ret = max(self.ret, num_a + num_b)

        if num_a < self.N:
            self.helper(i + 1, j, time + self.A[i], num_a + 1, num_b)

        if num_b < self.M:
            self.helper(i, j + 1, time + self.B[j], num_a, num_b + 1)

        return

    def run(self):
        self.helper(0, 0, 0, 0, 0)
        return self.ret


c = X(K, A, B, N, M)
print(c.run())



### FIXED CODE ###

import bisect

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

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

A_sum = A.copy()
B_sum = B.copy()

for i in range(1, N):
    A_sum[i] = A_sum[i - 1] + A[i]

A_sum = [0] + A_sum

for i in range(1, M):
    B_sum[i] = B_sum[i - 1] + B[i]


max_ = 0
for i, n in enumerate(A_sum):
    if n > K:
        continue

    target = K - n
    v = bisect.bisect_left(B_sum, target)

    if v != M and B_sum[v] == target:
        v += 1

    max_ = max(max_, i + v)

print(max_)
### BUGGY CODE ###

from collections import deque


def solve(H, W, Ch, Cw, Dh, Dw, maze):
    INF = 10 ** 12
    path = [[INF] * W for _ in range(H)]

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    while q:
        y, x, s = q.popleft()
        for dy, dx in walk:
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and maze[ny][nx] == '.' and path[ny][nx] > s:
                path[ny][nx] = s
                q.appendleft((ny, nx, s))
        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and maze[ny][nx] == '.' and path[ny][nx] > s + 1:
                path[ny][nx] = s + 1
                q.append((ny, nx, s + 1))

    ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
    print(ans)


if __name__ == "__main__":
    H, W = map(int, input().split())
    Ch, Cw = map(lambda x: int(x) - 1, input().split())
    Dh, Dw = map(lambda x: int(x) - 1, input().split())
    maze = [input() for _ in range(H)]
    solve(H, W, Ch, Cw, Dh, Dw, maze)


### FIXED CODE ###

from collections import deque


def solve(H, W, Ch, Cw, Dh, Dw, maze):
    # 後の条件分岐を簡略化するためワープしても迷路外に出ないように壁で囲む
    walled_maze = ['##{}##'.format(row) for row in maze]
    walled_maze.insert(0, '##{}##'.format('#' * W))
    walled_maze.insert(0, '##{}##'.format('#' * W))
    walled_maze.append('##{}##'.format('#' * W))
    walled_maze.append('##{}##'.format('#' * W))

    INF = 10 ** 12
    path = [[INF] * (W + 4) for _ in range(H + 4)]
    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    yet = deque()
    yet.append((Ch + 2, Cw + 2, 0))    # 囲った壁の分だけプラス
    path[Ch + 2][Cw + 2] = 0
    done = deque()

    while yet:
        y, x, s = yet.popleft()
        done.append((y, x, s))
        for dy, dx in walk:
            ny = y + dy
            nx = x + dx
            if walled_maze[ny][nx] == '.' and path[ny][nx] > s:
                path[ny][nx] = s
                yet.append((ny, nx, s))
        if len(yet) == 0:
            while done:
                y, x, s = done.popleft()
                for dy, dx in warp:
                    ny = y + dy
                    nx = x + dx
                    if walled_maze[ny][nx] == '.' and path[ny][nx] > s + 1:
                        path[ny][nx] = s + 1
                        yet.append((ny, nx, s + 1))
    ans = path[Dh + 2][Dw + 2] if path[Dh + 2][Dw + 2] < INF else -1
    print(ans)


if __name__ == '__main__':
    H, W = map(int, input().split())
    Ch, Cw = map(lambda x: int(x) - 1, input().split())
    Dh, Dw = map(lambda x: int(x) - 1, input().split())
    maze = [input() for _ in range(H)]
    solve(H, W, Ch, Cw, Dh, Dw, maze)
### BUGGY CODE ###

K, S = map(int, input().split())
count = 0
for x in range(K+1):
    for y in range(K+1):
            for z in range(K+1):
                if x+y+z==S:
                    count=count+1
                else:
                    pass
print(count)

### FIXED CODE ###

K, S = map(int, input().split())

count=0
for x in range(K+1):
    for y in range(K+1):
        if 0<=S-x-y<=K:
            count=count+1
print(count)
### BUGGY CODE ###

x = int(input())

s =[2]
a = x

if x==2:
    print(x)
else:
  for i in range(3,2*x,2):
    if all(i%k!=0 for k in s):
        s.append(i)
        if i >=x:
          print(i)
          exit()
    





### FIXED CODE ###

x = int(input())

s =[2]

if x==2:
    print(x)
    exit()
else:
    for i in range(3,int(x/2),2):
        if all(i%k!=0 for k in s):
            s.append(i)

while any(x%k==0 for k in s):
  x+=1
else:
  print(x)
### BUGGY CODE ###

n,m = map(int,input().split())
graph = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1

flag = False
for i in range(n):
    if graph[0][i] == 1:
        if graph[i][n-1] == 1:
            flag = True
            break
                
if flag:
    print("POSSIBLE")
    
else:
    print("IMPOSSIBLE")


### FIXED CODE ###

n,m = map(int,input().split())
c = [False for i in range(200000)]
d = [False for i in range(200000)]
for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
        c[b] = True 
    if b == n:
        d[a] = True
        
flag = False
for i in range(200000):
    if c[i] and d[i]:
        flag = True
        break
if flag:
    print("POSSIBLE")
    
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

n = int(input())
boss_list = list(map(int, input().split(" ")))

boss_list = sorted(boss_list)


for i in range(1, n+1):
    boss_count = boss_list.count(i)
    del boss_list[:boss_count]
    print(boss_count)

### FIXED CODE ###

n = int(input())
boss_list = list(map(int, input().split(" ")))

boss_count_list = [0] * n


for val in boss_list:
  boss_count_list[val - 1] += 1

for val in boss_count_list:
  print(val)
### BUGGY CODE ###

from collections import deque

n, m, k = map(int, input().split())
f = {i: set() for i in range(1, n+1)}
BL = {i: set() for i in range(1, n+1)}
ans = [0] * n
for _ in range(m):
    a, b = map(int, input().split())
    f[a].add(b)
    f[b].add(a)
for _ in range(k):
    c, d = map(int, input().split())
    BL[c].add(d)
    BL[d].add(c)
for i in range(1, n+1):
    ff = f[i].copy()
    q = deque(f[i])
    while q:
        t = q.popleft()
        for x in f[t]:
            if x not in ff:
                ff.add(x)
                q.append(x)
    ans[i-1] = max(0, len(ff - f[i] - BL[i]) - 1)
print(*ans)


### FIXED CODE ###

def main():
    from sys import stdin
    input = stdin.readline

    n, m, k = map(int, input().split())
    f = [[] for i in range(n)]
    BL = [[] for i in range(n)]
    ans = [0] * n
    for _ in range(m):
        a, b = map(int, input().split())
        f[a-1].append(b-1)
        f[b-1].append(a-1)
    for _ in range(k):
        c, d = map(int, input().split())
        BL[c-1].append(d-1)
        BL[d-1].append(c-1)
    D = {}
    parent = [-1] * n
    visited = [False] * n
    for root in range(n):
        if visited[root]:
            continue
        D[root]  = set([root])
        stack = [root]
        while stack:
            x = stack.pop()
            visited[x] = True
            parent[x] = root
            for t in f[x]:
                if visited[t]:
                    continue
                D[root].add(t)
                stack.append(t)
    for i in range(n):
        grp = D[parent[i]]
        tans = len(grp) - len(f[i]) - 1
        for block in BL[i]:
            if block in grp:
                tans -= 1
        ans[i] = tans
    print(*ans)
main()
### BUGGY CODE ###

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

for i in range(M):
  index = A.index(max(A))
  A[index] = round(A[index]//2)

print(sum(A))


### FIXED CODE ###

import sys
from heapq import heappush, heappop
input = sys.stdin.readline
N,M = map(int, input().split())
A = []
for a in input().split():
  heappush(A,-int(a))

for _ in range(M):
  tmp = heappop(A)
  heappush(A, -(-tmp//2))

print(-sum(A))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

N = int(input())
Xb = input().rstrip()
# N = 2*10**5
# Xb = '1'*N


X = 0
t = 1
for i in range(N):
    if Xb[N-1-i]=='1':
        X += t
    t *= 2

def popcount(x):
    return bin(x).count('1')
def calc(X):
    ans = 0
    while X!=0:
        X %= popcount(X)
        ans += 1
    return ans

ret = []
t = 1
for i in range(N):
    if Xb[N-1-i]=='1':
        Xt = X - t
    else:
        Xt = X + t
    ret.append(calc(Xt))
    t *= 2

for i in range(N):
    print(ret[N-1-i])
    

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

N = int(input())
Xb = input().rstrip()
p = Xb.count('1')
def popcount(x):
    return bin(x).count('1')
def calc(X):
    ans = 0
    while X!=0:
        X %= popcount(X)
        ans += 1
    return ans
Xp = 0
Xm = 0
tp = 1
tm = 1
b = 0
if p>1:
    flag = True
else:
    flag = False

for i in reversed(range(N)):
    if Xb[i]=='1':
        Xp += tp
        Xp %= (p+1)
        if flag:
            Xm += tm
            Xm %= (p-1)
    tp *= 2
    tp %= (p+1)
    if flag:
        tm *= 2
        tm %= (p-1)

for i in range(N):
    if Xb[i]=='1' and p==1:
        print(0)
        continue
    elif Xb[i]=='1':
        X = (Xm - pow(2,N-1-i,p-1)+p-1)%(p-1)
    else:
        X = (Xp + pow(2,N-1-i,p+1))%(p+1)
    print(calc(X)+1)