Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys, math

n = int(sys.stdin.readline().strip())
s = sys.stdin.readline().strip()
res = 0

r = []
g = []
b = []
for i, c in enumerate(s):
    if c == "R":
        r.append(i)
    if c == "G":
        g.append(i)
    if c == "B":
        b.append(i)


res = len(r) * len(b) * len(g)

for i in r:
    for j in g:
        for k in b:
            x,y,z = sorted([i,j,k])
            if y-x ==z-y:
                res -= 1
print(res)

Fixed submission:
import sys, math

n = int(sys.stdin.readline().strip())
s = sys.stdin.readline().strip()
res = 0

r = []
g = []
b = []
for i, c in enumerate(s):
    if c == "R":
        r.append(i)
    if c == "G":
        g.append(i)
    if c == "B":
        b.append(i)


res = len(r) * len(b) * len(g)

def bin_find(tar):
    left = 0
    right = len(b)
    while left < right:
        mid = (left+right) // 2
        if b[mid] < tar:
            left = mid+1
        elif b[mid] > tar:
            right = mid
        else:
            return mid
    return -1

for i in r:
    for j in g:
        diff = i - j
        if diff < 0:
            diff = -diff
        if diff % 2 == 0:
            target = diff // 2 + min(i,j)
            if target < n and s[target] == 'B':
                res -= 1
        target = min(i,j) - diff
        if target >= 0 and s[target] == 'B':
            res -= 1
        target = max(i,j) + diff
        if target < n and s[target] == "B":
            res -= 1

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
import sys, math

n = int(sys.stdin.readline().strip())
s = sys.stdin.readline().strip()
res = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        if s[j] == s[i]:
            continue
        for k in range(j+1, n):
            if s[k] == s[i] or s[k] == s[j] or j-i == k-j:
                continue
            res += 1
print(res)

Fixed submission:
import sys, math

n = int(sys.stdin.readline().strip())
s = sys.stdin.readline().strip()
res = 0

r = []
g = []
b = []
for i, c in enumerate(s):
    if c == "R":
        r.append(i)
    if c == "G":
        g.append(i)
    if c == "B":
        b.append(i)


res = len(r) * len(b) * len(g)

def bin_find(tar):
    left = 0
    right = len(b)
    while left < right:
        mid = (left+right) // 2
        if b[mid] < tar:
            left = mid+1
        elif b[mid] > tar:
            right = mid
        else:
            return mid
    return -1

for i in r:
    for j in g:
        diff = i - j
        if diff < 0:
            diff = -diff
        if diff % 2 == 0:
            target = diff // 2 + min(i,j)
            if target < n and s[target] == 'B':
                res -= 1
        target = min(i,j) - diff
        if target >= 0 and s[target] == 'B':
            res -= 1
        target = max(i,j) + diff
        if target < n and s[target] == "B":
            res -= 1

print(res)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

n = int(sys.stdin.readline().strip())
nums = list(map(int, sys.stdin.readline().strip().split()))

d = dict()
for one in nums:
    if one in d:
        d[one] += 1
    else:
        d[one] = 1

def C(a):
    return (a*(a-1)//2 )

res_history = dict()

for one in nums:
    if one in res_history:
        print(res_history[one])
    else:
        d[one] -= 1
        res = 0
        for k,v in d.items():
            if v==2:
                res += 1
            elif v > 2:
                res += C(v)
        print (res)
        d[one] += 1
        res_history[one] = res


Fixed submission:
import sys

n = int(sys.stdin.readline().strip())
nums = list(map(int, sys.stdin.readline().strip().split()))
# appear times
d = dict()
for one in nums:
    if one in d:
        d[one] += 1
    else:
        d[one] = 1

def C(a):
    return (a*(a-1)//2 )

accum = 0
for k, v in d.items():
    accum += C(v)

res_history = dict()

for one in nums:
    if one in res_history:
        print(res_history[one])
    else:
        if d[one] == 1:
            print(accum)
        else:
            res = accum 
            delta = C(d[one]) - C(d[one] - 1)
            res -= delta
            res_history[one] = res
            print(res)

Buggy python submission (verdict: Runtime Error):
import sys

n = int(sys.stdin.readline().strip())
nums = list(map(int, sys.stdin.readline().strip().split()))

d = dict()
for one in nums:
    if one in d:
        d[one] += 1
    else:
        d[one] = 1
history = dict()
history[0] = 1
history[1] = 1
history[2] = 2
def stepMulti(v):
    if v < 1:
        return 1
    if v not in history:
        history[v]  = v * stepMulti(v-1)
    return history[v]

def C(a,b):
    return stepMulti(a) // (stepMulti(a-b) * stepMulti(b))

res_history = dict()

for one in nums:
    if one in res_history:
        print(res_history[one])
    else:
        d[one] -= 1
        res = 0
        for k,v in d.items():
            if v==2:
                res += 1
            elif v > 2:
                res += C(v, 2)
        print (res)
        d[one] += 1
        res_history[one] = res


Fixed submission:
import sys

n = int(sys.stdin.readline().strip())
nums = list(map(int, sys.stdin.readline().strip().split()))
# appear times
d = dict()
for one in nums:
    if one in d:
        d[one] += 1
    else:
        d[one] = 1

def C(a):
    return (a*(a-1)//2 )

accum = 0
for k, v in d.items():
    accum += C(v)

res_history = dict()

for one in nums:
    if one in res_history:
        print(res_history[one])
    else:
        if d[one] == 1:
            print(accum)
        else:
            res = accum 
            delta = C(d[one]) - C(d[one] - 1)
            res -= delta
            res_history[one] = res
            print(res)
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python3
# -*- coding: utf-8 -*-
h, w, m = map(int, input().split())
bom_set = set()
h_dict = {}
w_dict = {}
for i in range(m):
    hh, ww = map(int, input().split())
    bom_set.add(tuple([hh, ww]))
    if hh in h_dict:
        h_dict[hh] += 1
    else:
        h_dict[hh] = 1
    if ww in w_dict:
        w_dict[ww] += 1
    else:
        w_dict[ww] = 1
h_max_count = max(h_dict.values())
w_max_count = max(w_dict.values())
flag = 0
for hh in h_dict:
    if h_dict[hh] < h_max_count:
        continue
    for ww in w_dict:
        if w_dict[ww] < w_max_count:
            continue
        if tuple([hh, ww]) not in bom_set:
            flag = 1
            break
    if flag == 1:
        break
if flag == 1:
    print(h_max_count + w_max_count)
else:
    print(h_max_count + w_max_count - 1)

Fixed submission:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
h, w, m = map(int, input().split())
bom_set = set()
h_dict = {}
w_dict = {}
for i in range(m):
    hh, ww = map(int, input().split())
    bom_set.add(tuple([hh, ww]))
    if hh in h_dict:
        h_dict[hh] += 1
    else:
        h_dict[hh] = 1
    if ww in w_dict:
        w_dict[ww] += 1
    else:
        w_dict[ww] = 1
h_max_count = max(h_dict.values())
w_max_count = max(w_dict.values())
hh_dict = {}
ww_dict = {}
for hh in h_dict:
    if h_dict[hh] == h_max_count:
        hh_dict[hh] = h_max_count
for ww in w_dict:
    if w_dict[ww] == w_max_count:
        ww_dict[ww] = w_max_count
flag = 0
for hh in hh_dict:
    for ww in ww_dict:
        if tuple([hh, ww]) not in bom_set:
            flag = 1
            break
    if flag == 1:
        break
if flag == 1:
    print(h_max_count + w_max_count)
else:
    print(h_max_count + w_max_count - 1)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a_list = list(map(int, input().split()))
a_list.sort(reverse=True)
ans = 0
for i in range(0, n - 1):
    ans += A[(i + 1) // 2]
print(ans)

Fixed submission:
n = int(input())
a_list = list(map(int, input().split()))
a_list.sort(reverse=True)
ans = 0
for i in range(0, n - 1):
    ans += a_list[(i + 1) // 2]
print(ans)
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
a_list = list(map(int, input().split()))
mod = 10**9+7
a_list.sort()
ans = 1
if k % 2 == 1 and a[-1] < 0:
    for i in range(k):
        ans *= a_list[n - 1 - i]
        ans %= mod
else:
    l = 0
    r = -1
    mlt1 = a_list[0] * a_list[1]
    mlt2 = a_list[-2] * a_list[-1]
    for _ in range(0, k // 2):
        if mlt1 >= mlt2:
            ans *= mlt1 % mod
            l += 2
            if l <= n-2:
                mlt1 = a_list[l + 1] * a_list[l]
        else:
            ans *= mlt2 % mod
            r -= 2
            if r >= - n + 1:
                mlt2 = a_list[r - 1] * a_list[r]
        ans %= mod

    if k % 2 == 1:
        ans *= a_list[r]
        ans %= mod
print(ans)

Fixed submission:
n, k = map(int, input().split())
a_list = list(map(int, input().split()))
mod = 10**9+7
a_list.sort()
ans = 1
if k % 2 == 1 and a_list[-1] < 0:
    for i in range(k):
        ans *= a_list[n - 1 - i]
        ans %= mod
else:
    l = 0
    r = -1
    mlt1 = a_list[0] * a_list[1]
    mlt2 = a_list[-2] * a_list[-1]
    count = 0
    while True:
        if count == k:
            break
        elif count == k - 1:
            ans *= a_list[r] % mod
            ans %= mod
            break
        if mlt1 >= mlt2:
            ans *= mlt1 % mod
            l += 2
            count += 2
            if l <= n - 2:
                mlt1 = a_list[l + 1] * a_list[l]
        else:
            ans *= a_list[r] % mod
            r -= 1
            count += 1
            if r >= - n + 1:
                mlt2 = a_list[r - 1] * a_list[r]
        ans %= mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import collections
n = int(input())
a_list = list(map(int, input().split()))
a_dict = dict(collections.Counter(a_list))
sorted_dict = sorted(a_dict.items(), key=lambda x:x[0])
flag_list = [1] * len(sorted_dict)
i = 0
for key, count in sorted_dict:
    if flag_list[i] == 0:
        i += 1
        continue
    if count > 1:
        flag_list[i] = 0
    i += 1
    j = i
    for key1, count1 in sorted_dict[i:]:
        if flag_list[j] == 0:
            j += 1
            continue
        if key1 % key == 0:
            flag_list[j] = 0
        j += 1
print(sum(flag_list))

Fixed submission:
n = int(input())
a_list = list(map(int, input().split()))
a_set = set(a_list)
m = max(a_list)
a_list.sort()
 
pre_a = 0
for a in a_list:
    if a == pre_a:
        a_set.discard(a)
    if a in a_set:
        j = a * 2
        while j <= m:
            a_set.discard(j)
            j += a
    pre_a = a

print(len(a_set))
Buggy python submission (verdict: Runtime Error):
n = int(input())
a_list = np.array(list(map(int, input().split())))
if 0 in a_list:
    print(0)
else:
    ans = 1
    flag = 1
    for i in range(0, n):
        ans *= int(a_list[i])
        if ans > 10 ** 18:
            flag = 0
            break
    if flag == 0:
        print(-1)
    else:
        print(ans)

Fixed submission:
n = int(input())
a_list = list(map(int, input().split()))
if 0 in a_list:
    print(0)
else:
    ans = 1
    flag = 1
    for i in range(0, n):
        ans *= int(a_list[i])
        if ans > 10 ** 18:
            flag = 0
            break
    if flag == 0:
        print(-1)
    else:
        print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
if True:
    n,x,y = map(int, input().split())


else:
    # n=5
    # x=2
    # y=4
    # n=3
    # x=1
    # y=3
    n=7
    x=3
    y=7

# print(n)
# print(x)
# print(y)
#
ret = [0] * (n-1)
for i in range(1, n):
    for j in range(i+1, n+1):
        # print(str(i) + "," + str(j))
        p =[]
        p.append(j - i)
        p.append(abs(i - x) + 1 + abs(j - y))
        p.append(abs(i - y) + 1 + abs(j - x))

        # print(p)
        # print(min(p))
        ret[min(p)-1] += 1

# print(ret)
# print("=======")
for data in ret:
    print(data)

Fixed submission:
n,x,y = map(int, input().split())

ret = [0] * (n-1)
for i in range(1, n):
    for j in range(i+1, n+1):
        p1 = j-i
        p2 = abs(i - x) + 1 + abs(j - y)
        p3 = abs(i - y) + 1 + abs(j - x)
        if p1 > p2:
            p1 = p2
        if p1 > p3:
            p1 = p3
        ret[p1-1] += 1

for data in ret:
    print(data)
Buggy python submission (verdict: Time Limit Exceeded):
x,y,a,b,c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

p.sort()
q.sort()
r.sort()
p.reverse()
q.reverse()
r.reverse()

ret = 0
z = 0
while(x + y > z):
    pattern = 0
    apple = 0
    if x > 0 and len(p) > 0:
        apple = p[0]
        pattern = 1
    if y > 0 and len(q) > 0:
        if apple < q[0]:
            apple = q[0]
            pattern = 2
    if len(r) > 0 and apple < r[0]:
        apple = r[0]
        pattern = 3
    ret += apple
    if pattern == 1:
        x -= 1
        p.pop(0)
    elif pattern == 2:
        y -= 1
        q.pop(0)
    elif pattern == 3:
        z += 1
        r.pop(0)

print(ret)


Fixed submission:
x,y,a,b,c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

p.sort()
q.sort()
r.sort()
p.reverse()
q.reverse()
r.reverse()

ret = 0
z = 0

pidx=0
qidx=0
ridx=0

plen=len(p)
qlen=len(q)
rlen=len(r)
while(x + y > z):
    pattern = 0
    apple = 0
    if x > 0 and pidx < plen:
        apple = p[pidx]
        pattern = 1
    if y > 0 and qidx < qlen:
        if apple < q[qidx]:
            apple = q[qidx]
            pattern = 2
    if ridx < rlen and apple < r[ridx]:
        apple = r[ridx]
        pattern = 3
    ret += apple
    if pattern == 1:
        x -= 1
        pidx += 1
    elif pattern == 2:
        y -= 1
        qidx  += 1
    elif pattern == 3:
        z += 1
        ridx += 1

print(ret)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(i) for i in input().split()]
res = 1
for i in range(N):
    if A[i] >= 0:
        res *= A[i];
    if res > 1e+18:
        res = -1

if res > 1e+18: print("-1")
else          : print(res)

Fixed submission:
N = int(input())
A = [int(i) for i in input().split()]
res = 1
for i in range(N):
    if A[i] == 0:
        res = 0
    if res < 0:
        continue
    res *= A[i];
    if res > 1e+18:
        res = -1

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(i) for i in input().split()]
res = 1
for i in range(N):
    if A[i] >= 0:
        res *= A[i];

if res > 1e+18: print("-1")
else          : print(res)

Fixed submission:
N = int(input())
A = [int(i) for i in input().split()]
res = 1
for i in range(N):
    if A[i] == 0:
        res = 0
    if res < 0:
        continue
    res *= A[i];
    if res > 1e+18:
        res = -1

print(res)
Buggy python submission (verdict: Runtime Error):
p = 998244353
n, k = map(int, input().split())
LRs = [tuple(map(int, input().split())) for _ in range(k)]
A = [0] * (2 * n)
for lj, rj in LRs:
    A[lj] += 1
    A[rj + 1] -= 1
s = 0
for i in range(1, n):
    s = (s + A[i]) % p
    for lj, rj in LRs:
        A[i + lj] += s
        A[i + rj + 1] -= s
print(s)


Fixed submission:
p = 998244353
n, k = map(int, input().split())
LRs = []
for j in range(k):
    lj, rj = map(int, input().split())
    LRs.append((lj, rj))
A = [0] * (n + 1)
i0 = min(lj for lj, rj in LRs)
A[0] = 1
A[i0] = 1
for i in range(i0 + 1, n):
    A[i] = A[i - 1]
    for j in range(k):
        lj, rj = LRs[j]
        if i - lj >= 0:
            A[i] += A[i - lj]
        if i - 1 - rj >= 0:
            A[i] -= A[i - 1 - rj]
        A[i] %= p
print(A[n - 1])

Buggy python submission (verdict: Runtime Error):
p = 998244353
n, k = map(int, input().split())
LRs = []
for j in range(k):
    lj, rj = map(int, input().split())
    LRs.append((lj, rj))
A = [0] * n
i0 = min(lj for lj, rj in LRs)
A[0] = 1
A[i0] = 1
for i in range(i0 + 1, n):
    A[i] = A[i - 1]
    for j in range(k):
        lj, rj = LRs[j]
        if i - lj >= 0:
            A[i] += A[i - lj]
        if i - 1 - rj >= 0:
            A[i] -= A[i - 1 - rj]
        A[i] %= p
print(A[n - 1])


Fixed submission:
p = 998244353
n, k = map(int, input().split())
LRs = []
for j in range(k):
    lj, rj = map(int, input().split())
    LRs.append((lj, rj))
A = [0] * (n + 1)
i0 = min(lj for lj, rj in LRs)
A[0] = 1
A[i0] = 1
for i in range(i0 + 1, n):
    A[i] = A[i - 1]
    for j in range(k):
        lj, rj = LRs[j]
        if i - lj >= 0:
            A[i] += A[i - lj]
        if i - 1 - rj >= 0:
            A[i] -= A[i - 1 - rj]
        A[i] %= p
print(A[n - 1])
Buggy python submission (verdict: Runtime Error):
class UnionFind():
    def __init__(self, n):
        self.n = n
        # 親の名(いない場合はNone)
        self.parent = [None] * n
        # 子の数
        self.count = [0] * n

    def root(self, x):
        # xの根を返す
        if self.parent[x] is None:
            return x
        else:
            return self.root(self.parent[x])

    def union(self, x, y):
        # xとyをまとめる
        x0 = self.root(x)
        y0 = self.root(y)
        if x0 == y0:
            return
        if x0 > y0:
            x0, y0 = y0, x0
        self.parent[y0] = x0
        self.count[x0] += self.count[y0] + 1

    def size(self, x):
        # xの属する木の大きさ
        return self.count[self.root(x)] + 1

    def same(self, x, y):
        return self.root(x) == self.root(y)


n, m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a - 1, b - 1)
maxSize = 0
for i in range(n):
    maxSize = max(maxSize, uf.size(i))
print(maxSize)


Fixed submission:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r))
                         for r in self.roots())


n, m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a - 1, b - 1)
maxSize = 0
for j in range(n):
    maxSize = max(maxSize, uf.size(j))
print(maxSize)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq

h, w = map(int, input().split())
i0, j0 = map(lambda x: int(x) - 1, input().split())
i1, j1 = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(h)]
inf = 10**10
D = [[inf] * w for i in range(h)]
D[i0][j0] = 0
Q = [(0, (i0, j0))]
heapq.heapify(Q)
while Q:
    _, (i, j) = heapq.heappop(Q)
    for di in range(-2, 3):
        for dj in range(-2, 3):
            ii, jj = i + di, j + dj
            if 0 <= ii < h and 0 <= jj < w and S[ii][jj] == ".":
                nex = int(abs(di) + abs(dj) != 1)
                if D[i][j] + nex < D[ii][jj]:
                    D[ii][jj] = D[i][j] + nex
                    heapq.heappush(Q, (D[ii][jj], (ii, jj)))
if D[i1][j1] >= inf:
    print(-1)
else:
    print(D[i1][j1])


Fixed submission:
from collections import deque

h, w = map(int, input().split())
i0, j0 = map(lambda x: int(x) - 1, input().split())
i1, j1 = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(h)]
D = [[-1] * w for i in range(h)]
Q = deque([(i0, j0, 0)])
while Q:
    i, j, cnt = Q.popleft()
    if D[i][j] != -1:
        continue
    D[i][j] = cnt
    for di in range(-2, 3):
        for dj in range(-2, 3):
            if 0 <= i + di < h and 0 <= j + \
                    dj < w and S[i + di][j + dj] == "." and D[i + di][j + dj] == -1:
                if abs(di) + abs(dj) == 1:
                    Q.appendleft((i + di, j + dj, cnt))
                else:
                    Q.append((i + di, j + dj, cnt + 1))
print(D[i1][j1])
Buggy python submission (verdict: Runtime Error):
k = int(input())
a = 7
i = 1
F = [0] * k
while F[a % k] == 0:
    F[a] = 1
    a = ((10 * a) + 7) % k
    i += 1
    if a == 0:
        print(i)
        exit()
print(-1)


Fixed submission:
k = int(input())
a = 7
for i in range(1, k + 1):
    if a % k == 0:
        print(i)
        exit()
    a = (10 * a + 7) % k
print(-1)
Buggy python submission (verdict: Runtime Error):
def popcount(n):
    return bin(n).count("1")


def f(n):
    tmp = n
    count = 0
    while tmp > 0:
        tmp %= popcount(tmp)
        count += 1
    return count


n = int(input())
# f(0)~f(n)までを計算しておく
F = [f(i) for i in range(n + 2)]
x = input()
pcx = x.count("1")
# xをpcx-1,pcx+1で割ったあまりをそれぞれ計算
a, b = 0, 0
if pcx > 0:
    for i in range(n):
        if x[i] == "1":
            a += pow(2, n - i - 1, pcx - 1)
            a %= (pcx - 1)
            b += pow(2, n - i - 1, pcx + 1)
            b %= (pcx + 1)
else:
    for i in range(n):
        print(1)
    exit()
for i in range(n):
    if x[i] == "1":
        print(1 + f((a - pow(2, n - i - 1, pcx - 1)) % (pcx - 1)))
    else:
        print(1 + f((b + pow(2, n - i - 1, pcx + 1)) % (pcx + 1)))


Fixed submission:
def popcount(n):
    return bin(n).count("1")


def f(n):
    tmp = n
    count = 0
    while tmp > 0:
        tmp %= popcount(tmp)
        count += 1
    return count


n = int(input())
# f(0)~f(n)までを計算しておく
F = [f(i) for i in range(n + 2)]
x = input()
pcx = x.count("1")
# xをpcx-1,pcx+1で割ったあまりをそれぞれ計算

a, b = 0, 0
if pcx == 1:
    for i in range(n):
        if x[i] == "1":
            b += pow(2, n - i - 1, pcx + 1)
            b %= (pcx + 1)
    for i in range(n):
        if x[i] == "1":
            print(0)
        else:
            print(1 + f((b + pow(2, n - i - 1, pcx + 1)) % (pcx + 1)))
    exit()

if pcx > 1:
    for i in range(n):
        if x[i] == "1":
            a += pow(2, n - i - 1, pcx - 1)
            a %= (pcx - 1)
            b += pow(2, n - i - 1, pcx + 1)
            b %= (pcx + 1)
else:
    for i in range(n):
        print(1)
    exit()
for i in range(n):
    if x[i] == "1":
        print(1 + f((a - pow(2, n - i - 1, pcx - 1)) % (pcx - 1)))
    else:
        print(1 + f((b + pow(2, n - i - 1, pcx + 1)) % (pcx + 1)))