Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02804 (python)

Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7


def pow(x, t):
    if t == 0:
        return 1
    a = pow(x, t >> 1)
    return a * a * (x ** (t & 1)) % MOD


fact = [0] * N
fact[0] = 1
for i in range(1, N):
    fact[i] = fact[i - 1] * i
    fact[i] %= MOD
ifact = [0] * N
ifact[N - 1] = pow(fact[N - 1], MOD - 2)
for i in range(N - 1, 0, -1):
    ifact[i - 1] = ifact[i] * i
    ifact[i - 1] %= MOD


def nCr(n, r):
    if r < 0 or r > n:
        return 0
    return fact[n] * ifact[r] * ifact[n - r] % MOD


A.sort()
ans = 0
for i in range(K, N + 1):
    C = nCr(i - 1, K - 1)
    ans += A[i - 1] * C
    ans -= A[N - i] * C
    ans %= MOD
print(ans)

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

inv_t = [0, 1] + [0] * (N - 2)
for i in range(2, N):
    inv_t[i] = inv_t[MOD % i] * (MOD - MOD // i) % MOD

A.sort()
ans = 0
C = 1
for i in range(K, N + 1):
    ans += (A[i - 1] - A[N - i]) * C
    ans %= MOD
    C = C * i * inv_t[i - K + 1]
    C %= MOD
print(ans)
Problem p02814 (python)

Fixed submission:
from functools import reduce

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


def f(x):
    c = 0
    while x % 2 == 0:
        x //= 2
        c += 1
    return c


def gcd(x, y):
    return gcd(y, x % y) if y != 0 else x


nth = [f(ai) for ai in a]
if len(set(nth)) == 1:
    half_a = [ai >> 1 for ai in a]
    L = reduce(lambda x, y: x * y // gcd(x, y), half_a)
    ans = (M - L) // (2 * L) + 1 if M >= L else 0
else:
    ans = 0
print(ans)

Buggy submission (verdict: Runtime Error):
from math import gcd
from functools import reduce
N, M = map(int, input().split())
a = list(map(int, input().split()))

half_a = [ai // 2 for ai in a]
L = reduce(lambda x, y: x * y // gcd(x, y), half_a)
print((M - L) // (2 * L) + 1)

Buggy submission (verdict: Runtime Error):
from math import gcd
from functools import reduce
N, M = map(int, input().split())
a = list(map(int, input().split()))

half_a = [ai // 2 for ai in a]
L = reduce(lambda x, y: x * y // gcd(x, y), half_a)
Problem p02821 (python)

Fixed submission:
from itertools import accumulate

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

A.sort(reverse=True)
d = [0] * (A[0] * 2 + 1)
for i in range(N):
    d[A[i]] += 1
d = list(accumulate(d[::-1]))[::-1]
S = list(accumulate([0] + A))

left = 0
right = A[0] * 2 + 1
while right - left > 1:
    mid = (left + right) // 2
    m = 0
    for i in range(N):
        m += d[max(0, mid - A[i])]
    if m >= M:
        left = mid
    else:
        right = mid

ans = 0
m = 0
for i in range(N):
    t = min(d[max(0, right - A[i])], M - m)
    ans += S[t] + A[i] * t
    m += t
ans += left * (M - m)
print(ans)

Buggy submission (verdict: Runtime Error):
from itertools import accumulate

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

A.sort(reverse=True)
d = [0] * (A[0] * 2 + 1)
for i in range(N):
    d[A[i]] += 1
d = list(accumulate(d[::-1]))[::-1]
b = list(accumulate(A))

left = 0
right = A[0] * 2 + 1
while right - left > 1:
    mid = (left + right) // 2
    m = 0
    for i in range(N):
        m += d[max(0, mid - A[i])]
    if m >= M:
        left = mid
    else:
        right = mid

ans = 0
m = 0
for i in range(N):
    t = min(d[max(0, left - A[i])], M - m)
    ans += b[t] + A[i] * t
    m += t
print(ans)

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse=True)
d = [0] * 100001
for i in range(N):
    d[A[i]] = 1
for i in range(100000, 0, -1):
    d[i - 1] += d[i]

left = 0
right = A[0] * 2 + 1
while right - left > 1:
    mid = (left + right) // 2
    m = 0
    for i in range(N):
        m += d[max(0, mid - A[i])]
    if m >= M:
        left = mid
    else:
        right = mid

ans = 0
m = 0
for i in range(N):
    t = min(d[max(0, left - A[i])], M - m)
    ans += sum(A[:t]) + A[i] * t
    m += t
print(ans)
Problem p02900 (python)

Fixed submission:
import math

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

while B > 0:
    A, B = B, A % B
N = A

ans = 1
for i in [2] + list(range(3, int(math.sqrt(N)) + 2, 2)):
    if N % i == 0:
        while N % i == 0:
            N //= i
        ans += 1
if N > 1:
    ans += 1
print(ans)

Buggy submission (verdict: Runtime Error):
import math

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

N = math.gcd(A, B)
primes = []
if N % 2 == 0:
    primes.append(2)
for i in range(3, int(math.sqrt(N)) + 2, 2):
    if N % i == 0:
        for p in primes:
            if i % p == 0:
                break
        else:
            primes.append(i)
print(len(primes) + 1)
Problem p02936 (python)

Fixed submission:
from collections import defaultdict, deque

N, Q = map(int, input().split())
adjacent = defaultdict(list)
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    adjacent[a].append(b)
    adjacent[b].append(a)
ans = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x

q = deque([(0, -1)])
while len(q) > 0:
    u, p = q.pop()
    for v in adjacent[u]:
        if v == p:
            continue
        ans[v] += ans[u]
        q.appendleft((v, u))
print(' '.join([str(ans[i]) for i in range(N)]))

Buggy submission (verdict: Runtime Error):
from collections import defaultdict

N, Q = map(int, input().split())
adjacent = defaultdict(list)
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    adjacent[a].append(b)
    adjacent[b].append(a)
scores = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    scores[p] += x

ans = [0] * N


def dfs(to, fr, score):
    score += scores[to]
    ans[to] = score
    for u in adjacent[to]:
        if u == fr:
            continue
        dfs(u, to, score)


dfs(0, -1, 0)
print(' '.join([str(ans[i]) for i in range(N)]))

Buggy submission (verdict: Runtime Error):
from collections import defaultdict


def dfs(to, fr, score):
    score += scores[to]
    ans[to] = score
    for u in adjacent[to]:
        if u == fr:
            continue
        dfs(u, to, score)


N, Q = map(int, input().split())
adjacent = defaultdict(list)
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    adjacent[a].append(b)
    adjacent[b].append(a)
scores = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    scores[p] += x

ans = [0] * N
dfs(0, -1, 0)
print(' '.join([str(ans[i]) for i in range(N)]))
Problem p02995 (python)

Fixed submission:
import fractions

A, B, C, D = map(int, input().split())
lcm = C * D // fractions.gcd(C, D)

def f(n):
    return n - (n // C + n // D - n // lcm)

print(f(B) - f(A - 1))

Buggy submission (verdict: Runtime Error):
import fractions

A, B, C, D = map(int, input().split())
lcm = C * D // math.gcd(C, D)

def f(n):
    return n - (n // C + n // D - n // lcm)

print(f(B) - f(A - 1))
Problem p03014 (python)

Fixed submission:
H, W = map(int, input().split())
S = [input() for i in range(H)]

h = []
v = []
for i in range(H):
    a = 0
    h.append([])
    v.append([])
    for j in range(W):
        if S[i][j] == '#':
            a = 0
        else:
            a += 1
        h[i].append(a)
    for j in range(W - 1, -1, -1):
        if S[i][j] == '#':
            a = 0
        else:
            if a == 0:
                a = h[i][j]
            h[i][j] = a

for i in range(W):
    a = 0
    for j in range(H):
        if S[j][i] == '#':
            a = 0
        else:
            a += 1
        v[j].append(a)
    for j in range(H - 1, -1, -1):
        if S[j][i] == '#':
            a = 0
        else:
            if a == 0:
                a = v[j][i]
            v[j][i] = a

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, h[i][j] + v[i][j])
print(ans - 1)

Buggy submission (verdict: Runtime Error):
H, W = map(int, input().split())
S = [input() for i in range(H)]

h = []
v = []
for i in range(H):
    a = 0
    h.append([])
    v.append([])
    for j in range(W):
        if S[i][j] == '#':
            a = 0
        else:
            a += 1
        h[i].append(a)
    for j in range(W - 1, -1, -1):
        if S[i][j] == '#':
            a = 0
        else:
            if a == 0:
                a = h[i][j]
            h[i][j] = a

for i in range(W):
    a = 0
    for j in range(H):
        if S[j][i] == '#':
            a = 0
        else:
            a += 1
        v[j].append(a)
    for j in range(H - 1, -1, -1):
        if S[j][i] == '#':
            a = 0
        else:
            if a == 0:
                a = v[j][i]
            v[j][i] = a

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, h[i][j] + v[i][j])
print(ans - 1)
H, W = map(int, input().split())
Problem p03061 (python)

Fixed submission:
from fractions import gcd

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

cum_left = [A[0]]
cum_right = [A[N - 1]]
for i in range(1, N - 1):
    cum_left.append(gcd(cum_left[-1], A[i]))
    cum_right.append(gcd(cum_right[-1], A[N - 1 - i]))

ans = max(cum_left[N - 2], cum_right[N - 2])
for i in range(1, N - 1):
    ans = max(ans, gcd(cum_left[i - 1], cum_right[N - 2 - i]))
print(ans)

Buggy submission (verdict: Runtime Error):
from math import gcd

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

cum_left = [A[0]]
cum_right = [A[N - 1]]
for i in range(1, N - 1):
    cum_left.append(gcd(cum_left[-1], A[i]))
    cum_right.append(gcd(cum_right[-1], A[N - 1 - i]))

ans = max(cum_left[N - 2], cum_right[N - 2])
for i in range(1, N - 1):
    ans = max(ans, gcd(cum_left[i - 1], cum_right[N - 2 - i]))
print(ans)
Problem p03106 (python)

Fixed submission:
import fractions

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

gcd = fractions.gcd(A, B)
order = 0
for i in range(gcd, 0, -1):
    if gcd % i == 0:
        order += 1
        if order == K:
            print(i)
            break

Buggy submission (verdict: Runtime Error):
import math

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

gcd = math.gcd(A, B)
order = 0
for i in range(gcd, 0, -1):
    if gcd % i == 0:
        order += 1
        if order == K:
            print(i)
            break
Problem p03231 (python)

Fixed submission:
from fractions import gcd

N, M = map(int, input().split())
S = input()
T = input()

G = gcd(N, M)
L = N * M // G
n = N // G
m = M // G

ans = True
for k in range(G):
    if S[k * n] != T[k * m]:
        ans = False
        break
print(L if ans else -1)

Buggy submission (verdict: Runtime Error):
from math import gcd

N, M = map(int, input().split())
S = input()
T = input()

G = gcd(N, M)
L = N * M // G
n = N // G
m = M // G

ans = True
for k in range(G):
    if S[k * n] != T[k * m]:
        ans = False
        break
print(L if ans else -1)
Problem p03592 (python)

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

ans = False
for n in range(N + 1):
    for m in range(M + 1):
        if n * (M - m) + m * (N - n) == K:
            ans = True
            break
    else:
        continue
    break
print('Yes' if ans else 'No')

Buggy submission (verdict: Runtime Error):
N, M, K = map(int, input().split())

ans = False
for n in range(N + 1):
    if (M * n - K) % (2 * n - N) == 0:
        ans = True
        break
print('Yes' if ans else 'No')
Problem p03651 (python)

Fixed submission:
from fractions import gcd
from functools import reduce

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

d = reduce(gcd, A)
print('POSSIBLE' if K <= max(A) and K % d == 0 else 'IMPOSSIBLE')

Buggy submission (verdict: Runtime Error):
from math import gcd
from functools import reduce

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

d = reduce(gcd, A)
print('POSSIBLE' if K <= max(A) and K % d == 0 else 'IMPOSSIBLE')
Problem p03729 (python)

Fixed submission:
A, B, C = input().split()
print('YES' if A[-1] == B[0] and B[-1] == C[0] else 'NO')

Buggy submission (verdict: Runtime Error):
A, B, C = map(int, input().split())
print('YES' if A[-1] == B[0] and B[-1] == C[0] else 'NO')
Problem p03737 (python)

Fixed submission:
s1, s2, s3 = input().split()
print(s1[0].upper() + s2[0].upper() + s3[0].upper())

Buggy submission (verdict: Runtime Error):
s1, s2, s3 = map(int, input().split())
print(s1[0].upper() + s2[0].upper() + s3[0].upper())
Problem p03999 (python)

Fixed submission:
S = input()

N = len(S)
ans = 0
for i in range(2 ** (N - 1)):
    bit = '{:010b}'.format(i)[11 - N:]
    formula = S[0]
    for j in range(len(bit)):
        if bit[j] == '1':
            formula += '+'
        formula += S[j + 1]
    ans += eval(formula)
print(ans)

Buggy submission (verdict: Runtime Error):
S = input()

N = len(S)
ans = 0
for i in range(2 ** (N - 1)):
    bit = ('{:0' + str(N - 1) + 'b}').format(i)
    formula = S[0]
    for j in range(len(bit)):
        if bit[j] == '1':
            formula += '+'
        formula += S[j + 1]
    ans += eval(formula)
print(ans)
Problem p02780 (python)

Fixed submission:
def main():
    N, K = map(int, input().split())

    pN_ = []

    ans = 0
    total = 0
    for i, s in enumerate(input().split()):
        total += 1 + int(s)
        pN_.append(total)

        if i == K - 1:
            ans = max(ans, (total / 2))
        elif K <= i:
            ans = max(ans, (total - pN_[i - K]) / 2)

    print(ans)


main()

Buggy submission (verdict: Runtime Error):
def main():
    N, K = map(int, input().split())

    pN_ = []

    ans = 0
    total = 0
    for i, s in enumerate(input().split()):
        total += 1 + int(s)
        pN_.append(total)

        if i == K - 1:
            ans = max(ans, (total / 2)
        elif K <= i:
            ans = max(ans, (total - pN_[i - K]) / 2)

    print(ans)


main()
Problem p02823 (python)

Fixed submission:
def main():
    N, A, B = map(int, input().split())

    if (A + B) % 2 == 0:
        print(abs(A - ((A + B) // 2)))
    else:
        Y = min(B - 1, N - A)

        c = 0
        if 1 < A:
            c += A - 1
        c += 1
        B1 = B - c
        A1 = 1
        X = abs(A1 - ((A1 + B1) // 2)) + c
        if B1 < A1:
            X = 9999999999999999999999999999

        c = 0
        if B < N:
            c += N - B
        c += 1
        A2 = A + c
        B2 = N
        Z = abs(A2 - ((A2 + B2) // 2)) + c
        if B2 < A2:
            Z = 9999999999999999999999999999

        print(min(Y, X, Z))


main()

Buggy submission (verdict: Runtime Error):
def main():
    N, A, B = map(int, input().split())

    if (A + B) % 2 == 0:
        print(abs(A - ((A + B) // 2)))
    else:
        Y = min(B - 1, N - A)

        c = 0
        if 1 < A:
            A1 = 1
            c += A - 1
        c += 1
        B1 = (B - c)
        X = abs(A1 - ((A1 + B1) // 2)) + c

        c = 0
        if B < N:
            B2 = N
            c += B - 1
        c += 1
        A2 = (A + c)
        Z = abs(A2 - ((A2 + B2) // 2)) + c

        print(min(Y, X, Z))


main()

Buggy submission (verdict: Runtime Error):
def main():
    N, A, B = map(int, input().split())

    if (A + B) % 2 == 0:
        print(abs(A - ((A + B) // 2)))
    else:
        Y = min(B - 1, N - A)

        c = 0
        if 1 < A:
            A1 = 1
            c += A - 1
        c += 1
        B1 = (B - c)
        X = abs(A1 - ((A1 + B1) // 2) + c)

        c = 0
        if B < N:
            B2 = N
            c += B - 1
        c += 1
        A2 = (A + c)
        Z = (abs(A2 - ((A2 + B2) // 2)) + c)

        print(min(Y, X, Z))


main()
Problem p03282 (python)

Fixed submission:
#!/usr/bin/env python


def main():
    s = input().strip()
    k = int(input().strip())

    # 1桁目が、1以外のときは、1桁目を表示
    if s[0] != '1':
        print(s[0])
        return

    count_one = 0
    for c in s:
        if c == '1':
            count_one += 1
        else:
            break

    if k <= count_one:
        print(1)
    else:
        print(s[count_one])


main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python

s = input().strip()
k = int(input().strip())

flag = True
for i in range(k):
    if s[i] == '1':
        print(s[i])
        flag = False

if flag:
    print(s[1])

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python

s = input().strip()
k = input().strip()

flag = True
for i in range(k):
    if s[i] == '1':
        print(s[i])
        flag = False

if flag:
    print(s[1])

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python

s = input().strip()
k = input().strip()

if s[0] == '1':
    print(s[1])
else:
    print(s[0])
Problem p03294 (python)

Fixed submission:

import fractions

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


def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


temp = an[0]
for i in range(len(an)):
    temp = lcm(temp, an[i])

m = temp - 1

ret = 0
for a in an:
    ret += m % a

print(ret)

Buggy submission (verdict: Runtime Error):
N = int(input().split())
AN = list(map(int, input().split()))
 
print(sum(AN)-N)

Buggy submission (verdict: Runtime Error):
N = int(input().split())
AN = map(int, input().split())

print(sum(AN)-N)

Buggy submission (verdict: Runtime Error):
import math

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


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


temp = an[0]
for i in range(len(an)):
    temp = lcm(temp, an[i])

m = temp - 1

ret = 0
for a in an:
    ret += m % a

print(ret)

Buggy submission (verdict: Runtime Error):
import math

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


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


temp = an[0]
for i in range(len(an)):
    temp = lcm(temp, an[i])

m = temp - 1

ret = 0
for a in an:
    ret += m % a

print(ret)

Buggy submission (verdict: Runtime Error):

import math

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


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


temp = an[0]
for i in range(len(an)):
    temp = lcm(temp, an[i])

m = temp - 1

ret = 0
for a in an:
    ret += m % a

print(ret)
Problem p02801 (python)

Fixed submission:
alp = input()
asc = ord(alp)
print(chr(asc + 1))

Buggy submission (verdict: Runtime Error):
n, k, m = map(int, input().split())
a = list(map(int, input().split()))

if n * m - sum(a) <= 0:
    print(0)

elif n * m - sum(a) > k:
    print('-1')
    
else:
    print(n * m - sum(a))

Buggy submission (verdict: Runtime Error):
n, k, m = map(int, input().split())
a = map(int, input().split())

if m * n - sum(a) <= 0:
    print(0)

elif 0 < m * n - sum(a) <= k:
    print(m * n - sum(a))
    
else:
    print('-1')
Problem p02922 (python)

Fixed submission:
a, b = map(int, input().split())

g = a - 1
d, r = divmod(b - 1, g)
if r == 0:
    print(d)
else:
    print(d + 1)

Buggy submission (verdict: Runtime Error):
g = a - 1
d, r = divmod(b - 1, g)
if r == 0:
    print(d)
else:
    print(d + 1)
Problem p03624 (python)

Fixed submission:
s = input()
r = set(map(chr, range(97, 97+26)))
r = r - set(s)
if len(r) == 0:
    print('None')
else:
    r = min(r)
    print(r)

Buggy submission (verdict: Runtime Error):
s = input()
r = set(map(chr, range(97, 97+26)))
r = r - set(s)
r = min(r)
print(r)
Problem p02678 (python)

Fixed submission:
N,M = list(map(int,input().split()))
MAX = 1000000000
import queue
dist = [MAX for i in range(N)]
pre = [-1 for i in range(N)]
To = [[] for i in range(N)]#indexに向かっている部屋番号の集合

que = queue.Queue()

for _ in range(M):
    a,b = list(map(int,input().split()))
    a -= 1
    b -= 1
    To[a].append(b)
    To[b].append(a)
dist[0] = 0
que.put(0)
while(not que.empty()):
    v = que.get()
    for u in To[v]:
        if pre[u] != -1: continue
        dist[u] = dist[v] + 1
        que.put(u)
        pre[u] = v
        
        
print('Yes')
for i in pre[1:N]:
    print(i+1)

Buggy submission (verdict: Runtime Error):
N,M = list(map(int,input().split()))
MAX = 1000000000
S = []
Room = [MAX for i in range(N)]#2 - N
Room[0] = 0
ACCESS = [0 for i in range(N-1)]
for _ in range(M):
    a,b = list(map(int,input().split()))
    S.append([a,b])
    S.append([b,a])
for i in S:
    if i[0] == 1:
        Room[i[1]-1] = 1
        ACCESS[i[1]-2] = 1
        S.remove(i)
depth = 1
while max(Room) > MAX/2:
    for i in range(len(Room)):
        if Room[i] ==depth:
            k = 0
            for _ in range(len(S)):
                j = S[k]
                if (j[0] == i+1)*(Room[j[1]-1]>MAX/2):
                    Room[j[1]-1] = depth+1
                    ACCESS[j[1]-2] = i+1
                    S.remove(j)
                    S.remove(j[::-1])
                    k -= 1
                k += 1
    depth += 1
print('Yes')
for i in ACCESS:
    print(i)
Problem p02609 (python)

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

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

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

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

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

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

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

Buggy submission (verdict: Runtime Error):
def readinput():
    n=int(input())
    x=input()
    return n,x

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

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

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

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