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

S = list(input())
Q = int(input())
inversion_flag = False
for _ in range(Q):
    query_list = list(input().split())
    if query_list[0] == "1":
        inversion_flag = not inversion_flag
        continue
    C = query_list[2]
    if query_list[1] == "2":
        if inversion_flag:
            S.insert(0, C)
        else:
            S.append(C)
    else:
        if inversion_flag:
            S.append(C)
        else:
            S.insert(0, C)

if inversion_flag:
    print(*S[::-1], sep="")
else:
    print(*S, sep="")


### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
inversion_flag = False
for _ in range(Q):
    query_list = list(input().split())
    if query_list[0] == "1":
        inversion_flag = not inversion_flag
        continue
    C = query_list[2]
    if query_list[1] == "2":
        if inversion_flag:
            S.appendleft(C)
        else:
            S.append(C)
    else:
        if inversion_flag:
            S.append(C)
        else:
            S.appendleft(C)

S = list(S)
if inversion_flag:
    print(*S[::-1], sep="")
else:
    print(*S, sep="")
### BUGGY CODE ###

N,K,*P = map(int,open(0).read().split())
m = [0]*N
E = [((n+1))/2 for n in range(1,1001)]
for i in range(0,N-K+1):
  tmp_sum = 0
  for j in range(K):
    tmp_sum+=E[P[i+j]-1]
  m[i]=tmp_sum
print(max(m))

### FIXED CODE ###

N,K,*P = map(int,open(0).read().split())
P = [(P[i]+1)/2 for i in range(N)]
M = m = sum(P[:K])

for i in range(N-K):
  if M < m-P[i]+P[i+K]:
    M = m-P[i]+P[i+K]
  m= m-P[i]+P[i+K]

print(M)
### BUGGY CODE ###

import collections
N,M = map(int,input().split())
road = [[] for i in range(N+1)]
rev_road = [[] for i in range(N+1)]
for _ in range(M):
    x,y=map(int,input().split())
    road[x].append(y)
    rev_road[y].append(x)

dep = []
for i in range(1,N+1):
    if len(rev_road[i]) == 0:
        dep.append(i)

def largest_distance(i):
    q = collections.deque([i])
    dp =[0]*(N+1) #地点iからの最長経路
    while q:
        now = q.popleft()
        for direct in road[now]:
            if dp[direct]<=dp[now]:
                dp[direct] = dp[now]+1
                q.append(direct)
    return max(dp)

ans = 0
for de in dep:
    ans = max(ans,largest_distance(de))
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
N,M = map(int,input().split())
road = [[] for _ in range(N+1)]
for _ in range(M):
    x,y=map(int,input().split())
    road[x].append(y)
flag = [0]*(N+1)
dist = [0]*(N+1)
def distance(i):#地点iから終点までの最長距離
    if flag[i] == 1:
        return dist[i]
    
    if road[i] == []:#行き先がない
        return 0
    else:#行き先がある
        long_dist = 0
        tmp = 0
        for dirct in road[i]:
            tmp = 1 + distance(dirct)
            long_dist = max(long_dist,tmp)
        flag[i]=1
        dist[i] = long_dist
        return long_dist

ans = 0
for i in range(1,N+1):
    ans = max(ans,distance(i))
print(ans)
### BUGGY CODE ###

n = int(input())

l = []
ans = 1
l = input().split(' ')
for i in range(n):
  x = int(l[i])
  ans *= x

if ans > 1e18:
  ans = -1
print(ans)

### FIXED CODE ###

n = int(input())

l = []
ans = 1
z = False
l = input().split(' ')
for x in l:
  x = int(x)
  if x == 0:
    print(0)
    exit(0)
for i in range(n):
  x = int(l[i])
  ans *= x
  if ans > 1e18:
    ans = -1
    break

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

import bisect

n,m=[int(i) for i in input().split()]
a_list=[int(i) for i in input().split()]
a_list.sort()

for i in range(m):
    b,c=map(int,input().split())
    index=bisect.bisect_left(a_list,c)
    if index<=0:
        continue
    if index>b:
        if b==index:
            a_list=[a_list[b]]+[c]*b+a_list[index:]
        else:
            a_list=a_list[b:index]+[c]*b+a_list[index:]
    else:
        a_list=[c]*index+a_list[index:]
    
print(sum(a_list))

### FIXED CODE ###

N,M = list(map(int,input().split()))
a_list = list(map(int,input().split()))
bc_list = []
for _ in range(M):
    b,c = list(map(int,input().split()))
    bc_list.append([b,c])

a_list = sorted(a_list)
bc_list = sorted(bc_list,key=lambda x: x[1],reverse=True)

tmp = 0
for i,a in enumerate(a_list):
    if tmp >= len(bc_list):
        break
    
    if a < bc_list[tmp][1]:
        bc_list[tmp][0] -= 1
        a_list[i] = bc_list[tmp][1]
    else:
        break

    if bc_list[tmp][0] == 0:
        tmp += 1
print(sum(a_list))
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def count2019(str, l, k): 
    count = 0
    for i in range(l): 
        n = 0
        for j in range(i, l, 1): 
            n = n * 10 + (ord(str[j]) - ord('0')) 
            if (n % k == 0): 
                count += 1
    return count 
def main():
    s=input()
    print(count2019(s,len(s),2019))


if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
from collections import Counter
def main():
	s=input()
	len_s=len(s)
	T=[0]*(len_s+1)
	T[-1],T[-2]=0,int(s[-1])
	mod=2019
	for i in range(len_s-2,-1,-1):
		T[i]=(T[i+1]+int(s[i])*pow(10,len_s-i-1,mod))%mod
	tc=list(Counter(T).values())
	ans=0
	for tcc in tc:
		ans+=tcc*(tcc-1)//2
	print(ans)

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

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

maximum = 0
for i in range(N - K + 1):
    ans = sum(p[j] for j in range(i,i + K))
    if ans >= maximum:
        maximum = ans
maximum = (maximum + K) / 2
print(maximum)

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
summ = sum(p[i] for i in range(K))
sum_list = [summ]
maximum = 0

for i in range(N - K):
    summ += p[i + K] - p[i]
    sum_list.append(summ)

maximum = max(sum_list)

print("{}".format((maximum + K) / 2))
### BUGGY CODE ###

N = int(input())
L = []
for _ in range(N):
    s = input()
    if s in L:
        pass
    else:
        L.append(s)

print(len(L))


### FIXED CODE ###

N = int(input())
L = set()
for _ in range(N):
    s = input()
    if s in L:
        pass
    else:
        L.add(s)

print(len(L))
### BUGGY CODE ###

R, C, K = map(int, input().split())
V = [[0 for _ in range(C)] for _ in range(R)]
for _ in range(K):
  r, c, v = map(int, input().split())
  V[r-1][c-1] = v
M = [[[0, 0, 0, 0] for _ in range(C)] for _ in range(R)]
# M[r][c][count in column (c)]
for r in range(R):
  for c in range(C):
    for n_pick in [0, 1] if V[r][c] else [0]:
      M[r][c][n_pick] = max(M[r][c][n_pick], n_pick*V[r][c])
      if r > 0:
        for n_prev in range(4):
          #print('R++', r, c, n_pick, n_prev)
          if M[r-1][c][n_prev] > 0 or n_prev == 0:
            M[r][c][n_pick]=max(M[r][c][n_pick],
              M[r-1][c][n_prev] + n_pick*V[r][c])
      if c > 0:
        for n_prev in range(4 - n_pick):
          #print('C++', r, c, n_pick, n_prev)
          if  M[r][c-1][n_prev]  > 0 or n_prev == 0:
            M[r][c][n_prev+n_pick]=max(M[r][c][n_prev+n_pick],
              M[r][c-1][n_prev] + n_pick*V[r][c])
    #print(candidates)
    #print(r, c, candidates, M)
    #for i in range(4):
    #  M[r][c][i] = max(candidates[i])
    #print(r, c, M)
#print(V, M)
print(max(M[R-1][C-1]))


### FIXED CODE ###

R, C, K = map(int, input().split())
V = [[0 for _ in range(C)] for _ in range(R)]
for _ in range(K):
  r, c, v = map(int, input().split())
  V[r-1][c-1] = v
M = [0] * R * C * 4 
# M[r*C*4 + c*4 + i]
# M[(r-1)*C*4 + c*4 + i]
# M[r*C*4 + (c-1)*4 + i]
# M[r][c][count in column (c)]
for r in range(R):
  for c in range(C):
    for n_pick in [0, 1] if V[r][c] else [0]:
      M[r*C*4 + c*4 +n_pick] = max(M[r*C*4 + c*4 +n_pick], n_pick*V[r][c])
      if r > 0:
        for n_prev in range(4):
          #print('R++', r, c, n_pick, n_prev)
          if M[(r-1)*C*4 + c*4 +n_prev] > 0 or n_prev == 0:
            M[r*C*4 + c*4 +n_pick]=max(M[r*C*4 + c*4 +n_pick],
              M[(r-1)*C*4 + c*4 +n_prev] + n_pick*V[r][c])
      if c > 0:
        for n_prev in range(4 - n_pick):
          #print('C++', r, c, n_pick, n_prev)
          if  M[r*C*4 + (c-1)*4 +n_prev]  > 0 or n_prev == 0:
            M[r*C*4 + c*4 +n_prev+n_pick]=max(M[r*C*4 + c*4 + n_prev+n_pick],
              M[r*C*4 + (c-1)*4 +n_prev] + n_pick*V[r][c])
    #print(candidates)
    #print(r, c, candidates, M)
    #for i in range(4):
    #  M[r][c][i] = max(candidates[i])
    #print(r, c, M)
#print(V, M)
print(max(M[((R-1)*C*4 + (C-1) *4):((R-1)*C*4 + (C-1) *4+4)]))
### BUGGY CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    S = SI()
    T = SI()
    if set(S) | set(T) != set(S):
        print(-1)
        exit()
    s2i = {}

    for i, s in enumerate(S):
        if s in s2i:
            s2i[s].append(i)
        else:
            s2i[s] = [i]

    now = 0
    digit = -1
    for t in T:
        ng = True
        for idx in s2i[t]:
            if digit < idx:
                digit = idx
                ng = False
                break
        if ng:
            digit = s2i[t][0]
            now += 1
    print(now * len(S) + digit + 1)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import deque
import bisect

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    S = SI()
    T = SI()
    if set(S) | set(T) != set(S):
        print(-1)
        exit()
    s2i = {}

    for i, s in enumerate(S):
        if s in s2i:
            s2i[s].append(i)
        else:
            s2i[s] = [i]

    now = 0
    digit = -1
    for t in T:
        target = bisect.bisect_right(s2i[t], digit)
        if target == len(s2i[t]):
            digit = s2i[t][0]
            now += 1
        else:
            digit = s2i[t][target]

    print(now * len(S) + digit + 1)


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

S = input()
s_rev = S[::-1]

r_list = [0] * 2019
r_list[0] = 1
num, d = 0, 1
for i in range(len(S)):
    num += d*int(s_rev[i])
    num %= 2019
    r_list[num] += 1
    d *= 10

ans = 0
for i in range(2019):
        ans += r_list[i]*(r_list[i]-1)//2

print(ans)


### FIXED CODE ###

S = input()
s_rev = S[::-1]

r_list = [0] * 2019
r_list[0] = 1
num, d = 0, 1
for i in range(len(S)):
    num += d*int(s_rev[i])
    num %= 2019
    r_list[num] += 1
    d *= 10
    d %= 2019

ans = 0
for i in range(2019):
        ans += r_list[i]*(r_list[i]-1)//2

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

n, k = map(int, input().split())
a = sorted(map(int, input().split()))
f = sorted(map(int, input().split()), reverse=True)
t = [a[i] * f[i] for i in range(n)]

inf = -1 #NG
sup = 10 ** 12 #OK

while sup - inf > 1:
  x = (inf + sup) // 2
  train = 0
  for i in range(n):
    train += max(t[i] - x - 1, -1) // f[i] + 1
  if train <= k:
    sup = x
  else:
    inf = x
    
print(sup)

### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
a = np.sort(np.array(input().split(), dtype=np.int))
f = np.sort(np.array(input().split(), dtype=np.int))
time = f * a[::-1]

sup = time.max()
inf = 0
while sup > inf:
  x = (sup + inf) // 2
  train = ((np.maximum(time - x, 0) + f - 1) // f).sum()
  if k < train:
    inf = x + 1
  else:
    sup = x
print(sup)
### BUGGY CODE ###

from collections import deque

n, m = list(map(int, input().split()))
root_dict = {}

for _ in range(m):
    tmp = list(map(int, input().split()))
    if tmp[0] != tmp[1]:
        if tmp[0] not in list(root_dict.keys()):
            root_dict[tmp[0]] = [tmp[1]]
        else:
            root_dict[tmp[0]].append(tmp[1])
        if tmp[1] not in list(root_dict.keys()):
            root_dict[tmp[1]] = [tmp[0]]
        else:
            root_dict[tmp[1]].append(tmp[0])

visited = [1] + [-1] * (n-1)

done = deque([1])


while done:
    x = done.popleft()
    for i in root_dict[x]:
        if visited[i-1] < 0:
            visited[i-1] = x
            done.append(i)

if -1 in visited:
    print("No")
else:
    print("Yes")
    for i in range(1, n):
        print(visited[i])

### FIXED CODE ###

from collections import deque

n, m = list(map(int, input().split()))
root_dict = {}

for _ in range(m):
    a, b = list(map(int, input().split()))
    if a not in root_dict:
        root_dict[a] = deque([b])
    else:
        root_dict[a].append(b)
    if b not in root_dict:
        root_dict[b] = deque([a])
    else:
        root_dict[b].append(a)

visited = [1] + [-1] * (n-1)

done = deque([1])

while done:
    x = done.popleft()
    while root_dict[x]:
        i = root_dict[x].popleft()
        if visited[i-1] < 0:
            visited[i-1] = x
            done.append(i)

if -1 in visited:
    print("No")
else:
    print("Yes")
    for i in range(1, n):
        print(visited[i])
### BUGGY CODE ###

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

ans = 1

for i in an:
    
    ans *= i
    
else:
    print(ans if ans <= 10 ** 18 else -1)

### FIXED CODE ###

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

ans = 1

if(0 in an):
    print(0)
    
else:
    for i in an:
        
        ans *= i
        if(ans > 10 ** 18):
            print(-1)
            break
        
    else:
        print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
MOD = 10**9 + 7

for i in range(N):
    for j in range(i+1, N):
        ans = (ans + (A[i]*A[j]))%MOD
        
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split())) + [0]
B = [0]*(N+1)

for i in range(N-1):
    B[N-i-1] = A[N-i-1]+B[N-i]
ans = 0
MOD = 10**9 + 7

for i in range(N-1):
    ans = (ans + A[i]*B[i+1])%MOD
        
print(ans)
### BUGGY CODE ###

x,y,num = map(int, input().split())
gaiz = []
zen_gaiz = []
kaisu = x
for _ in range(num):
    xg,yg = map(int,input().split())
    zen_gaiz.append((xg,yg))
    if xg > yg:
        gaiz.append((xg,yg))

if len(gaiz) ==0:
    print(kaisu)
else:
    finish = False
    for gai in sorted(gaiz, key=lambda x: x[0]):
        hidari = [gai[0]-1, gai[1]]
        while True:
            if hidari[1]==1: 
                kaisu = gai[0]-1
                finish=True
                break
            for g in zen_gaiz:
                if g[0]==hidari[0] and g[1]==hidari[1]:
                    break
            else:
                hidari[0]-=1
                hidari[1]-=1
                continue
            break
        if finish:
            break
    print(kaisu) 
                

### FIXED CODE ###

x,y,num = map(int, input().split())
gaiz = [x]*x
kaisu = x
for _ in range(num):
    xg,yg = map(int,input().split())
    if xg >= yg:
        sa = xg-yg
        if yg < gaiz[sa]:
            gaiz[sa]=(yg)
 
if len(gaiz) ==0:
    print(kaisu)
else:
    for num,(maegai,gai) in enumerate(zip(gaiz[:-1],gaiz[1:])):
        if maegai>gai and num+gai < kaisu:
            kaisu = num+gai
    print(kaisu)
### BUGGY CODE ###

n,m=map(int,input().split())
L={}

for i in range(n):
    a,b=map(int,input().split())
    if a in L:
        L[a].append(b)
    else:
        L[a]=[b]

ans=0
tab=[0 for i in range(m)]
for i in range(m):
    if i+1 in L:
        tab.extend(L[i+1])
    tmax=max(tab)
    ans+=tmax
    tab.remove(tmax)

print(ans)
    

### FIXED CODE ###

import heapq
import queue

n,m=map(int,input().split())
L=[]
for inp in range(n):
    a,b=map(int,input().split())
    L.append((a,b))
L.sort(reverse=True)

pq=[]
heapq.heapify(pq)

    
ans=0
for i in range(1,m+1):
    while len(L)>0 and L[-1][0]==i:
        heapq.heappush(pq,L.pop()[1]*-1)
    #print(pq)
    if len(pq)==0:
        continue
    else:    
        ans-=heapq.heappop(pq)

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

import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
s = input()

t = []

ans = 0
MAX = 4002
for i in range(1, min(len(s) + 1, MAX)):
    for j in range(i + 1, min(len(s) + 1, MAX)):
        if s[i - 1] == s[j - 1]:
            continue
        for k in range(j + 1, min(len(s) + 1, MAX)):
            if j - i == k - j:
                continue
            if s[k - 1] == s[i - 1] or s[k - 1] == s[j - 1]:
                continue
            ans += 1
print(ans)

### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
s = input()

counter = [(0, 0, 0)]
for c in s:
    rgb = counter[-1]
    r, g, b = 0, 0, 0
    if c == 'R':
        r = 1
    if c == 'G':
        g = 1
    if c == 'B':
        b = 1
    new_rgb = (rgb[0] + r, rgb[1] + g, rgb[2] + b)
    counter.append(new_rgb)

ans = 0
MAX = 4002
x = []
for i in range(1, min(len(s) + 1, MAX)):
    for j in range(i + 1, min(len(s) + 1, MAX)):
        if s[i - 1] == s[j - 1]:
            continue
        x.append((i, j))

y = []
for p in x:
    i = p[0]
    j = p[1]
    rgb = {'R', 'G', 'B'}
    sub = {s[i - 1], s[j - 1]}

    k_s = rgb.difference(sub).pop()
    k_idx = 0
    if k_s == 'R':
        k_idx = 0
    if k_s == 'G':
        k_idx = 1
    if k_s == 'B':
        k_idx = 2

    j_cnt = counter[j]
    k_cnt = counter[len(s)]
    omit = 0
    if (2 * j - i) <= len(s):
        omit = counter[2* j - i][k_idx] - counter[2 * j - i - 1][k_idx]
    ans += (k_cnt[k_idx] - j_cnt[k_idx] - omit)

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

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

ans = 0
asum = sum(a)
c = []
csum = 0
num = set()
for i,j in zip(a,b):
	if i<j:
		i = i + (j-i)
		ans += 1
	if i>j:
		num.add(i-j)
	csum += i


while csum>asum and len(num):
	i = max(num)
	num.remove(i)
	csum -= i
	ans += 1

if csum>asum: ans = -1
	
print(ans)



### FIXED CODE ###

import heapq
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

ans = 0
asum = sum(a)
c = []
csum = 0
num = []
for i,j in zip(a,b):
	if i<j:
		i = i + (j-i)
		ans += 1
	if i>j:
		heapq.heappush(num, -1*(i-j))
	csum += i


while csum>asum and len(num):
	i = heapq.heappop(num)*-1
	csum -= i
	ans += 1

if csum>asum: ans = -1
	
print(ans)
### BUGGY CODE ###

n, m, qqq = map(int, input().split())
LR = [[0 for _ in range(n)]for __ in range(n)]

for i in range(m):
    l, r = map(int, input().split())
    for j in range(l):
        for k in range(r-1, n):
            LR[j][k]+=1


for i in range(qqq):
    p, q = map(int, input().split())
    ans = 0
    print(LR[p-1][q-1])
# print(LR)

### FIXED CODE ###

n, m, qqq = map(int, input().split())
DP = [[0 for _ in range(n)]for __ in range(n)]

for i in range(m):
    l, r = map(int, input().split())
    DP[l-1][r-1]+=1


#DP = [[0 for _ in range(n)]for __ in range(n)]
for i in range(n-1)[::-1]:
    for j in range(1,n):
        DP[i][j] += DP[i+1][j]+DP[i][j-1]-DP[i+1][j-1]

for i in range(qqq):
    p, q = map(int, input().split())
    print(DP[p-1][q-1])
# print(DP)
### BUGGY CODE ###

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

from functools import reduce
prod = reduce(lambda x,y: x*y, an[:k])

for i in range(k, n):
    prod_next = prod // an[i - k] * an[i]
    print(['No', 'Yes'][prod_next > prod])
    prod = prod_next


### FIXED CODE ###

n, k = list(map(int, input().split()))
an = list(map(int, input().split()))
            
ank = an[:k]
for i in range(k, n):
    print(['No', 'Yes'][an[i] > ank[0]])
    ank.pop(0)
    ank.append(an[i])
### BUGGY CODE ###

N = int(input())
X = input()
ans = [1 for _ in range(N)]
#original 1 count
l = 0
for k in range(N):
  if X[k] == '1':
    l+=1


intN = int(X, 2)
if l >1:
  N1 = intN %(l-1)
N0 = intN % (l+1)


start = []
if N == 1:
  if X[0] == '1':
    print(0)
    exit()
  else:
    print(1)
    exit()
  start.append(ia)

else:
  for k in range(N):
    if X[k] == '1':
      if l == 1:
        ans[k] = 0
        ia =0
      else:  
        ia = (N1 - (2**(N-k-1)))%(l-1)
    else:
      ia = (N0 + (2**(N-k-1)))%(l+1)
    start.append(ia)

ml = len(bin(l+1))-2
poplist = [[] for _ in range(ml)]
poplist[0] = [0,1]
for k in range(1, ml):
  for m in range(k):
    poplist[k] += poplist[m]
  for m in range(len(poplist[k])):
    poplist[k][m] += 1

newpoplist = []
for _ in range(len(poplist)):
  newpoplist += poplist[_] 

for k in range(len(start)):
  for count in range(10*5):
    if start[k] == 0:
      ans[k] += count
      break
    else:
      start[k] = start[k] % newpoplist[start[k]]

for k in range(N):
  print(ans[k])

### FIXED CODE ###

N = int(input())
X = input()
ans = [1 for _ in range(N)]
#original 1 count
l = 0
for k in range(N):
  if X[k] == '1':
    l+=1
if l == 0:
  for _ in range(N):
    print(1)
  exit()
if l == 1:
  if X[-1] == '1':
    for _ in range(N-1):
      ans[_] = 2
  else:
    ans[-1] = 2 
  for k in range(N):
    if X[k] =='1':
      ans[k] = 0 
  for _ in range(N):
    print(ans[_])
  exit()


intN = int(X, 2)
N1 = intN %(l-1)
N0 = intN % (l+1)


start = []
if N == 1:
  if X[0] == '1':
    print(0)
    exit()
  else:
    print(1)
    exit()
else:
  s1 = 1
  s0 = 1
  for k in range(N-1, -1, -1):
    if X[k] == '1':      
      ia = (N1 - s1)%(l-1)
    else:
      ia = (N0 + s0)%(l+1)
    start.append(ia)
    s1 = s1*2%(l-1)
    s0 = s0*2%(l+1)
start = start[::-1]
"""
ml = len(bin(l+1))-2
poplist = [0 for _ in range(N)]
t = 1
while t < N + 1:
  t *= 2
  for k in range(t//2, N, t):
    for j in range(t//2):
      if k+j>N-1:
        break
      poplist[k+j] += 1
"""

def popcount(n):
  c = 0
  n = bin(n)[2:]
  for k in range(len(n)):
    if n[k] == '1':
      c+=1
  return c

for k in range(len(start)):
  for count in range(10*5):
    if start[k] == 0:
      ans[k] += count
      break
    else:
      start[k] = start[k] % popcount(start[k])

for k in range(N):
  print(ans[k])
### BUGGY CODE ###

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

d=[[-1 for i in range(n)] for j in range(n)]
for i in range(n):
  d[i][i]=0
num=[0 for i in range(n)]
g=[[i+1] for i in range(n-1)]
g.append([])
for i in range(1,n):
  g[i].append(i-1)
x-=1
y-=1
g[x].append(y)
g[y].append(x)

def bfs(start,dist=0):
  #global d
  #global g
  q=[start]
  while q:

    dist+=1
    now=q.pop(0)
    #print("now",now,"q",q,"d",d)
    for i in g[now]:
      if d[start][i]!=-1:
        continue
      else:
        d[start][i]=d[start][now]+1
        q.append(i)
 
for i in range(n):
  bfs(i)

for i in range(n-1):
  for j in range(i+1,n):
    if d[i][j]>=n:
      continue
    num[d[i][j]]+=1

for i in range(1,n):
  print(num[i])

### FIXED CODE ###

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

d=[[-1 for i in range(n)] for j in range(n)]
for i in range(n):
  d[i][i]=0
num=[0 for i in range(n)]
g=[[i+1] for i in range(n-1)]
g.append([])
for i in range(1,n):
  g[i].append(i-1)
x-=1
y-=1
g[x].append(y)
g[y].append(x)

def bfs(start,dist=0):
  #global d
  #global g
  q=[start]
  while q:

    dist+=1
    now=q.pop(0)
    #print("now",now,"q",q,"d",d)
    for i in g[now]:
      if d[start][i]!=-1:
        continue
      else:
        d[start][i]=d[start][now]+1
        q.append(i)
 
for i in range(n):
  bfs(i)

for i in range(n-1):
  for j in range(i+1,n):
    if d[i][j]>=n:
      continue
    num[d[i][j]]+=1

for i in range(1,n):
  print(num[i])