Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
a = list(map(int, input().split()))

arr = [-1]*n
next_town = 0
arr[0] = 0
flag = False
for i in range(1, k+1):
    print(next_town+1)
    next_town = a[next_town] - 1
    if arr[next_town] >= 0:
        flag = True
        x = i - arr[next_town]
        l = arr[next_town]
        break
    else:
        arr[next_town] = i
print(flag, x, k%x)
if flag == False:
    print(next_town+1)
else:
    for i in range((k-l)%x):
        print(next_town+1)
        next_town = a[next_town] - 1

    print(next_town+1)

Fixed submission:
n, k = map(int, input().split())
a = list(map(int, input().split()))

arr = [-1]*n
next_town = 0
arr[0] = 0
flag = False
for i in range(1, k+1):
    #print(next_town+1)
    next_town = a[next_town] - 1
    if arr[next_town] >= 0:
        flag = True
        x = i - arr[next_town]
        l = arr[next_town]
        break
    else:
        arr[next_town] = i
#print(flag, x, k%x)
if flag == False:
    print(next_town+1)
else:
    for i in range((k-l)%x):
        #print(next_town+1)
        next_town = a[next_town] - 1

    print(next_town+1)
Buggy python submission (verdict: Time Limit Exceeded):
import math
import sys
x = int(input())

for s in range(1, int(math.sqrt(x))+1):
    if x % s == 0:
        t = x // s
        #print(s, t)
        for b in range(-100000, 100000):
            if (b+s)**5 - b**5 == x:
                print(b+s, b)
                sys.exit(0)
            elif (b+t)**5 - b**5 == x:
                print(b+t, b)
                sys.exit(0)


Fixed submission:
import math
import sys
x = int(input())

for s in range(1, int(math.sqrt(x))+1):
    if x % s == 0:
        t = x // s
        #print(s, t)
        for b in range(-1000, 1000):
            if (b+s)**5 - b**5 == x:
                print(b+s, b)
                sys.exit(0)
            elif (b+t)**5 - b**5 == x:
                print(b+t, b)
                sys.exit(0)

Buggy python submission (verdict: Time Limit Exceeded):
import math
x = int(input())

for s in range(1, int(math.sqrt(x))+1):
    if x % s == 0:
        t = x // s
        #print(s, t)
        for b in range(-100000, 100000):
            if (b+s)**5 - b**5 == x:
                print(b+s, b)
                break
            elif (b+t)**5 - b**5 == x:
                print(b+t, b)
                break


Fixed submission:
import math
import sys
x = int(input())

for s in range(1, int(math.sqrt(x))+1):
    if x % s == 0:
        t = x // s
        #print(s, t)
        for b in range(-1000, 1000):
            if (b+s)**5 - b**5 == x:
                print(b+s, b)
                sys.exit(0)
            elif (b+t)**5 - b**5 == x:
                print(b+t, b)
                sys.exit(0)
Buggy python submission (verdict: Runtime Error):
n = int(input())

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

Flag = True
for i in range(n):
    if a[i] % 2 == 0:
        if a[i] % 3 == 0 or a[i] % 5 == 0:
        else:
            Flag = False
            break
if Flag == True:
    print('APPROVED')
else:
    print('DENIED')

Fixed submission:
n = int(input())

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

Flag = True
for i in range(n):
    if a[i] % 2 == 0:
        if a[i] % 3 == 0 or a[i] % 5 == 0:
            pass
        else:
            Flag = False
            break
if Flag == True:
    print('APPROVED')
else:
    print('DENIED')
Buggy python submission (verdict: Time Limit Exceeded):
h = int(input())

cnt = 1
i = 2
while True:
    h //= 2
    cnt += i
    i *= 2
    if h == 1:
        break

print(cnt)

Fixed submission:
h = int(input())

cnt = 1
i = 2
if h == 1:
    print(1)
else:
    while True:
        h //= 2
        cnt += i
        i *= 2
        if h == 1:
            break

    print(cnt)
Buggy python submission (verdict: Runtime Error):
import math

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

p = 0
for i in range(N):
    p += 1/N * (1/2) ** max(0, math.ceil(math.log2(K/(i+1))))

print(p)

Fixed submission:
import math

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

p = 0
for i in range(N):
    p += 1/N * (1/2) ** max(0, math.ceil(math.log2(K/(i+1))))

print(p)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split()) 
A = [list(map(int, input().split())) for i in range(N)]
A.sort()
su = 0
mo = 0
cnt = 0
for i in range(N):
  if M < su + A[i][1]:
    break
  else:
    su += A[i][1]
    mo += A[i][0]*A[i][1]
    cnt += 1
print(mo + (M-su)*A[cnt][0])

Fixed submission:
N, M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
A.sort()
su = 0
mo = 0
cnt = 0
for i in range(N):
  if M <= su + A[i][1]:
    break
  else:
    su += A[i][1]
    mo += A[i][0]*A[i][1]
    cnt += 1
print(mo + (M-su)*A[cnt][0])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [[0, 0]for i in range(N)]
for i in range(N):
  A[i][0], A[i][1] = map(int, input().split())
a = [0, 0]

def max1(L, p):
  a = L[0][p]
  ix = 0
  for i in range(1, len(L)):
    if a > L[i][p]:
      a = L[i][p]
      ix = i
  return ix

for i in range(N):
  j = i % 2
  idx = max1(A, j)
  a[j] += A[idx][j]
  del A[idx]

print(a[0]-a[1])

Fixed submission:
N = int(input())
A = [[0, 0, 0]for i in range(N)]
for i in range(N):
  a, b = list(map(int, input().split()))
  A[i] = a+b, a, b
A.sort(reverse=True)
x = 0
for i in range(N):
    x += (-1)**i * A[i][1+i%2]
print(x)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

N, W = map(int, input().split())
w = np.zeros(N, dtype=int)
v = np.zeros(N, dtype=int)

for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = np.zeros((N+1, W+1), dtype=int)

for i in range(N):
    for j in range(W+1):
        if j >= w[i]:
            dp[i+1,j] = max(dp[i,j], dp[i,j-w[i]]+v[i])
        else:
            dp[i+1,j] = dp[i,j]


print(dp[N][W])


Fixed submission:
N, W = map(int, input().split())
w = [0]*N
v = [0]*N

for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [[0]*(W+1) for i in range(N+1)]

for i in range(N):
    for j in range(W+1):
        if j >= w[i]:
            dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
        else:
            dp[i+1][j] = dp[i][j]


print(dp[N][W])

Buggy python submission (verdict: Time Limit Exceeded):
def func():
    N, W = map(int, input().split())
    w = [0]*N
    v = [0]*N

    for i in range(N):
        w[i], v[i] = map(int, input().split())

    dp = [[0]*(W+1) for i in range(N+1)]

    for i in range(N):
        for j in range(W+1):
            if j >= w[i]:
                dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
            else:
                dp[i+1][j] = dp[i][j]


    print(dp[N][W])

func()

Fixed submission:
N, W = map(int, input().split())
w = [0]*N
v = [0]*N

for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [[0]*(W+1) for i in range(N+1)]

for i in range(N):
    for j in range(W+1):
        if j >= w[i]:
            dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
        else:
            dp[i+1][j] = dp[i][j]


print(dp[N][W])

Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
w = [0]*N
v = [0]*N

for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [[0]*(W+1) for i in range(N+1)]

for i in range(N):
    for j in range(W+1):
        if j >= w[i]:
            dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
        else:
            dp[i+1][j] = dp[i][j]


print(dp[N][W])

Fixed submission:
N, W = map(int, input().split())
w = [0]*N
v = [0]*N

for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [[0]*(W+1) for i in range(N+1)]

for i in range(N):
    for j in range(W+1):
        if j >= w[i]:
            dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
        else:
            dp[i+1][j] = dp[i][j]


print(dp[N][W])
Buggy python submission (verdict: Runtime Error):
N = int(input())
W = []
flag = "Yes"
last_chara = ''
for i in range(N):
  now_W = input()
  www = list(now_W)
  if i != 0:
    if www[0] != last_chara:
      flag = "No"
      break
  if now_W in W:
    flag = "No"
    break
  W.append(now_W)
  last_chara = www[-1]
print(flag)

Fixed submission:
A, B = list(map(int, input().split()))
if A * B % 2 == 0:
  print("No")
else:
  print("Yes")
Buggy python submission (verdict: Runtime Error):
N = int(input())
while N > 0:
    if N % 4 == 0 or N % 7 == 0:
        flag = True
        break
    else:
        N -= 7
if flag == True:
    print("Yes")
else:
    print("No")

Fixed submission:
flag = False
N = int(input())
while N > 0:
    if N % 4 == 0 or N % 7 == 0:
        flag = True
        break
    else:
        N -= 7
if flag == True:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Time Limit Exceeded):
from functools import reduce
N = int(input())

def up(n):
  global next_digit
  n += next_digit
  next_digit = 0
  if n == 0:
    return 0
  elif n == 1:
    return 1
  else:
    next_digit = 1
    return 0

digit = [0 for i in range(30)]
#a = [(digit[i] * (2 ** i)) for i in range(30)]
while True:
  a = [(digit[i] * ((-2) ** i)) for i in range(30)]
  #print(digit)
  #print(a)
  if sum(a) == N:
    break
  else:
    next_digit = 0
    digit[0] += 1
    for i in range(30):
      digit[i] = up(digit[i])
#print(digit)
rev_digit = [i for i in reversed(digit)]
result = reduce(lambda x, y:10*x+y, rev_digit)
print(result)

Fixed submission:
N = int(input())
dig = []
def dmod(a, b):
  if a % b < 0:
    return [1, a//b+1]
  else:
    return [a%b, a//b]
while abs(N) > 1 :
  d, N = dmod(N, -2)
  dig.append(d)
if N == -1:
  dig += [1, 1]
else:
  dig.append(N)
dig.reverse()

n = ''.join(map(str, dig))
print(int(n))
Buggy python submission (verdict: Runtime Error):
s_list = list(input())
s_list1 = s_list
count = 0

if s_list[0] == "A":
    del s_list[:2], s_list[-1]
    for i in range(len(s_list)):
        if s_list[i] == "C":
            count += 1
            isC = i + 2
    if count != 1:
        print("WA")
    else:
        del s_list1[isC]
        Str = "".join(s_list1)
        if Str.islower():
            print("AC")
        else:
            print("WA")
else:
    print("WA")

Fixed submission:
s_list = list(input())
s_list1 = s_list[1:]
count = 0

if s_list[0] == "A":
    del s_list[:2], s_list[-1]
    for i in range(len(s_list)):
        if s_list[i] == "C":
            count += 1
            isC = i + 1
    if count != 1:
        print("WA")
    else:
        del s_list1[isC]
        Str = "".join(s_list1)
        if Str.islower():
            print("AC")
        else:
            print("WA")
else:
    print("WA")

Buggy python submission (verdict: Runtime Error):
s_list = list(input())
s_list1 = s_list

if s_list[0] == "A":
    del s_list[:2], s_list[-1]
    Str = "".join(s_list)
    if Str.count("C") != 1:
        print("WA")
    else:
        Str = "".join(s_list1)
        Str = Str.replace("C", "")
        if Str1.islower():
            print("AC")
        else:
            print("WA")
else:
    print("WA")

Fixed submission:
s_list = list(input())
s_list1 = s_list[1:]
count = 0

if s_list[0] == "A":
    del s_list[:2], s_list[-1]
    for i in range(len(s_list)):
        if s_list[i] == "C":
            count += 1
            isC = i + 1
    if count != 1:
        print("WA")
    else:
        del s_list1[isC]
        Str = "".join(s_list1)
        if Str.islower():
            print("AC")
        else:
            print("WA")
else:
    print("WA")
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort()
b.sort()
c.sort()
cnt = 0
for i in range(n):
    for j in range(bisect.bisect_right(b, a[i]), n):
        cnt += n - bisect.bisect_right(c, b[j])

print(cnt)

Fixed submission:
import bisect
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort()
b.sort()
c.sort()
cnt = 0
for i in range(n):
    cnt += bisect.bisect_left(a, b[i]) * (n - bisect.bisect(c, b[i]))

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

import math

def num_cuts(A, ml):
	if ml == 0:
		while True:
			continue
			
	ret = 0
	for a in A:
		ret += (math.ceil(a / ml) - 1)
	return ret

def ok(A, ml):
	return num_cuts(A, ml) <= K

def ans(A, K):

	low = 0.5
	high = max(A)+1

	assert(not(ok(A, low)))
	assert(ok(A, high))

	while (high - low) > 0.1:
		mid = (low + high) / 2
		if ok(A, mid):
			high = mid
		else:
			low = mid

	low = max(1, math.floor(low) - 5)

	for i in range(100):
		p = low + i/3
		q = low + (i+1) / 3

		if not(ok(A, p)) and ok(A, q):
			return math.ceil(q)


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

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

print(ans(A, K))

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

import math

def num_cuts(A, ml):
	ret = 0
	for a in A:
		ret += (math.ceil(a / ml) - 1)
	return ret

def ok(A, ml):
	return num_cuts(A, ml) <= K

def ans(A, K):

	low = min(A) / (K+5)
	high = max(A)+1

	assert(not(ok(A, low)))
	assert(ok(A, high))

	while (high - low) > 0.1:
		mid = (low + high) / 2
		if ok(A, mid):
			high = mid
		else:
			low = mid

	low = max(1, math.floor(low) - 5)

	for i in range(100):
		p = low + i/2
		if ok(A, p):
			return math.ceil(p)

	assert(False)


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

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

print(ans(A, K))

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

import math

def num_cuts(A, ml):
	ret = 0
	for a in A:
		ret += (math.ceil(a / ml) - 1)
	return ret

def ok(A, ml):
	return num_cuts(A, ml) <= K

def ans(A, K):

	low = 0.5
	high = max(A)+1

	assert(not(ok(A, low)))
	assert(ok(A, high))

	while (high - low) > 0.1:
		mid = (low + high) / 2
		if ok(A, mid):
			high = mid
		else:
			low = mid

	low = max(1, math.floor(low) - 5)

	for i in range(100):
		p = low + i/3
		q = low + (i+1) / 3

		if not(ok(A, p)) and ok(A, q):
			return math.ceil(q)


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

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

print(ans(A, K))

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

import math

def num_cuts(A, ml):
	ret = 0
	for a in A:
		ret += (math.ceil(a / ml) - 1)
	return ret

def ok(A, ml):
	return num_cuts(A, ml) <= K

def ans(A, K):

	low = min(A) / (K+5)
	high = max(A)+1

	assert(not(ok(A, low)))
	assert(ok(A, high))

	while (high - low) > 0.1:
		mid = (low + high) / 2
		if ok(A, mid):
			high = mid
		else:
			low = mid

	low = max(1, math.floor(low) - 5)

	for i in range(100):
		p = low + i/2
		if ok(A, p):
			return math.ceil(p)

	assert(False)


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

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

print(ans(A, K))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from functools import reduce
from operator import add


def _i(): return int(sys.stdin.readline().strip())


def _ia(): return map(int, sys.stdin.readline().strip().split())


def gcd(a, b):
    if a < b:
        a, b = b, a
    r = a % b
    if r == 0:
        return b
    else:
        return gcd(b, r)


def main():
    n = _i()
    a = list(sorted(_ia()))
    r = a[0]
    for ai in a[1:]:
        r = gcd(r, ai)
        if r == 1:
            break
    else:
        return "not coprime"

    N = 10 ** 6 + 1
    f = [False] * N
    p = []
    k = {ai: [] for ai in a}
    for i in range(2, N):
        if f[i]:
            continue
        p.append(i)
        if k.get(i) is not None:
            k[i].append(i)
        for j in range(2*i, N, i):
            f[j] = True
            if k.get(j) is not None:
                k[j].append(i)

    ls = reduce(add, k.values(), [])
    if len(ls) != len(set(ls)):
        return "setwise coprime"
    else:
        return "pairwise coprime"


if __name__ == "__main__":
    print(main())


Fixed submission:
import sys
from functools import reduce
from operator import add


def _i(): return int(sys.stdin.readline().strip())


def _ia(): return map(int, sys.stdin.readline().strip().split())


def gcd(a, b):
    if a < b:
        a, b = b, a
    r = a % b
    if r == 0:
        return b
    else:
        return gcd(b, r)


def main():
    n = _i()
    a = list(sorted(_ia()))
    r = a[0]
    for ai in a[1:]:
        r = gcd(r, ai)
        if r == 1:
            break
    else:
        return "not coprime"

    N = 10 ** 6 + 1
    f = [False] * N
    p = []
    k = {ai: 1 for ai in a}
    for i in range(2, N):
        if f[i]:
            continue
        p.append(i)

        tmp = 0
        if k.get(i) is not None:
            tmp += 1
        for j in range(2*i, N, i):
            f[j] = True
            if k.get(j) is not None:
                tmp += 1
                if tmp > 1:
                    return "setwise coprime"
    else:
        return "pairwise coprime"


if __name__ == "__main__":
    print(main())
Buggy python submission (verdict: Time Limit Exceeded):
import sys


def _s(): return sys.stdin.readline().strip()


def _ia(): return map(int, sys.stdin.readline().strip().split())


def walk(s, w1, h1, x, y, cur, v):
    if s[y][x] is not None:
        return
    s[y][x] = cur
    for hi in range(max(0, y - 2), min(h1, y + 2) + 1):
        for wi in range(max(0, x - 2), min(w1, x + 2) + 1):
            v[hi][wi] = True

    if x > 0:
        walk(s, w1, h1, x-1, y, cur, v)
    if x < w1:
        walk(s, w1, h1, x+1, y, cur, v)
    if y > 0:
        walk(s, w1, h1, x, y-1, cur, v)
    if y < h1:
        walk(s, w1, h1, x, y+1, cur, v)


def main():
    h, w = _ia()
    sh, sw = map(lambda x: x-1, _ia())
    gh, gw = map(lambda x: x-1, _ia())
    s = [[0]*w for _ in range(h)]
    for hi in range(h):
        for wi, c in enumerate(_s()):
            if c == '.':
                s[hi][wi] = None
            else:
                s[hi][wi] = -1

    v = [[False]*w for _ in range(h)]
    p = [(sw, sh)]
    c = 0
    h1, w1 = h-1, w-1
    while len(p) > 0:
        for pi in p:
            walk(s, w1, h1, *pi, c, v)
        p = []
        for j, sv in enumerate(zip(s, v)):
            sj, vj = sv
            for i, svj in enumerate(zip(sj, vj)):
                sij, vij = svj
                if sij is not None or (not vij):
                    continue
                p.append((i, j))
        c += 1
    ans = s[gh][gw]
    return ans if ans is not None else -1


if __name__ == "__main__":
    print(main())


Fixed submission:
import sys


def _s(): return sys.stdin.readline().strip()


def _ia(): return map(int, sys.stdin.readline().strip().split())


def walk(s, w1, h1, x, y, cur, v1, v2):
    if s[y][x] is not None:
        return
    s[y][x] = cur
    v1.add((x, y))
    for hi in range(max(0, y - 2), min(h1, y + 2) + 1):
        for wi in range(max(0, x - 2), min(w1, x + 2) + 1):
            if s[hi][wi] is None:
                v2.add((wi, hi))

    if x > 0:
        walk(s, w1, h1, x-1, y, cur, v1, v2)
    if x < w1:
        walk(s, w1, h1, x+1, y, cur, v1, v2)
    if y > 0:
        walk(s, w1, h1, x, y-1, cur, v1, v2)
    if y < h1:
        walk(s, w1, h1, x, y+1, cur, v1, v2)


def main():
    h, w = _ia()
    sh, sw = map(lambda x: x-1, _ia())
    gh, gw = map(lambda x: x-1, _ia())
    s = [[0]*w for _ in range(h)]
    for hi in range(h):
        for wi, c in enumerate(_s()):
            if c == '.':
                s[hi][wi] = None
            else:
                s[hi][wi] = -1

    p = [(sw, sh)]
    c = 0
    h1, w1 = h-1, w-1
    while len(p) > 0:
        v1 = set()
        v2 = set()
        for pi in p:
            walk(s, w1, h1, *pi, c, v1, v2)
        p = v2 - v1
        c += 1
    ans = s[gh][gw]
    return ans if ans is not None else -1


if __name__ == "__main__":
    print(main())
Buggy python submission (verdict: Runtime Error):
import sys


def _ia(): return map(int, sys.stdin.readline().strip().split())


def calc(arr, k):
    s = sum(arr)
    n = len(arr)
    flag = s > 0 and k > n

    kp = k % n if flag else k
    l = min(kp, n)

    cm = max(arr) if s <= 0 else 0
    for i in range(n):
        cn = 0
        for ki in range(i, i+l):
            cn += arr[ki % n]
            cm = max(cn, cm)

    if flag:
        return s * (k//n) + cm
    else:
        return cm


def main():
    n, k = _ia()
    p = list(map(lambda x: x-1, _ia()))
    c = list(_ia())

    f = [False] * n
    g = []
    for idx in range(n):
        if f[idx]:
            continue

        nxt = idx
        tmp = [c[nxt]]
        f[nxt] = True

        for _ in range(n):
            nxt = p[nxt]
            if nxt == idx:
                break
            tmp.append(c[nxt])
            f[nxt] = True

        g.append(tmp)

    return calc(g[1], k)

    # return max(calc(gi, k) for gi in g)


if __name__ == "__main__":
    print(main())


Fixed submission:
import sys


def _ia(): return map(int, sys.stdin.readline().strip().split())


def calc(arr, k):
    s = sum(arr)
    n = len(arr)
    kp = k % n if s > 0 else k
    if kp == 0:
        kp = n

    ll = min(kp, n)
    cm = max(arr)
    for i in range(n):
        cn = 0
        for ki in range(i, i+ll):
            cn += arr[ki % n]
            cm = max(cn, cm)

    if s > 0:
        return s * ((k-1)//n) + cm
    else:
        return cm


def main():
    n, k = _ia()
    p = list(map(lambda x: x-1, _ia()))
    c = list(_ia())

    f = [False] * n
    g = []
    for idx in range(n):
        if f[idx]:
            continue

        nxt = idx
        tmp = [c[nxt]]
        f[nxt] = True

        for _ in range(n):
            nxt = p[nxt]
            if nxt == idx:
                break
            tmp.append(c[nxt])
            f[nxt] = True

        g.append(tmp)

    return max(calc(gi, k) for gi in g)


if __name__ == "__main__":
    print(main())
Buggy python submission (verdict: Runtime Error):
import sys


def _s(): return sys.stdin.readline().strip()


def _i(): return int(sys.stdin.readline().strip())


def flip(c):
    return "1" if c == "0" else "0"


def main():
    n = _i()
    s = _s()

    lst = [0] * (n+1)
    lst[0] = 0
    for i in range(1, n+1):
        t = i % bin(i)[2:].count("1")
        lst[i] = 1 + lst[t]

    for i in range(n):
        m = s[:i] + flip(s[i]) + s[i+1:]
        t = int(m, 2) % m.count("1")
        print(lst[t] + 1)


if __name__ == "__main__":
    main()


Fixed submission:
import sys


def _s(): return sys.stdin.readline().strip()


def _i(): return int(sys.stdin.readline().strip())


def main():
    n = _i()
    s = _s()
    m = s.count("1")
    arr = list(range(max(1, m-1), m+2))
    d1 = {}
    for ai in arr:
        d1[ai] = [1 % ai]
        for i in range(n-1):
            d1[ai].append((2*d1[ai][-1]) % ai)

    d2 = {ai: 0 for ai in arr}
    for ai in arr:
        for i, c in enumerate(reversed(s)):
            if c == "1":
                d2[ai] = (d2[ai] + d1[ai][i]) % ai

    lst = [0] * (n+1)
    for i in range(1, n+1):
        t = i % bin(i)[2:].count("1")
        lst[i] = 1 + lst[t]

    i = n
    for c in s:
        i -= 1
        if c == "1":
            m1 = m - 1
            if m1 == 0:
                print(0)
                continue
            else:
                t = (d2[m1] - d1[m1][i]) % m1
        else:
            m1 = m + 1
            t = (d2[m1] + d1[m1][i]) % m1
        print(lst[t] + 1)


if __name__ == "__main__":
    main()