Harryxun/stf_run huggingface dataset:
def inpl():
    return list(map(int, input().split()))


def dfs(v=0, c=0):
    if visited[v] is True:
        return
    visited[v] = True
    c += counter[v]
    ans[v] = c
    for nv in edge[v]:
        dfs(nv, c)
    return


N, Q = inpl()
AB = [inpl() for i in range(N - 1)]
PQ = [inpl() for i in range(Q)]

edge = [[] for i in range(N)]
for a, b in AB:
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)
counter = {k: 0 for k in range(N)}
for p, q in PQ:
    counter[p - 1] += q

ans = [0 for i in range(N)]
visited = [False for i in range(N)]

dfs()

print(" ".join(list(map(str, ans))))


### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(2 * 10**6)


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


def bfs():
    visited[0] = True
    ans[0] = counter[0]
    deq = deque()
    deq.append(0)
    while deq:
        v = deq.popleft()
        for nv in edge[v]:
            if visited[nv] is True:
                continue
            visited[nv] = True
            ans[nv] = ans[v] + counter[nv]
            deq.append(nv)


N, Q = inpl()

edge = [[] for i in range(N)]
for i in range(N - 1):
    a, b = inpl()
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

counter = {k: 0 for k in range(N)}
for i in range(Q):
    p, q = inpl()
    counter[p - 1] = counter.get(p - 1, 0) + q

ans = [0 for i in range(N)]
visited = [False for i in range(N)]

bfs()

print(" ".join(list(map(str, ans))))
N = int(input())
a = list(map(int, input().split))

print(max(a) - min(a))

### FIXED CODE ###

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

print(max(a) - min(a))
n,m = map(int,input().split())
min = 0
max = 0
for i in range(m):
    l,r = map(int,input().split())
    min = min(min,l)
    max = max(max,r)
print(int(n-max+min))

### FIXED CODE ###

n,m = map(int,input().split())
s = 0
t = n
for i in range(m):
    l,r = map(int,input().split())
    s = max(s,l)
    t = min(t,r)
print(max(t-s+1,0))
K = int(input())

ans = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            ans += math.gcd(math.gcd(a,b),c)
print(ans)
exit()


### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
from queue import PriorityQueue
from fractions import gcd
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def gcd(*numbers):
    return functools.reduce(math.gcd, numbers)
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort(reverse=True)
    return divisors

K = _I()

ans = 0
d = {}
vals = []
for i in range(1, K+1):
    for j in range(1, K+1):
        nums = [i,j]
        nums.sort()
        key = str(i) + '-' + str(j)
        if key in d:
            vals.append(d[key])
        else:
            val = gcd(i,j)
            d[key] = val
            vals.append(val)
#  print(vals)
#  print(d)
for val in vals:
    for k in range(1, K+1):
        #  print(val, k)
        nums = [i,j]
        nums.sort()
        key = str(val) + '-' + str(k)
        if key in d:
            ans += d[key]
        else:
            val = gcd(val, k)
            ans += val
            d[key] = val
print(ans)
exit()
da = list(map(int,input().split()))

k = [[0 for i in range(2)]for j in range(10001)]
i = 0
su = 0
j = 0

while da[0] != 0 and da[1] != 0:
	i = 0
	su = 0
	j = 0
	for i in range(da[0]):
		k[i][0],k[i][1] = map(int,input().split())
		su += k[i][0] * k[i][1]


	sorted(k,key = lambda x: x[1],reverse = True)
	while da[1] > 0 and j != i + 1:
		if da[1] >= k[j][0] and j != i + 1
			su -= k[j][0] * k[j][1]
			da[1] -= k[j][0]
			j += 1
		else:
			su -= da[1] * k[j - 1][1]
			da[1] = 0

	print(su)

	da = list(map(int,input().split()))
	if da[0] == 0 and da[1] == 0:
		break
	k = [[0 for i in range(2)]for j in range(10001)]



### FIXED CODE ###

da = list(map(int,input().split()))

k = [[0 for i in range(2)]for j in range(10001)]
i = 0
su = 0
j = 0

while da[0] + da[1] != 0:
	i = 0
	su = 0
	j = 0
	for i in range(da[0]):
		k[i][0],k[i][1] = map(int,input().split())


	k = sorted(k,key = lambda x: x[1],reverse = True)

	while j != i + 1:
		if da[1] > k[j][0]:
			da[1] -= k[j][0]
			j += 1
		elif da[1] <= k[j][0] and da[1] > 0:
			su += (k[j][0] - da[1]) * k[j][1]
			da[1] = 0
			j += 1
		else:
			su += k[j][0] * k[j][1]
			j += 1

	print(su)

	da = list(map(int,input().split()))

	k = [[0 for i in range(2)]for j in range(10001)]
K, N = map(int, input().split())
A = list(map(int, input().split()))
B = []
for a in A:
  if a < N:
    B.append(A[a+1]-A[a])
  else:
    B.append(A[1]+K-A[a])

print(K-max(B))

### FIXED CODE ###

K, N = map(int, input().split())
A = list(map(int, input().split()))
B = [0] * N
k = 0
for i in A:
  k += 1
  if k != N:
    B[k-1]=A[k]-A[k-1]
  else:
    B[N-1] = A[0] + K - A[N-1]

print(K-max(B))
from collections import Counter
n = input()
s = [''.join(list(input()).sort()) for i in range(n)]
d = Counter(s)
count = 0
for i in d.values():
  if i !=1:
    count+=i
print(count)

### FIXED CODE ###

n = int(input())
d = dict()
for i in range(n):
  S = ''.join(sorted(list(input())))
  if S in d.keys():
    d[S] +=1
  else:
    d[S] = 1
 
ans = 0
for i in d.values():
  ans += i*(i-1)//2
print(ans)
for i in range(100000):
    H,W = map(int,input().split(" "))
    if H + W == 0:
        break
    print("#"*W)
    for j in range(h-2):
        print("#" + "."*(W-2) + "#")
    print("#"*W)
    print("")
    


### FIXED CODE ###

while True:
    H,W = map(int, input().split())
    if H == W == 0: break
    print("#"*W)
    print(("#"+"."*(W-2)+"#\n")*(H-2),end="")
    print("#"*W+"\n")
N, M = map(int, input().split())
a = []
tmp = []
for i in range(N):
    tmp = list(map(str,input().split()))
    a.append(list(tmp[0]))

for i in range(1,N+1):
    for j in range(1,M+1):
        if a[i][j] == '#':
            if a[i][j - 1] != '#' and a[i - 1][j] != '#' and a[i][j + 1] != '#' and a[i + 1][j] != '#':
                print("No")
                exit()
        else:
            pass

print("Yes")

### FIXED CODE ###

H, W = map(int, input().split())
a = []
tmp = []
for i in range(H):
    tmp = list(map(str,input().split()))
    a.append(list(tmp[0]))

for i in range(H):
    for j in range(W):
        if a[i][j] == '#':
            if j - 1 >= 0 and a[i][j - 1] == "#":
                continue
            elif j + 1 < W and a[i][j + 1] == "#" :
                continue
            elif i + 1 < H and a[i + 1][j] == "#" :
                continue
            elif i - 1 >= 0 and a[i - 1][j] == "#":
                continue
            else:
                print("No")
                exit()
 
print("Yes")
s = print(int(input()))
n = 0
for i in range(1, s):
  n = n + 1
return(n)

### FIXED CODE ###

s=int(input())
n=0
while(s>0):
  n=n+s
  s=s-1
print(n)
def cal(S):
    tmp, a, cnt = S[0], 1, 0
    flag = True
    for s in S[1:]:
        if S[0]!=s: flag=False
        if flag: a+=1
        if tmp[-1]==s:
            s = '*'
            ans += 1
        tmp += s
    return a, cnt


S = input().replace('\n', '')
k = int(input())
ans = 0
if len(list(set(S)))==1:
    ans = len(S)*k//2
else:
    a, cnt = cal(S)
    b, _ = cal(S[::-1])
    ans = cnt*k
    if S[0]==S[-1]:
        ans -= ((a//2)+(b//2)-((a+b)//2))*(k-1)
print(ans)

### FIXED CODE ###

def cal(S):
    tmp, a, cnt = S[0], 1, 0
    flag = True
    for s in S[1:]:
        if S[0]!=s: flag=False
        if flag: a+=1
        if tmp[-1]==s:
            s = '*'
            cnt += 1
        tmp += s
    return a, cnt


S = input().replace('\n', '')
k = int(input())
ans = 0
if len(list(set(S)))==1:
    ans = len(S)*k//2
else:
    a, cnt = cal(S)
    b, _ = cal(S[::-1])
    ans = cnt*k
    if S[0]==S[-1]:
        ans -= ((a//2)+(b//2)-((a+b)//2))*(k-1)
print(ans)
h, n = map(int, input().split())
a = list(map(int, input().split())

if h <= sum(a):
   print("yes")
else:
   print("no")

### FIXED CODE ###

h, n = map(int, input().split())
a = list(map(int, input().split()))
if sum(a) >= h:
   print("Yes")
else:
   print("No")
N = int(input())
X = list(map(int, input().split()))
x = sorted(X)
m1 = x[N//2]
m2 = x[N//2-1]
for i in X:
    print(m1 if i < m else m2)

### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
x = sorted(X)
m1 = x[N//2]
m2 = x[N//2-1]
for i in X:
    print(m1 if i < m1 else m2)
n = int(input())
a= [int(i) for i in input().split()]

for i in range(len(a)):
    a[i]-=i+1

import math
#import statistics
#b=statistics.median(a)
b=math.floor(sum(a)/n)

import numpy as np

aa=np.asarray(a)
def p(b,k):
  s=np.sum(np.abs(aa-b))
  t=np.sum(np.abs(aa-b-1))
  if s>t:
    if k==-1:
      print(t)
    else:
      return p(b+1,1)
  elif s==t:
    print(s)
  else:
    if k==1:
      print(s)
    else:
      return p(b-1,-1)
  
p(b,0)



### FIXED CODE ###

n = int(input())
a= [int(i) for i in input().split()]

for i in range(len(a)):
    a[i]-=i+1

aa=sorted(a)
if n%2==0:
  b=(aa[int(n/2-1)]+aa[int(n/2)])/2
else:
  b=aa[int((n-1)/2)]

s=0
for i in aa:
  s+=abs(i-b)
print(int(s))
a,b = map(int,input())
m = max(a,b)
m1 = m*2-1
m2 = a+b
ans = max(m1,m2)
print(ans)

### FIXED CODE ###

a,b = map(int,input().split())
m = max(a,b)
m1 = m*2-1
m2 = a+b
ans = max(m1,m2)
print(ans)
N = int(input())
n = list(map(int, input().split()))

for a in n:
    if a % 2 == 0:
        ans = all(a%3==0 or a%5==0)
if ans:
    print("APPROVED")
else:
    print("DENIED")


### FIXED CODE ###

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

ans = all(a%3==0 or a%5==0 for a in A if a%2==0)
if ans:
    print("APPROVED")
else:
    print("DENIED")
N=int(input())
c=[[0 in range(10)] in range(10)] #c[i][j]=1以上N以下の整数で先頭i末尾jとなる数字の個数
for i in range(1,11):
  for j in range(1,11):
    for k in range(1,N+1):
      k=str(k)
      if k[0]==i and k[-1]==j:
        c[i][j]=c[i][j]+1
S=0
for i in range(1,11):
  for j in range(1,11):
    S=S+c[i][j]*c[j][i]
print(S)

### FIXED CODE ###

N=int(input())
c=[[0 for z in range(10)] for z in range(10)] #c[i][j]=1以上N以下の整数で先頭i末尾jとなる数字の個数
for i in range(1,10):
  for j in range(1,10):
    for k in range(1,N+1):
      k=str(k)
      if k[0]==str(i) and k[-1]==str(j):
        c[i][j]=c[i][j]+1
S=0
for i in range(1,10):
  for j in range(1,10):
    S=S+c[i][j]*c[j][i]
print(S)
def dfs(v, n, graph, visited):
    all_visited = 1

    for i in range(n):
        if visited[i] == 0:
            all_visited = 0
            break

    if all_visited:
        return 1

    n_paths = 0

    for i in range(0, n):
        if not graph[v][i]:
            continue
        if visited[i]:
            continue

        visited[i] = 1
        n_paths += dfs(i, n, graph, visited)
        visited[i] = 0

    return n_paths


def main():
    n, m = [int(i) for i in input().split()]
    graph = [[0] * m for _ in range(m)]
    for _ in range(m):
        a, b = [int(i) for i in input().split()]
        graph[a-1][b-1] = 1
        graph[b-1][a-1] = 1

    visited = [0] * n

    visited[0] = 1
    n_paths = dfs(0, n, graph, visited)
    print(n_paths)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import itertools


def main():
    n, m = [int(i) for i in input().split()]
    path_matrix = [[False] * n for _ in range(n)]
    for _ in range(m):
        a, b = [int(i) for i in input().split()]
        a -= 1
        b -= 1
        path_matrix[a][b] = True
        path_matrix[b][a] = True

    ans = 0
    for path in itertools.permutations(range(n), n):
        if path[0] != 0:
            continue
        for i in range(n):
            if i == n - 1:
                ans += 1
                break
            if not path_matrix[path[i]][path[i+1]]:
                break

    print(ans)


if __name__ == "__main__":
    main()
46 4 40 5

### FIXED CODE ###

a, b, c, d = map(int, input().split())

for i in range(1000):
    c = c - b
    if c <= 0:
        print('Yes')
        break
    a = a - d
    if a <= 0:
        print('No')
        break
n, l = map(int, input().split())
if n = l:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n, l = map(int, input().split())
if n == l:
  print("Yes")
else:
  print("No")
from collections import deque
def main():
    n,m = map(int, input().split())
    if n%2==0 and 2*(m+1)==n:
        lst = deque([i for i in range(1,n+1)])
        for i in range(1,m+1):
            a = lst.popleft()
            b = a + i
            lst.remove(b)
            print(str(a)+' '+str(b))
    else:
        for i in range(1,n//2+1):
            print(str(i)+' '+str(n-i))
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n,m = map(int, input().split())
    if n%2==0 and 2*(m+1)==n:
        if n%4:
            for i in range(1,n//4+1):
                print(i,n//2-i)
            j = n

            for i in range(n//2+1,n//2+n//4+1):
                print(i,j)
                j -= 1
        else:
            for i in range(1,n//4+1):
                print(i,n//2+1-i)
            j = n-1
            for i in range(n//2+1,n//2+n//4):
                print(i,j)
                j -= 1
    else:
        for i in range(1,m+1):
            print(i,n-i)
if __name__ == '__main__':
    main()
n = int(input())
mod = 10**9+7
print ((pow(10,N,mod) - 2*pow(9,N,mod) + pow(8,N,mod)) % mod)

### FIXED CODE ###

N = int(input())
mod = 10**9+7
print ((pow(10,N,mod) - 2*pow(9,N,mod) + pow(8,N,mod)) % mod)
w, h, n = map(int, input().split())
nums_list=[list(map(int, input().split())) for i in range(n)]
minX = 0
maxX = w
minY = 0
maxY = h
for nums in nums_list:
	x, y, a = map(int, nums)
	if a == 1:
		minX = minX if (minX > x) else x
	elif a == 2:
		maxX = maxX if (maxX < x) else x
	elif a == 3:
		minY = minY if (minY > y) else y
	elif a == 4:
		maxY = maxY if (maxY < y) else y
width = maxX-minX if (maxX-minX > 0) else 0
height = maxY-minY if (maxY-minY > 0) else 0
v = width*height
print(v)

### FIXED CODE ###

nums = sorted(list(map(int, input().split())))
result = 'Yes' if (nums[0] + nums[1] == nums[2]) else 'No'
print(result)
result = 0
for n in range (L, R + 1):
    if n % D == 0:
        result += 1
print(result)

### FIXED CODE ###

L, R, D = map(int, input().split())
result = 0
for n in range (L, R + 1):
    if n % D == 0:
        result += 1
print(result)
n=int(input())
str=input()
count=str.count("R")*str.count("G")*str.count("B")
count0=0
for i in range(0,n-2):
    for j in range(i+1,(n+i)/2):
        k=2*j-i
        if str[k]!=str[i] and str[k]!=str[j] and str[i]!=str[j]:
            count0=count0+1
print(count-count0)

### FIXED CODE ###

n=int(input())
str=input()
count=str.count("R")*str.count("G")*str.count("B")
count0=0
for i in range(0,n-2):
    for j in range(i+1,int((n+i-1)/2)+1):
        k=2*j-i
        if str[k]!=str[i] and str[k]!=str[j] and str[i]!=str[j]:
            count0=count0+1
print(count-count0)
N,X = map(int,input().split())
moto = list(map(int,input().split()) for _ in range(N))

num = 0
for i in moto:
    num = num + i

k = 0
while X - num > num:
    X = X - num
    k += 1
#余ったXから最小のmiを作れるだけ作る
k2 = X % min(moto)
print(k1 + k2)

### FIXED CODE ###

N,X = map(int,input().split())
#入力が一文字ずつだから split()は不要
moto = [int(input()) for _ in range(N)]

num = 0
for i in moto:
    num = num + int(i)

X = X - num
#余ったXから最小のmiを作れるだけ作る
k2 = X // min(moto)
#最初作った個数とその後最小のmiのものだけ作った個数の和
print(N + k2)
W, H, x, y, r = map(int, input().split(" "))
if x - r >= 0 and x + r =< W:
    if y - r >= 0 and y + r <= H:
        print("Yes")
    else:
        print("No")
else:
    print("No")

### FIXED CODE ###

W, H, x, y, r = map(int, input().split())
if x - r >= 0 and x + r <= W:
    if y - r >= 0 and y + r <= H:
        print("Yes")
    else:
        print("No")
else:
    print("No")
#!/usr/bin/env python3
import copy

def main():
    N = int(input())
    sides = [[] for _ in range(N-1)]
    
    for i in range(N-1):
        a,b = map(int, input().split())
        sides[a-1].append((b-1,i))

    ans = [[None] for _ in range(N-1)]

    def dfs(focus,parent_color):
        if focus == N - 1:
            return
        color = 1
        for child,index in sides[focus]:
            if parent_color == color:
                color += 1 #もし親の色と被っていた場合はその色を飛ばす
            ans[index] = color
            dfs(child,color)
            color += 1

    dfs(0,0)

    print(max(ans))
    for color in ans:
        print(color)

def main_ver0():
    N = int(input())
    sides = [[int(s) for s in input().split()] for i in range(N-1)]

    # まず最大次数を探す
    sides = sorted(sides)
    max_degree = 0
    current = 1
    current_degree = 0
    for side in sides:
        if side[0]==current:
            current_degree += 1
        else:
            current = side[0]
            current_degree = 2 #見ている頂点が変わるということは、1つ前の頂点から必ず1つ辺が出ているため
        max_degree = max(current_degree,max_degree)
    
    # 上から順番見ていくと、既に使われている色はひとつだけなので、それを除いて塗っていくだけでいい
    # 使用可能な色リスト
    color_list = [i for i in range(1,max_degree+1)]
    color_lists = []
    for i in range(N):
        color_lists.append(copy.copy(color_list))

    sides_color = []
    current = 0
    for side in sides:
        choose_color = color_lists[side[0]-1].pop(0)
        sides_color.append(choose_color)
        color_lists[side[1]-1].remove(choose_color) #次の頂点が使用可能な色から使用済の色を除く

    print(max_degree)
    for color in sides_color:
        print(color)

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(100000)

def main():
    N = int(input())
    sides = [[] for _ in range(N-1)]
    
    for i in range(N-1):
        a,b = map(int, input().split())
        sides[a-1].append((b-1,i))

    ans = [[None] for _ in range(N-1)]

    def dfs(focus,parent_color):
        color = 1
        for child,index in sides[focus]:
            if parent_color == color:
                color += 1 #もし親の色と被っていた場合はその色を飛ばす
            ans[index] = color
            if child < N-1:
                dfs(child,color)
            color += 1 #同じ親から続く次の辺の色を変更する

    dfs(0,0)

    print(max(ans))
    for color in ans:
        print(color)


if __name__ == "__main__":
    main()
N, K = map(int, input().split())
X = map(int, input().split())

k = []
# print(X)

k0 = abs(X[0])
for n in range(0+1, K):
    k0 += X[n] - X[n-1]
# print(k0)
k.append(k0)
for i in range(1, len(X)-K+1):
    # print(i, i-1, i+K, i+K-1)
    ki = k[i-1] - (X[i] - X[i-1]) + (X[i+K-1] - X[i+K-2]) - abs(X[i-1]) + abs(X[i])
    k.append(ki)
print(min(k))


### FIXED CODE ###

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

k = []
# print(X)

k0 = abs(X[0])
for n in range(0+1, K):
    k0 += X[n] - X[n-1]
k.append(k0)
for i in range(1, len(X)-K+1):
    ki = k[i-1] - (X[i] - X[i-1]) + (X[i+K-1] - X[i+K-2]) - abs(X[i-1]) + abs(X[i])
    k.append(ki)
# print(min(k))

l = []
l0 = abs(X[N-1])
for n in range(N-1, N-K, -1):
    l0 += X[n] - X[n-1]
# print(l0)
l.append(l0)
for i in range(1, len(X)-K+1):
    # print(i, i-1, i+K, i+K-1)
    li = l[i-1] - (X[N-i] - X[N-i-1]) + (X[N-K-i+1] - X[N-K-i]) - abs(X[N-i]) + abs(X[N-i-1])
    # print(li)
    l.append(li)
print(min(min(k), min(l)))
N,M=map(int,input().split())
group=[]
number=[0 for i in range(N)]
A,B=map(int,input().split())
group.append([A,B])
number[0]=2


for i in range(M-1):
    A,B=map(int,input().split())
    flag=0
    for j in range(len(group)):
        new=[]
        if A in group[j]:
            flag=1
            if B not in group[j]:
                group[j].append(B)
                number[j]+=1
        elif B in group[j]:
            flag=1
            if A not in group[j]:
                group[j].append(A)
                number[j]+=1
                flag=1
    if flag==0:
        group.append([A,B])
        number[len(group)]=2

print(max(number))


### FIXED CODE ###

n,m=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(m)]
root=[-1]*n

def find(x):
    if root[x]<0:
        return x
    else:
        root[x]=find(root[x])
        return root[x]
    
def unite(x,y):
    parent_x=find(x)
    parent_y=find(y)
    
    if parent_x==parent_y:
        return

    if parent_x>parent_y:
        parent_x,parent_y=parent_y,parent_x

    root[parent_x]+=root[parent_y]
    root[parent_y]=parent_x

def size(x):
    a=find(x)
    return -root[a]

for i in range(m):
    unite(AB[i][0]-1,AB[i][1]-1)

ans=0
for i in range(n):
    ans=max(ans,size(i))

print(ans)
def main():
    n = int(input())
    x = input()
    p = x.count("1")
    f = [0] * (n + 1)
    for i in range(1, n + 1):
        f[i] = f[i % bin(i).count("1")] + 1
    for i in range(n):
        xi = x[:i] + str(1 - int(x[i])) + x[i + 1:]
        pi = p + int(xi[i]) * 2 - 1
        print(f[int(xi, 2) % pi] + 1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    x = input()
    k = int(x, 2)
    p = x.count("1")
    if p > 1:
        kp0 = k % (p - 1)
    kp1 = k % (p + 1)
    f = [0] * (n + 1)
    for i in range(1, n + 1):
        f[i] = f[i % bin(i).count("1")] + 1
    for i in range(n):
        if x[i] == "1":
            pi = p - 1
            if pi == 0:
                print(0)
                continue
            print(f[(kp0 - pow(2, n - i - 1, pi)) % pi] + 1)
        else:
            pi = p + 1
            print(f[(kp1 + pow(2, n - i - 1, pi)) % pi] + 1)


if __name__ == '__main__':
    main()