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

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N = int(readline())
    A = [[int(i) for i in readline().split()] for _ in range(N)]

    via_min = [[10**15] * N for _ in range(N)]

    for i in range(N):
        for j in range(N):
            for k in range(N):
                if k == i or k == j:
                    continue
                via_min[i][j] = min(via_min[i][j], A[i][k] + A[k][j]) 

    ans = 0
    for i in range(N):
        for j in range(i+1,N):
            if via_min[i][j] < A[i][j]:
                print(-1)
                exit()
            elif via_min[i][j] == A[i][j]:
                continue
            else:
                ans += A[i][j]
    
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N = int(readline())
    A = [[int(i) for i in readline().split()] for _ in range(N)]

    via_min = [[10**15] * N for _ in range(N)]

    for i in range(N):
        for j in range(N):
            for k in range(N):
                if k == i or k == j:
                    continue
                via_min[i][j] = min(via_min[i][j], A[i][k] + A[k][j]) 

    ans = 0
    for i in range(N):
        for j in range(i+1,N):
            if via_min[i][j] < A[i][j]:
                print(-1)
                exit()
            elif via_min[i][j] == A[i][j]:
                continue
            else:
                ans += A[i][j]
    
    print(ans)


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

from collections import deque

H, W = map(int, input().split())
maze = [input() for i in range(H)]
reached = [[0] * W for i in range(H)]
L = []

que = deque([])

for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            L.append(0)
            continue
        que.append([i, j])
        while que:
            py, px = que.popleft()
            dy = (0, 1, 0, -1)
            dx = (1, 0, -1, 0)
            for k, t in zip(dy, dx):
                ny = py + k
                nx = px + t
                if ny < 0 or ny >= H or nx < 0 or nx >= W:
                    continue
                if reached[ny][nx]:
                    continue

                que.append([ny, nx])
                reached[ny][nx] += reached[py][px] + 1

                if maze[ny][nx] == '#':
                    L.append(reached[ny][nx])
                    reached = [[0] * W for i in range(H)]
                    que = deque([])
                    break
                    
print(max(L))

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
maze = [input() for i in range(H)]
reached = [[-1] * W for i in range(H)]

que = deque([])

for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            continue
        reached[i][j] = 0
        que.append([i, j])

while que:
    py, px = que.popleft()
    dy = (0, 1, 0, -1)
    dx = (1, 0, -1, 0)
    for y, x in zip(dy, dx):
        ny = py + y
        nx = px + x
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        if reached[ny][nx] == -1:        
            que.append([ny, nx])
            reached[ny][nx] = reached[py][px] + 1

MAX = 0
for i in range(H):
    MAX = max(max(reached[i]), MAX)

print(MAX)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()
n, m = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)
dp1 = [0] * n


def dfs1(i=0, r=-1):
    s = 1
    for j in e[i]:
        if j != r:
            s *= dfs1(j, i)
            s %= m
    dp1[i] = s
    return s + 1


dfs1()
dp2 = [0] * n
dp2[0] = dp1[0]


def dfs2(i=0, r=-1, s=1):
    a = [1]
    for j in e[i]:
        if j != r:
            a.append(a[-1] * (dp1[j]+1) % m)
    b = [1]
    for j in reversed(e[i]):
        if j != r:
            b.append(b[-1] * (dp1[j]+1) % m)
    b.reverse()

    k = 0
    for j in e[i]:
        if j != r:
            l = (a[k] * b[k + 1] * s + 1)%m
            dp2[j] = l * dp1[j] % m
            dfs2(j, i, l)
            k += 1


dfs2()
print("\n".join(map(str,dp2)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()
n, m = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)
dp1 = [0] * n


def dfs1(i=0, r=-1):
    s = 1
    for j in e[i]:
        if j != r:
            s *= dfs1(j, i)
            s %= m
    dp1[i] = s
    return s + 1


dfs1()
dp2 = [0] * n
dp2[0] = dp1[0]


def dfs2(i=0, r=-1, s=1):
    a = [1]
    for j in e[i]:
        if j != r:
            a.append(a[-1] * (dp1[j]+1) % m)
    b = [1]
    for j in reversed(e[i]):
        if j != r:
            b.append(b[-1] * (dp1[j]+1) % m)
    b.reverse()

    k = 0
    for j in e[i]:
        if j != r:
            l = (a[k] * b[k + 1] * s + 1)%m
            dp2[j] = l * dp1[j] % m
            dfs2(j, i, l)
            k += 1


dfs2()
print("\n".join(map(str,dp2)))
### BUGGY CODE ###

n, q = map(int, input().split())
S = input()
for i in range(q):
    l, r = map(int, input().split())
    S_ = S[l-1:r]
    print(S_.count("AC"))

### FIXED CODE ###

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

S = list(input())

A = [0]

for i in range(1, n+1):
    # if S[i-1:i]:
    if S[i-2:i] == ['A', 'C']:
        A.append(A[-1] + 1)
    else: 
        A.append(A[-1])
# print(A[1:])
A = A[1:]
for i in range(q):
    a, b = map(int, input().split())
    print(A[b-1] - A[a-1])
### BUGGY CODE ###

x=int(input())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if i != n // i:
                divisors.append([i,n//i])
            else:
                divisors.append([i,i])
    return divisors
l=make_divisors(x)
for x,y in l:
    for i in range(10**5):
        p=i-x
        if i**4+(i**3)*p+(i**2)*(p**2)+i*(p**3)+p**4==y:
            print(i,p)
            break

### FIXED CODE ###

x=int(input())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if i != n // i:
                divisors.append([i,n//i])
            else:
                divisors.append([i,i])
    return divisors
l=make_divisors(x)
for x,y in l:
    for i in range(10**4):
        p=i-x
        if i**4+(i**3)*p+(i**2)*(p**2)+i*(p**3)+p**4==y:
            print(i,p)
            break
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# D

import sys
# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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

max_len = len(bin(max(a))[2:])
l = [0] * max_len

for a in a:
    temp = bin(a)[2:][::-1]
    for i in range(len(temp)):
        l[i] += int(temp[i])

ans = 0
mod = 10**9 + 7

for i in range(max_len):
    ans += pow(2, i, mod) * l[i] * (N-l[i])

print(ans % mod)


### FIXED CODE ###

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

max_len = len(bin(max(a))[2:])
l = [0] * max_len

ans = 0
mod = 10**9 + 7

for i in range(max_len):
    for x in a:
        l[i] += x >> i & 1
    ans += pow(2, i, mod) * l[i] * (N-l[i])

print(ans % mod)
### BUGGY CODE ###

n,m=(int(i) for i in input().split())
p = int(m/n)
while p>1:
    if m%p==0 and m>=n*p:
        break
    p-=1
print(p)

### FIXED CODE ###

n,m=(int(i) for i in input().split())
p = int(m**(1/2))
divisors = []
for i in range(1,p+1):
    if m%i == 0:
        if n*i<=m:
            divisors.append(i)
        if n<=i:
            divisors.append(int(m/i))
print(max(divisors))
### BUGGY CODE ###

import bisect
n = int(input())
s = input()
R,G,B = [],[],[]
for i in range(n):
    if s[i]=='R':
        R.append(i)
    elif s[i]=='G':
        G.append(i)
    else:
        B.append(i)

ans = 0
for i in range(n):
    for j in range(i+1, n):
        ci, cj = s[i], s[j]
        if ci==cj:
            continue
        ng = 2*j-i
        if (ci=='R' and cj=='B') or (ci=='B' and cj=='R'):
            ans += len(G)-bisect.bisect_left(G, j)
            if ng in G:
                ans -= 1
        elif (ci=='R' and cj=='G') or (ci=='G' and cj=='R'):
            ans += len(B)-bisect.bisect_left(B, j)
            if ng in B:
                ans -= 1
        else:
            ans += len(R)-bisect.bisect_left(R, j)
            if ng in R:
                ans -= 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = s.count('R')*s.count('G')*s.count('B')
if ans==0:
    print(ans)
else:
    for i in range(n):
        for j in range(i+1, n):
            k=2*j-i
            if k<n:
                if s[i]!=s[j] and s[j]!=s[k] and s[i]!=s[k]:
                    ans -= 1
    print(ans)
### BUGGY CODE ###

N = int(input())
cs = list(input())

ans = 0
sorted = N - 1
for i in range(N):
  if cs[i] == "W":
    for j in range(sorted, i, -1):
      if cs[j] == "R":
        cs[i], cs[j] = cs[j], cs[i]
        ans += 1
        sorted = j
        break
  if i > sorted:
    break
print(str(ans))

### FIXED CODE ###

N = int(input())
cs = list(input())

ans = 0
sorted = N - 1
for i in range(N):
  if cs[i] == "W":
    for j in range(sorted, i, -1):
      sorted = j - 1
      if cs[j] == "R":
        cs[i], cs[j] = cs[j], cs[i]
        ans += 1
        break
  if (i + 1) > sorted:
    break
print(str(ans))
### BUGGY CODE ###

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

dice = list(map(int, input().split()))
a = 0
b = 0
for j in range(k):
    a += dice[j]
    b += dice[j]
res = 0
ll = 0
s = 0
for i in range(len(dice)):
    if i < k:
        continue
    a += dice[i]
    a -= dice[s]
    if a > b:
        b = a
        ll = i
    s += 1

for mn in range(ll - k + 1, ll + 1):
    ss = range(dice[mn] + 1)
    p = 1 / dice[mn]
    ex = 0
    for x in ss:
        px = p * x
        ex += px
    res += ex
print(res)

### FIXED CODE ###

n, k = map(int, input().split())
 
dice = list(map(int, input().split()))
 
a = sum(dice[0: k])
b = sum(dice[0: k])
 
res = 0
ll = 0
s = 0

for i in range(k, len(dice)):
    a += dice[i]
    a -= dice[i - k]
    if a > b:
        b = a
 
res = (b + k) /2.0
 
print(res)
### BUGGY CODE ###

import random
from copy import deepcopy

d = int(input())
c = list(map(int,input().split()))
s = [list(map(int,input().split())) for _ in range(d)]

ma = 0
li = [0]*26

for i in range(1000):
    lin = [random.randrange(0, 26, 1) for _ in range(d)]
    point = 0
    lastd = [0]*26
    for j,k in enumerate(lin):
        point += s[j][k]
        lastd[k] = j+1
        for l in range(26):
            point -= c[l]*(j+1-lastd[l])
        if point > ma:
            ma = point
            li = deepcopy(lin)

for i in li:
    print(i+1)

### FIXED CODE ###

import random

d = int(input())
c = list(map(int,input().split()))
s = [list(map(int,input().split())) for _ in range(365)]

for i in range(d):
    print(random.randrange(1, 27, 1))
### BUGGY CODE ###


from functools import reduce
from fractions import gcd

n = int(input())
list_ = list(map(int, input().strip().split()))

reductive_gcd = lambda list_: list_[0] if len(list_) == 1 else reduce(gcd, list_)

ans = 0
for i in range(n):
    temp = list_.pop(0)
    gcd_ = reductive_gcd(list_)
    list_.append(temp)
    if gcd_ > ans:
        ans = gcd_

print(ans)


### FIXED CODE ###

from fractions import gcd

n = int(input())
list_ = list(map(int, input().strip().split()))

gcd_from_left = [0]
gcd_from_right = [0]
for i in range(n):
    gcd_from_left.append(gcd(gcd_from_left[i], list_[i]))
    gcd_from_right.append(gcd(gcd_from_right[i], list_[-(i + 1)]))

gcd_from_left.insert(0, 0)
gcd_from_right.insert(0, 0)
gcd_from_right.reverse()

print(max(gcd(gcd_from_left[i], gcd_from_right[i]) for i in range(n + 2)))
### BUGGY CODE ###

import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = 0
MOD = 10**9 + 7
if k == 1:
    print(0)
    exit()


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


for min_index in range(n-k+1):
    for max_index in range(min_index+k-1, n):
        comb_num = combinations_count(max_index-min_index-1, k-2)
        ans += (a[max_index] - a[min_index]) * comb_num
    ans %= MOD

print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = 0
MOD = 10**9 + 7
if k == 1:
    print(0)
    exit()

mod = 10 ** 9 + 7
fact = [1]
fact_inv = [1]
for i in range(10 ** 5):
    new_fact = fact[-1] * (i + 1) % mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact, mod - 2, mod))


def cmb(n, k, mod=MOD):
    return fact[n] * fact_inv[k] % mod * fact_inv[n - k] % mod


for max_index in range(k-1, n):
    ans += a[max_index] * cmb(max_index, k-1)
    ans %= MOD

for min_index in range(0, n-k+1):
    ans -= a[min_index] * cmb(n-(min_index+1), k-1)
    ans %= MOD

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

import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

n = int(input())
list_ABC = [ list(map(int,input().split(" "))) for i in range(n-1)]
q, k = map(int, input().split())
list_XY = [ list(map(int,input().split(" "))) for i in range(q)]

ma = [[0]*n for _ in range(n)]
for a, b, c in list_ABC:
    ma[a-1][b-1] = c
    ma[b-1][a-1] = c

a = csgraph_from_dense(ma, null_value=0)
b = dijkstra(a, indices=k-1 , directed=False).astype(int)

for x, y in list_XY:
    print(b[x-1]+b[y-1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)
 
N = int(input())
ABC = [list(map(int, input().split())) for i in range(N-1)]
Q, K = map(int, input().split())
D = [0] * (N+1)
L = [[] for i in range(N+1)]
for a, b, c in ABC:
    L[a].append([b, c])
    L[b].append([a, c])
 
 
def dfs(n, np):
    for nc in L[n]:
        if nc[0] == np:
            continue
        else:
            D[nc[0]] = D[n] + nc[1]
            dfs(nc[0], n)
 
 
dfs(K, 0)
for i in range(Q):
    x, y = map(int, input().split())
    print(D[x] + D[y])
### BUGGY CODE ###

n,k=map(int,input().split())
li=[[0,0] for i in range(n)]
for i in range(n):
    li[i][0],li[i][1]=map(int,input().split())

#####################
li.sort(reverse=True,key=lambda x:x[1])

def calc_score(li,choice):
    score=0
    k=[]
    for i in choice:
        score+=li[i][1]
        k.append(li[i][0])        
    score+=len(set(k))**2
    return score

def find_num_neta(choice,li):
    k=[]
    for i in choice:
        k.append(li[i][0])
    return len(set(k))

#-----------------------------------------
best_list=[]
not_best_list=[]

for i in li:
    if i[0] in [best_list[p][0] for p in range(len(best_list))]:
        not_best_list.append(i)
    else:
        best_list.append(i)

#-----------------------------------------


first_choice=list(range(k))
score=calc_score(li,first_choice)
li_choice_set=set([li[i][0] for i in first_choice])


#------------------------------------------------
s2=min(find_num_neta(list(range(n)),li),k)
s1=find_num_neta(first_choice,li)


for i in range(s1+1,s2+1):

    oishisa=0
    for j in range(i):
        oishisa+=best_list[j][1]
    for j in range(k-i):
        oishisa+=not_best_list[j][1]
    
    new_score=i**2+oishisa

    
    if score<new_score:
        score=new_score
        
    
print(score)

### FIXED CODE ###

n,k=map(int,input().split())
li=[[0,0] for i in range(n)]
for i in range(n):
    li[i][0],li[i][1]=map(int,input().split())



def find_num_neta(choice,li):
    k=[]
    for i in choice:
        k.append(li[i][0])
    return len(set(k))
#-----------------------------------------

li.sort(reverse=True,key=lambda x:x[1])
s2=min(find_num_neta(list(range(n)),li),k)
s1=find_num_neta(list(range(k)),li)
oishisa=sum([li[i][1] for i in range(k)])
score=oishisa+s1**2

#-----------------------------------------
li.sort(key=lambda x:x[0])
best_list=[]
not_best_list=[]


m=-1
for i in li:
    if m==i[0]:
        not_best_list.append(i)
    else:
        best_list.append(i)
        m=i[0]
        
not_best_list.sort(reverse=True,key=lambda x:x[1])
best_list.sort(reverse=True,key=lambda x:x[1])



 
 
for i in range(s1+1,s2+1):
    oishisa=oishisa+best_list[i-1][1]-not_best_list[k-i][1]
    
    new_score=i**2+oishisa
    
    if score<new_score:
        score=new_score
        
    
print(score)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = 0
for m in range(n-1):
    for o in range(m+1,n):
        b = b + a[m]*a[o]
c = b % (10**9+7)
print(c)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = 0
d = sum(a)
for m in range(n-1):
    d = d -a[m]
    b = b + a[m]*d
    if b >= 10**9+7:
        b = b % (10**9+7)
print(b)
### BUGGY CODE ###

s = input()[::-1]
l = len(s)
MOD = 2019
ans = 0
mods = [0] * 2019
mods[0] = 1
num = 0
cnt = 0
for i in s:
    num += int(i) * (10**cnt)
    num %= MOD
    mods[num] += 1
    cnt += 1

for j in mods:
    ans += int(j*(j-1)/2)

print(ans)


### FIXED CODE ###

s = input()[::-1]
l = len(s)
MOD = 2019
ans = 0
mods = [0] * 2019
mods[0] = 1
num = 0
cnt = 0
d = 1
for i in s:
    num += int(i) * d
    num %= MOD
    mods[num] += 1
    d *= 10
    d %= MOD

for j in mods:
    ans += int(j*(j-1)/2)

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

def chmin(a, b):
    if a > b:
        a = b
        return a
    else:
        return a

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

dp = [10**9] * n
dp[0] = 0


for i in range(1, n):
    for j in range(k):
        if i - j < 1:
            continue
        else:
            dp[i] = chmin(dp[i], dp[i - 1 - j] + abs(ls[i] - ls[i - 1 - j]))

print(dp[n - 1])

### FIXED CODE ###

def chmin(a, b):
    if a > b:
        a = b
        return a
    else:
        return a

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

dp = [10**9] * n
dp[0] = 0


for i in range(1, n):
    for j in range(k):
        if i - j < 1:
            continue
        else:
            dp[i] = chmin(dp[i], dp[i - 1 - j] + abs(ls[i] - ls[i - 1 - j]))

print(dp[n - 1])
### BUGGY CODE ###

import sys
import math
import collections
from collections import deque
def main():
    #n = int(input())
    #a, b = map(int, input().split())
    s = input()
    #x = list(map(int, input().split()))
    q = int(input())
    d = deque([])
    for i in range(len(s)):
        d.append(s[i])

    rev = 1
    for i in range(q):
        que = sys.stdin.readline().split()
        if que[0] == "1":
            rev *= -1

        else:
            if rev == 1:
                if que[1] == "1":
                    d.appendleft(que[2])
                else:
                    d.append(que[2])

            else:
                if que[1] == "1":
                    d.append(que[2])
                else:
                    d.appendleft(que[2])


    if rev == 1:
        for i in range(len(d)):
            print(d[i], end="")
    else:
        for i in range(len(d)):
            print(d[len(d) - i - 1], end="")

main()


### FIXED CODE ###

import sys
import math
import collections
from collections import deque
def main():
    #n = int(input())
    #a, b = map(int, input().split())
    s = input()
    #x = list(map(int, input().split()))
    q = int(input())
    d = deque([])
    for i in range(len(s)):
        d.append(s[i])

    rev = 1
    for i in range(q):
        que = sys.stdin.readline().split()
        if que[0] == "1":
            rev *= -1

        else:
            if rev == 1:
                if que[1] == "1":
                    d.appendleft(que[2])
                else:
                    d.append(que[2])

            else:
                if que[1] == "1":
                    d.append(que[2])
                else:
                    d.appendleft(que[2])


    if rev == 1:
        for i in range(len(d)):
            print(d.popleft(), end="")
    else:
        for i in range(len(d)):
            print(d.pop(), end="")

main()
### BUGGY CODE ###

s = input()
t = len(s)

m = [0 for i in range(2019)]
m[0] = 1
a = 0
for i in reversed(range(0, t)):
    a += 10**(t-i-1) * int(s[i])
    a = a % 2019
    m[a] += 1

def triangle(n):
    if n > 1:
        return n * (n-1) // 2
    else:
        return 0

p = list(map(triangle, m))
# print(p)
print(sum(p))


### FIXED CODE ###

s = input()
t = len(s)

x = []
y = 0

while 10 ** y % 2019 not in x:
    x.append(10 ** y % 2019)
    y += 1

z = len(x)

m = [0 for i in range(2019)]
m[0] = 1
a = 0
for i in reversed(range(0, t)):
    a += x[(t-i-1) % z] * (int(s[i]) % 2019)
    a = a % 2019
    m[a] += 1

def triangle(n):
    if n > 1:
        return n * (n-1) // 2
    else:
        return 0

p = list(map(triangle, m))
# print(p)
print(sum(p))
### BUGGY CODE ###

import numpy as np
N=int(input())
A=list(map(int,(input().split())))
npArray = np.array(A)
npArray=npArray.copy()
ans=np.sum(npArray)
Q=int(input())
B=[]
C=[]
for _ in range(Q):
  L, R = map(int,(input().split()))
  B.append(L)
  C.append(R)

for i in range(Q):
  B_count=np.count_nonzero(npArray == B[i])
  sa=(C[i]-B[i])*B_count
  upNpArray = np.where(npArray == B[i], C[i], npArray)
  ans= ans+sa
  print(ans)
  npArray=upNpArray.copy()


### FIXED CODE ###

import collections
import copy
N=int(input())
A=list(map(int,(input().split())))
ans=sum(A)
Q=int(input())
col = collections.Counter(A)

for i in range(Q):
  L, R = map(int,(input().split()))
  sa=(R-L)*col[L]
  col[R]+=copy.copy(col[L])
  col[L]=0
  ans= ans+sa
  print(ans)
### BUGGY CODE ###

def resolve():
  N = int(input())
  X = input()

  if N == 1:
    if X.count("1"):
      print(0)
    else:
      print(1)
    return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        if i == N - 1:
          Xi = X_int_p + 1
        else:
          Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = 2**(N-i-1)%(base_1_count-1)
      if X_int_m <= pow_2:
        Xi = X_int_m - pow_2 + base_1_count-1
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)
      while Xi >= base_1_count+1:
        Xi %= base_1_count+1

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      # print("Xi={0}".format(Xi))
      Xi %= num_of_1
      count += 1
    print(count)
    # print("==")

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

def resolve():
  N = int(input())
  X = input()

  if N == 1:
    if X.count("1"):
      print(0)
    else:
      print(1)
    return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        if i == N - 1:
          Xi = X_int_p + 1
        else:
          Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = pow(2, N-i-1, base_1_count-1)
      if X_int_m <= pow_2:
        Xi = X_int_m - pow_2 + base_1_count-1
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + pow(2, N-i-1, base_1_count+1)
      while Xi >= base_1_count+1:
        Xi %= base_1_count+1

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      Xi %= num_of_1
      count += 1
    print(count)

if __name__ == "__main__":
    resolve()