Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L = sorted(map(int, input().split()))
ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        for k in range(j + 1, N):
            if L[k] < L[i] + L[j]:
                ans += 1
print(ans)


Fixed submission:
import bisect

N = int(input())
L = sorted(map(int, input().split()))
ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        k = bisect.bisect_left(L, L[i] + L[j])
        if k > j:
            ans += k - j - 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations

N = int(input())
L = list(map(int, input().split()))
ans = 0
for l in combinations(L, 3):
    if max(l) < sum(l) - max(l):
        ans += 1
print(ans)


Fixed submission:
import bisect

N = int(input())
L = sorted(map(int, input().split()))
ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        k = bisect.bisect_left(L, L[i] + L[j])
        if k > j:
            ans += k - j - 1
print(ans)
Buggy python submission (verdict: Runtime Error):
def input_li():
    return list(map(int, input().split()))


def input_int():
    return int(input())


def prime_factorization(n):
    table = []
    for x in range(2, int(n ** 0.5) + 1):
        while n % x == 0:
            table.append(x)
            n //= x
    if n > 1:
        table.append(n)
    return table


A, B = input_li()
A_LI = [x[0] for x in prime_factorization(A)]
B_LI = [x[0] for x in prime_factorization(B)]
print(len(set(A_LI) & set(B_LI)) + 1)


Fixed submission:
def input_li():
    return list(map(int, input().split()))


def input_int():
    return int(input())


def prime_factorization(n):
    table = []
    for x in range(2, int(n ** 0.5) + 1):
        while n % x == 0:
            table.append(x)
            n //= x
    if n > 1:
        table.append(n)
    return table


A, B = input_li()
A_SET = set(prime_factorization(A))
B_SET = set(prime_factorization(B))
print(len((A_SET) & set(B_SET)) + 1)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
a_list = sorted(map(int, input().split()))
for _ in range(M):
    a_list[-1] //= 2
    a_list.sort()
print(sum(a_list))


Fixed submission:
import heapq

N, M = map(int, input().split())
a_list = list(map(lambda x: int(x) * (-1), input().split()))
heapq.heapify(a_list)
for _ in range(M):
    min_num = heapq.heappop(a_list)
    heapq.heappush(a_list, (-1) * (-min_num // 2))
print(-sum(a_list))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
print(sum(range(N)))

Fixed submission:
N = int(input())
print(N * (N-1) // 2)
Buggy python submission (verdict: Time Limit Exceeded):
# TODO: WAなので修正する
from math import factorial
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

n = int(input())
li = []
for i in range(n):
    s = input()
    s = "".join(sorted(s))
    li.append(s)

li.sort()
index = 0
anagram_cnt_sum = 0
while(index < n):
    anagram_cnt = li.count(li[index])
    if anagram_cnt > 1:
        anagram_cnt_sum += cmb(anagram_cnt, 2)
    index += anagram_cnt
print(anagram_cnt_sum)


Fixed submission:
N = int(input())
d = {}
ans = 0
for _ in range(N):
    s = str(sorted(input()))
    if s not in d.keys():
        d[s] = 0
    else:
        d[s] += 1
        ans += d[s]
print(ans)
Buggy python submission (verdict: Runtime Error):
A, B = map(int, input().split())
sum_num = 0

for i in range(2):
    if A >= B:
        sum_num = A
        A -= 1
    else:
        sum_num = B
        B -= 0

print(sum_num):


Fixed submission:
A, B = map(int, input().split(' '))
sum_num = 0

for i in range(2):
    if A >= B:
        sum_num += A
        A -= 1
    else:
        sum_num += B
        B -= 1

print(sum_num)
Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
S = input()
for _ in range(Q):
    l, r = map(int, input().split())
    print(S[l-1:r].count("AC"))


Fixed submission:
N, Q = map(int, input().split())
S = input()
ac = [0] * (N + 1)
ans = []
for i in range(N):
    ac[i + 1] = ac[i] + (1 if S[i:i+2] == "AC" else 0)
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(ac[r - 1] - ac[l - 1])
for i in range(Q):
    print(ans[i])
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
ans = 0
while "BW" in S:
    S = S.replace("BW", "WB", 1)
    ans += 1

print(ans)


Fixed submission:
S = input()
b_cnt = 0
ans = 0
for c in S:
    if c == "B":
        b_cnt += 1
    else:
        ans += b_cnt

print(ans)
Buggy python submission (verdict: Runtime Error):
S = input()
K = int(input())
if len(S) > K and S[:K].count(1) == K:
    print(1)
else:
    for c in S:
        if c != '1':
            print(c)
            break


Fixed submission:
S = input()
K = int(input())
if len(S) >= K and S[:K].count("1") == K:
    print(1)
else:
    for c in S:
        if c != "1":
            print(c)
            break
Buggy python submission (verdict: Runtime Error):
D, N = map(int, input().split())
li = [i * 100 ** D for i in range(100)]
print(li[N])

Fixed submission:
D, N = map(int, input().split())
li = []
cnt = 1
while len(li) < N:
    if cnt % 100 != 0:
        li.append(cnt * 100 ** D)
    cnt += 1

print(li[-1])

Buggy python submission (verdict: Runtime Error):
D, N = map(int, input().split())
li = [i * 100 ** D for i in range(1, N + 1)]
print(li[N])


Fixed submission:
D, N = map(int, input().split())
li = []
cnt = 1
while len(li) < N:
    if cnt % 100 != 0:
        li.append(cnt * 100 ** D)
    cnt += 1

print(li[-1])

Buggy python submission (verdict: Runtime Error):
D, N = map(int, input().split())
li = [i * 100 ** D for i in range(1, N + 1)]
print(li[N])


Fixed submission:
D, N = map(int, input().split())
li = []
cnt = 1
while len(li) < N:
    if cnt % 100 != 0:
        li.append(cnt * 100 ** D)
    cnt += 1

print(li[-1])
Buggy python submission (verdict: Time Limit Exceeded):
def pow(x, n):
    if n == 0:
        return 1
    value = pow(x, int(n / 2))
    value *= value
    if n % 2 == 1:
        value *= x
    return value


x = int(input())
li = [False] * (x + 1)
li[1] = True

for i in range(x):
    for j in range(2, x):
        idx = pow(i, j)
        if idx < x + 1:
            li[idx] = True

for i in reversed(range(x + 1)):
    if li[i]:
        print(i)
        break


Fixed submission:
x = int(input())
li = [False] * (x + 1)
li[1] = True

for i in range(x):
    for j in range(2, x):
        if i ** j > x:
            break
        li[i ** j] = True

for i in reversed(range(x + 1)):
    if li[i]:
        print(i)
        break

Buggy python submission (verdict: Time Limit Exceeded):
x = int(input())
li = [False] * (x + 1)
li[1] = True

for i in range(x):
    for j in range(2, x):
        idx = i ** j
        if idx < x + 1:
            li[idx] = True

for i in reversed(range(x + 1)):
    if li[i]:
        print(i)
        break


Fixed submission:
x = int(input())
li = [False] * (x + 1)
li[1] = True

for i in range(x):
    for j in range(2, x):
        if i ** j > x:
            break
        li[i ** j] = True

for i in reversed(range(x + 1)):
    if li[i]:
        print(i)
        break

Buggy python submission (verdict: Time Limit Exceeded):
x = int(input())
li = [False] * (x + 1)
li[1] = True

for i in range(x):
    for j in range(2, x):
        if i ** j < x + 1:
            li[i ** j] = True

for i in reversed(range(x + 1)):
    if li[i]:
        print(i)
        break


Fixed submission:
x = int(input())
li = [False] * (x + 1)
li[1] = True

for i in range(x):
    for j in range(2, x):
        if i ** j > x:
            break
        li[i ** j] = True

for i in reversed(range(x + 1)):
    if li[i]:
        print(i)
        break
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
XS = list(map(int, input().split()))
for i in range(N):
    xs_ = sorted(XS[:i] + XS[i+1:])
    print(xs_[(N + 1) // 2 - 1])


Fixed submission:
N = int(input())
XS = list(map(int, input().split()))
mid_low = sorted(XS)[len(XS) // 2 - 1]
mid_high = sorted(XS)[len(XS) // 2]
for x in XS:
    if x <= mid_low:
        print(mid_high)
    else:
        print(mid_low)
Buggy python submission (verdict: Time Limit Exceeded):
A, B, K = map(int, input().split())
for num in range(A, B + 1):
    if num < A + K or num > B - K:
        print(num)


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

x = b - a
if x < 2 * k:
    for i in range(a, b + 1):
        print(i)
else:
    for i in range(a, a + k):
        print(i)

    for i in range(b - k + 1, b + 1):
        print(i)

Buggy python submission (verdict: Time Limit Exceeded):
A, B, K = map(int, input().split())
for num in range(A, B + 1):
    if num < A + K or num > B - K:
        print(num)


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

x = b - a
if x < 2 * k:
    for i in range(a, b + 1):
        print(i)
else:
    for i in range(a, a + k):
        print(i)

    for i in range(b - k + 1, b + 1):
        print(i)

Buggy python submission (verdict: Time Limit Exceeded):
A, B, K = map(int, input().split())
ans = list()
for num in range(A, B + 1):
    if num < A + K or num > B - K:
        print(num)


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

x = b - a
if x < 2 * k:
    for i in range(a, b + 1):
        print(i)
else:
    for i in range(a, a + k):
        print(i)

    for i in range(b - k + 1, b + 1):
        print(i)

Buggy python submission (verdict: Runtime Error):
A, B, K = map(int, input().split())
ans = list(range(A, B + 1))
for num in ans:
    if num < min(ans) + K or num > max(ans) - K:
        print(num)


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

x = b - a
if x < 2 * k:
    for i in range(a, b + 1):
        print(i)
else:
    for i in range(a, a + k):
        print(i)

    for i in range(b - k + 1, b + 1):
        print(i)
Buggy python submission (verdict: Runtime Error):
A, B, C = map(int, input().split())
diff = max(A, B, C) * 3 - sum(A, B, C)
if diff % 2 == 0:
    print(diff // 2)
else:
    print(diff // 2 + 2)


Fixed submission:
A, B, C = map(int, input().split())
diff = max(A, B, C) * 3 - (A + B + C)
if diff % 2 == 0:
    print(diff // 2)
else:
    print(diff // 2 + 2)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations

N = int(input())
s_li = []
for _ in range(N):
    s = input()
    if s[0] in "MARCH":
        s_li.append(s)
s_set = set(s_li)
# print(len(list(combinations(s_set, 3))))
ans = 0
for c in combinations(s_set, 3):
    initial = []
    for name in c:
        if name[0] in initial:
            break
        initial.append(name[0])
    else:
        ans += 1
print(ans)


Fixed submission:
N = int(input())
cnt_li = [0, 0, 0, 0, 0]
comb = [
    [0, 1, 2],
    [0, 1, 3],
    [0, 1, 4],
    [0, 2, 3],
    [0, 2, 4],
    [0, 3, 4],
    [1, 2, 3],
    [1, 2, 4],
    [1, 3, 4],
    [2, 3, 4],
]
for _ in range(N):
    s = input()
    if s[0] == 'M':
        cnt_li[0] += 1
    if s[0] == 'A':
        cnt_li[1] += 1
    if s[0] == 'R':
        cnt_li[2] += 1
    if s[0] == 'C':
        cnt_li[3] += 1
    if s[0] == 'H':
        cnt_li[4] += 1
ans = 0
for i in range(len(comb)):
    one, two, three = comb[i]
    mid = cnt_li[one] * cnt_li[two] * cnt_li[three]
    ans += mid
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A_LI = sorted(map(int, input().split()))
A_SET = set(A_LI)
ans = 0
for a in A_SET:
    cnt = A_LI.count(a)
    if cnt < a:
        ans += cnt
    else:
        ans += cnt - a
print(ans)


Fixed submission:
N = int(input())
A_LI = sorted(map(int, input().split()))
a_dict = {}
ans = 0
pre = None
for a in A_LI:
    if a not in a_dict:
        if pre in a_dict:
            # 出揃った値について取り除く個数を求める
            if a_dict[pre] < pre:
                ans += a_dict[pre]
            else:
                ans += a_dict[pre] - pre
        pre = a
        a_dict[a] = 1
    else:
        a_dict[a] += 1
# 最後の値について取り除く個数を求める
if a_dict[pre] < pre:
    ans += a_dict[pre]
else:
    ans += a_dict[pre] - pre
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

N, K = map(int, input().split())
counter = Counter(list(map(int, input().split())))
ans = 0
if len(counter.keys()) > K:
    for i in range(len(counter.keys()) - K):
        ans += counter.most_common()[0 - i - 1][1]

print(ans)


Fixed submission:
import collections

N, K = map(int, input().split())
arr = list(map(int, input().split()))
ans = 0
cnt = collections.defaultdict(int)
for num in arr:
    cnt[num] += 1

vals = sorted(cnt.values())

if len(cnt) > K:
    for i in range(len(cnt) - K):
        ans += vals[i]

print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import Counter

S = input()
counter = Counter(S)
if len(counter) == 1:
    k = counter.keys()[0]
    if counter[k] > 1:
        print('NO')
    else:
        print('YES')
elif len(counter) == 2:
    print('NO')
else:
    # 通らない気がする
    print('YES')


Fixed submission:
from collections import Counter

S = input()
counter = Counter(S)
if len(counter) == 1:
    k = list(counter.keys())[0]
    if counter[k] > 1:
        print('NO')
    else:
        print('YES')
elif len(counter) == 2:
    # a, b → OK
    # a, a, b, b → NG
    for k in counter.keys():
        if counter[k] != 1:
            print('NO')
            exit()
    print('YES')
else:
    # abcabcb → bacbacb OK
    # abbccc → cabc これのどこにcを追加してもNG
    # abcba → abcab OK
    # aabc → abca OK
    min_v = 10 ** 5
    max_v = 0
    for k in counter.keys():
        min_v = min(min_v, counter[k])
        max_v = max(max_v, counter[k])
    if max_v - min_v > 1:
        print('NO')
    else:
        print('YES')
Buggy python submission (verdict: Runtime Error):
import math


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


N = int(input())
t_li = []
for _ in range(N):
    t_li.append(int(input()))
ans = lcm(t_li[0], t_li[1])
for i in range(2, N):
    ans = lcm(ans, t_li[i])
print(ans)


Fixed submission:
import math


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


N = int(input())
t_li = []
for _ in range(N):
    t_li.append(int(input()))
if N > 1:
    ans = lcm(t_li[0], t_li[1])
    for i in range(2, N):
        ans = lcm(ans, t_li[i])
else:
    ans = t_li[0]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
teiki_1 = []
teiki_N = []
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1 or b == 1:
        teiki_1.append(a if a != 1 else b)
    if a == N or b == N:
        teiki_N.append(a if a != N else b)
for num in sorted(teiki_1):
    if num in sorted(teiki_N):
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')


Fixed submission:
N, M = map(int, input().split())
teiki_1 = []
teiki_N = []
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1 or b == 1:
        teiki_1.append(a if a != 1 else b)
    if a == N or b == N:
        teiki_N.append(a if a != N else b)
if len(set(teiki_1) & set(teiki_N)) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
teiki_1 = []
teiki_N = []
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1 or b == 1:
        teiki_1.append(a if a != 1 else b)
    if a == N or b == N:
        teiki_N.append(a if a != N else b)
for num in teiki_1:
    if num in teiki_N:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')


Fixed submission:
N, M = map(int, input().split())
teiki_1 = []
teiki_N = []
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1 or b == 1:
        teiki_1.append(a if a != 1 else b)
    if a == N or b == N:
        teiki_N.append(a if a != N else b)
if len(set(teiki_1) & set(teiki_N)) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a_li = list(map(int, input().split()))
# y = X - x
# |x - y| = |x - (X - x)|
#         = |-X + 2x|
total = sum(a_li)
ans = 10 ** 18
for i in range(1, N):
    ans = min(ans, abs(sum(a_li[:i]) * 2 - total))
print(ans)


Fixed submission:
from itertools import accumulate

N = int(input())
a_li = list(map(int, input().split()))
# y = X - x
# |x - y| = |x - (X - x)|
#         = |-X + 2x|
total = sum(a_li)
acc = list(accumulate(a_li))
ans = 10 ** 18
for i in range(N - 1):
    ans = min(ans, abs(acc[i] * 2 - total))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
X = int(input())
# X > 0 なのでマイナス方向にジャンプする選択肢は選ばない
cnt = 0
while X != 0:
    if X != cnt + 1:
        X -= cnt
    cnt += 1
print(cnt - 1)


Fixed submission:
X = int(input())
acc = 0
# X > 0 なのでマイナス方向にジャンプする選択肢は選ばない
for i in range(X + 1):
    acc += i
    if X <= acc:
        ans = i
        break
print(i)
Buggy python submission (verdict: Time Limit Exceeded):
INF = 1000000000 + 7
N = int(input())
ans = 1
for i in range(1, N + 1):
    ans *= i

print(ans % INF)


Fixed submission:
INF = 1000000000 + 7
N = int(input())
ans = 1
for i in range(1, N + 1):
    ans = ans * i % INF

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
INF = 1000000000 + 7
N = int(input())
ans = 1
for i in range(1, N + 1):
    ans *= i

print(ans % INF)


Fixed submission:
INF = 1000000000 + 7
N = int(input())
ans = 1
for i in range(1, N + 1):
    ans = ans * i % INF

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

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

N, M = map(int, input().split())
S = input()
T = input()
L = lcm(N , M)
x = [""] * L
for i in range(N):
    idx = i * (L // N)
    # x[idx] = S[i]
for i in range(M):
    idx = i * (L // M)
    if x[idx] != "" and x[idx] != T[i]:
        print(-1)
        exit()
print(L)


Fixed submission:
import math

N = int(input())
a_li = []
b_li = []
ans = 0
for _ in range(N):
    a, b = map(int, input().split())
    a_li.append(a)
    b_li.append(b)
for i in reversed(range(N)):
    a, b = a_li[i], b_li[i]
    a += ans
    div = math.ceil(a / b)
    ans += b * div - a
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
H,W,M = map(int,input().split())
Hinx = [0 for _ in range(H+1)]
Winx = [0 for _ in range(W+1)]
isExist = []
for i in range(M):
    h,w = map(int,input().split())
    Hinx[h] += 1
    Winx[w] += 1
    isExist.append((h,w))


HMinx = []
WMinx = []
Hmax = max(Hinx)
Wmax = max(Winx)
ans = Hmax + Wmax

isExist = set(isExist)
for i in range(1,H+1):
    if Hinx[i] == Hmax:
        HMinx.append(i)
for i in range(1,W+1):
    if Winx[i] == Wmax:
        WMinx.append(i)

cross = 0
not_cross = 0

for i in HMinx:
    for j in WMinx:
        if (i,j) in isExist:
            cross += 1
        else:
            not_cross += 1

if not_cross > 0:
    print(ans)
else:
    print(ans - 1)

Fixed submission:
import sys
input = sys.stdin.readline

class SegmentTree():
    def __init__(self, n, init):
        self.n = 2 ** (n - 1).bit_length()
        self.init = init
        self.data = [init] * (2 * self.n)

    def inc(self, k):
        self.data[k + self.n - 1] += 1

    def build(self):
        for k in reversed(range(self.n - 1)):
            self.data[k] = max(self.data[k * 2 + 1], self.data[k * 2 + 2])

    def update(self, k, a):
        k += self.n - 1
        self.data[k] += a

        while k > 0:
            k = (k - 1) // 2
            self.data[k] = max(self.data[k * 2 + 1], self.data[k * 2 + 2])

    def query(self, l, r):
        L = l + self.n
        R = r + self.n
        ret = self.init
        while L < R:
            if R & 1:
                R -= 1
                ret = max(ret, self.data[R - 1])
            if L & 1:
                ret = max(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret



if __name__ == "__main__":
    H, W, M = map(int, input().split())

    Seg = SegmentTree(W + 5, 0)

    Yaxis = dict()

    for _ in range(M):
        h, w = map(int, input().split())
        if h in Yaxis: Yaxis[h].append(w)
        else: Yaxis[h] = [w]
        Seg.inc(w)

    Seg.build()


    ans = 0
    for y in Yaxis:
        for x in Yaxis[y]: Seg.update(x, -1)
        ans = max(ans, len(Yaxis[y]) + Seg.query(0, W + 1))
        for x in Yaxis[y]: Seg.update(x, 1)

    print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
X = input()
tmp = sum(X[i] == '1' for i in range(N))

for_zero = tmp + 1
for_one = tmp - 1
zero_S = 0
one_S = 0


numbers = [-1] * N
counts = [1] * N

if tmp == 1:
    for i in range(N):
        if X[i] == '1':
            counts[i] = 0

# =====================first sweep
tmp_zero = 1
tmp_one = 1
for i in range(N):
    if X[-i-1] == '1':
        one_S += tmp_one
        one_S %= for_one
        zero_S += tmp_zero
        zero_S %= for_zero
    tmp_zero *= 2
    tmp_zero %= for_zero
    tmp_one *= 2
    tmp_one %= for_one


# =====================second sweep
tmp_zero = 1
tmp_one = 1
for i in range(N):
    if X[-i-1] == '1':
        numbers[-i - 1] = (one_S - tmp_one) % for_one
    else:
        numbers[-i - 1] = (zero_S + tmp_zero) % for_zero
    tmp_zero *= 2
    tmp_zero %= for_zero
    tmp_one *= 2
    tmp_one %= for_one


def solution(number):
    loop = 0
    while number != 0:
        popcount = 0
        for i in range(30):
            if (1 << i) & number:
                popcount += 1
        number %= popcount
        loop += 1
    return loop

for i in range(N):
    counts[i] += solution(numbers[i])

print(*counts, sep='\n')

Fixed submission:
N = int(input())
X = input()
tmp = sum(X[i] == '1' for i in range(N))

for_zero = tmp + 1
for_one = tmp - 1
zero_S = 0
one_S = 0


numbers = [0] * N
counts = [1] * N

if tmp == 1:
    for i in range(N):
        if X[i] == '1':
            counts[i] = 0
    # =====================first sweep
    tmp_zero = 1
    for i in range(N):
        if X[-i - 1] == '1':
            zero_S += tmp_zero
            zero_S %= for_zero
        tmp_zero *= 2
        tmp_zero %= for_zero

    # =====================second sweep
    tmp_zero = 1
    for i in range(N):
        if X[-i - 1] == '1':
            pass
        else:
            numbers[-i - 1] = (zero_S + tmp_zero) % for_zero
        tmp_zero *= 2
        tmp_zero %= for_zero

else:
    # =====================first sweep
    tmp_zero = 1
    tmp_one = 1
    for i in range(N):
        if X[-i - 1] == '1':
            one_S += tmp_one
            one_S %= for_one
            zero_S += tmp_zero
            zero_S %= for_zero
        tmp_zero *= 2
        tmp_zero %= for_zero
        tmp_one *= 2
        tmp_one %= for_one

    # =====================second sweep
    tmp_zero = 1
    tmp_one = 1
    for i in range(N):
        if X[-i - 1] == '1':
            numbers[-i - 1] = (one_S - tmp_one) % for_one
        else:
            numbers[-i - 1] = (zero_S + tmp_zero) % for_zero
        tmp_zero *= 2
        tmp_zero %= for_zero
        tmp_one *= 2
        tmp_one %= for_one




def solution(number):
    loop = 0
    while number != 0:
        popcount = 0
        for i in range(30):
            if (1 << i) & number:
                popcount += 1
        number %= popcount
        loop += 1
    return loop

for i in range(N):
    counts[i] += solution(numbers[i])

print(*counts, sep='\n')