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

def main():
    import sys
    input = sys.stdin.readline

    s = input()
    s = s[0:len(s)-1]
    Q = int(input())

    flg = 0 # 0:sonomama 1:gyakuten
    for _ in range(Q):
        q = input().split()
        if q[0] == "1":
            if flg == 0:
                flg = 1
            else:
                flg = 0
        elif q[0]=="2":
            index,tmp = q[1],q[2]
            if (index == "1" and flg ==0) or (index == "2" and flg ==1):
                tmp += s
                s = tmp
            elif (index == "2" and flg == 0) or (index == "1" and flg == 1):
                s += tmp

    if flg==1:
        s = s[::-1]
    print(s)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    s = input()
    s = s[0:len(s)-1]
    Q = int(input())
    head = []
    tail = []

    flg = 0 # 0:sonomama 1:gyakuten
    for _ in range(Q):
        q = input().split()
        if q[0] == "1":
            if flg == 0:
                flg = 1
            else:
                flg = 0
        elif q[0]=="2":
            index,tmp = q[1],q[2]
            if (index == "1" and flg ==0) or (index == "2" and flg ==1):
                head.append(tmp)
            elif (index == "2" and flg == 0) or (index == "1" and flg == 1):
                tail.append(tmp)

    s1 = "".join(head)
    s1 = s1[::-1]
    s2 = "".join(tail)
    ans = s1 + s + s2
    if flg == 1:
        ans = ans[::-1]

    print(ans)

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

import numpy as np
H,W,M=map(int, input().split())
hl=np.array([0 for i in range(H+1)])
wl=np.array([0 for i in range(W+1)])
ms=[]
for i in range(M):
    h,w=map(int, input().split())
    hl[h]+=1
    wl[w]+=1
    ms.append([h,w])
a=max(hl)
b=max(wl)
# hmax= [i for i, x in enumerate(hl) if x ==a]
# wmax=[i for i, x in enumerate(wl) if x ==b]
hmax=np.where(hl == hl.max())[0]
wmax=np.where(wl == wl.max())[0]
a=max(hl)
b=max(wl)
bl=False
for x in hmax:
    for y in wmax:
        if [x,y] not in ms:
            bl=True
            break
    if bl:
        break
if bl:
    print(a+b)
else:
    print(a+b-1)

### FIXED CODE ###


H,W,M=map(int, input().split())
hl=[0 for i in range(H+1)]
wl=[0 for i in range(W+1)]
ms=[]
for i in range(M):
    h,w=map(int, input().split())
    hl[h]+=1
    wl[w]+=1
    ms.append([h,w])
a=max(hl)
b=max(wl)
hmax=[]
wmax=[]
s=0
for x in ms:
    if  hl[x[0]]==a and wl[x[1]]==b:
        s+=1
c=hl.count(a)
d=wl.count(b)
if s<c*d:
    print(a+b)
else:
    print(a+b-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
H, W = map(int, input().split())
map = [list(input()) for _ in range(H)]
from collections import deque

que = deque()
seen = [[-1]*W for _ in range(H)]
max = 0



for i in range(H):
    for j in range(W):
        if map[i][j] == "#":
            que.append([i,j])
            seen[i][j] = 0

while que:
    #print(que)
    y, x = que.popleft()
    for dy, dx in ([0,1],[0,-1],[1,0],[-1,0]):
        ny = y + dy
        nx = x + dx
        if 0<=ny<H and 0<=nx<W and seen[ny][nx]==-1:
            seen[ny][nx] = seen[y][x] + 1
            que.append([ny,nx])
            if max < seen[ny][nx]:
                max = seen[ny][nx]

print(max)


### FIXED CODE ###

H, W = map(int, input().split())
map = [list(input()) for _ in range(H)]
from collections import deque

que = deque()
seen = [[-1]*W for _ in range(H)]
max = 0



for i in range(H):
    for j in range(W):
        if map[i][j] == "#":
            que.append([i,j])
            seen[i][j] = 0

while que:
    #print(que)
    y, x = que.popleft()
    for dy, dx in ([0,1],[0,-1],[1,0],[-1,0]):
        ny = y + dy
        nx = x + dx
        if 0<=ny<H and 0<=nx<W and seen[ny][nx]==-1:
            seen[ny][nx] = seen[y][x] + 1
            que.append([ny,nx])
            if max < seen[ny][nx]:
                max = seen[ny][nx]

print(max)
### BUGGY CODE ###

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

cost = [0] + [float("inf") for _ in range(N-1)]
    
for i in range(1,N):
    t = max(0, i - K)
    for j in range(t,i):
        cost[i] = min(cost[i], cost[j] + abs(h[i] - h[j])) 
    
print(cost[-1])

### FIXED CODE ###

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

cost = [0 for _ in range(N)]
K = min(N, K)
for i in range(1,K):
    cost[i] = abs(h[0] - h[i])
    
for i in range(1,N):
    t = max(0, i - K)
    for j in range(t,i):
        if j == t:
            cost[i] = cost[j] + abs(h[i] - h[j])
        else:
            cost[i] = min(cost[i], cost[j] + abs(h[i] - h[j])) 
    
print(cost[-1])
### BUGGY CODE ###

l = input().split()
N = int(l[0])
Y = int(l[1])

k10 = 0
k5 = 0
k1 = 0

max_k10 = min(N, Y // 10000)
for i in reversed(range(max_k10 + 1)):
    remain10 = Y - i * 10000
    if remain10 == 0 and i == N:
        print(i, 0, 0)
        exit()
    max_k5 = min(N, remain10 // 5000)
    for j in reversed(range(max_k5 + 1)):
        remain5 = remain10 - j * 5000
        if remain5 == 0 and i + j == N:
            print(i, j, 0)
            exit()
        max_k1 = min(N, remain5 // 1000)
        for k in reversed(range(max_k1 + 1)):
            remain1 = remain5 - k * 1000
            if remain1 == 0 and i + j + k == N:
                print(i, j, k)
                exit()

print(-1, -1, -1)


### FIXED CODE ###

l = input().split()
N = int(l[0])
Y = int(l[1])

k10 = 0
k5 = 0
k1 = 0

max_k10 = min(N, Y // 10000)
for i in reversed(range(max_k10 + 1)):
    remain10 = Y - i * 10000
    if remain10 == 0 and i == N:
        print(i, 0, 0)
        exit()
    max_k5 = min(N, remain10 // 5000)
    for j in reversed(range(max_k5 + 1)):
        remain5 = remain10 - j * 5000
        if remain5 == 0 and i + j == N:
            print(i, j, 0)
            exit()
        z = N - i - j
        if remain5 - z * 1000 == 0:
            print(i, j, z)
            exit()

print(-1, -1, -1)
### BUGGY CODE ###

L,R = map(int,input().split())
l = L
m = (L *(L + 1)) % 2019
while l < R:
  r = l + 1
  while r <= R:
  	n = (l * r) % 2019 
  	m = min(m,n)
  	r = r + 1
  l = l + 1
print(m)  


### FIXED CODE ###

L,R = map(int,input().split())
l = L
m = (L *(L + 1)) % 2019
while l < min (R, L + 2019):
  r = l + 1
  while r <= min (R, L + 2019):
  	n = (l * r) % 2019 
  	m = min(m,n)
  	r = r + 1
  l = l + 1
print(m)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from operator import itemgetter    

def solve():
    from operator import itemgetter

    turns = tuple(map(int, input().split()))[1]
    cardsList = list(map(int, input().split()))
    turnsList = [tuple(map(int, input().split())) for _ in range(turns)]
    
    for chances, num in sorted(turnsList, key=itemgetter(1), reverse=True):
        for i in range(chances):
            minCard = min(cardsList)
            if num > minCard:
                cardsList[cardsList.index(minCard)] = num
            elif i == 0:
                return print(sum(cardsList))
            else:
                break
    print(sum(cardsList))
solve()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from operator import itemgetter

def solve():
    cardsNum, turnsNum = tuple(map(int, input().split()))
    cards = sorted([int(x) for x in input().split()])
    turns = sorted([tuple(int(x) for x in input().split()) for _ in range(turnsNum)], key=itemgetter(1), reverse=True)
    
    largeCount = 0
    largeCards = [0,] * cardsNum
    for chances, num in turns:
        for _ in range(chances):
            if (largeCount < cardsNum):
                largeCards[largeCount] = num
                largeCount += 1
            else:
                break
        if (largeCount >= cardsNum):
            break 
    
    for i in range(cardsNum):
        if (largeCards[i] > cards[i]):
            cards[i] = largeCards[i]
        else:
            break
    print(sum(cards))
solve()
### BUGGY CODE ###

from collections import Counter
from operator import mul
from functools import reduce


n = int(input())
A = list(map(int, input().split()))
cnt_a = Counter(A)
memo = [1] * 1000001
for a in A:
    memo[a] = 1
A.sort()
for a in A:
    for i in range(a * 2, 1000001, a):
        memo[i] = -1
for l in cnt_a.keys():
    if cnt_a[l] >= 2:
        memo[l] = "daburi"
ans = 0
for a in A:
    if memo[a] == 1:
        ans += 1
print(ans)


### FIXED CODE ###

from collections import Counter
from operator import mul
from functools import reduce


n = int(input())
A = list(map(int, input().split()))
cnt_a = Counter(A)
memo = [1] * 1000001
for a in A:
    memo[a] = 1
A.sort()
a_max = max(A)
for a in A:
    if not memo[a]:
        continue
    for i in range(a * 2, a_max + 1, a):
        memo[i] = -1
for l in cnt_a.keys():
    if cnt_a[l] >= 2:
        memo[l] = "daburi"
ans = 0
for a in A:
    if memo[a] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())
present_list = []
for i in  range(N):
    S = str(input())
    if S not in present_list:
        present_list.append(S)
print(len(present_list))

### FIXED CODE ###

N = int(input())
st = set()
for i in  range(N):
    S = str(input())
    st.add(S)
print(len(st))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for i in range(h):
   s.append(input().rstrip('\n'))

INF = 10 ** 10
d = [INF] * (h*w)

stack = deque([[ch-1, cw-1, 0]])
stack_append = stack.append
stack_popleft = stack.popleft

nex = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i, j) in [(-1,0),(1,0),(0,-1),(0,1),(0,0)]:
            continue
        else:
            nex.append((i,j))

while stack:
    curh, curw, cnt = stack_popleft()
    if d[curh * w + curw] <= cnt:
        continue
    else:
        d[curh * w + curw] = cnt
    for dh, dw in ((-1,0), (1,0), (0,1), (0,-1)):
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt:
            stack_append([nh, nw, cnt])
    for dh, dw in nex:
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and  d[nh * w + nw] > cnt:
            stack_append([nh, nw, cnt+1])

# for item in d:
#     print(item)
gh -= 1
gw -= 1

if d[gh*w + gw] == INF:
    print(-1)
else:
    print(d[gh*w + gw])

### FIXED CODE ###

import sys
input = sys.stdin.readline

import heapq

INF = 10 ** 10

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    h = []
    heapq.heappush(h, (0, s))

    while h:
        # 使っていない頂点のうち、現時点で最も距離の近いものを選びvとする
        d, v = heapq.heappop(h)
        if dist[v] < d:
            continue
        # vから到達可能な頂点について、距離が短くなれば更新
        for end, cost in G[v]:
            if dist[end] > dist[v] + cost:
                dist[end] = dist[v] + cost
                heapq.heappush(h, (dist[end], end))
    return dist


H, W = map(int, input().split())
N = H * W
ch, cw = map(lambda x:int(x)-1, input().split())
gh, gw = map(lambda x:int(x)-1, input().split())

s = []
es = tuple([] for i in range(N))

for h in range(H):
   s.append(input().rstrip('\n'))

for h in range(H):
    for w in range(W):
        if s[h][w] != '.':
            continue
        a = h*W+w
        esappend = es[a].append
        for dh in (-2, -1, 0, 1, 2):
            for dw in (-2, -1, 0, 1, 2):
                if dh == 0 and dw == 0:
                    continue
                nh = h + dh
                nw = w + dw
                if 0 <= nh and nh < H and 0 <= nw and nw < W and s[nh][nw] == '.':
                    b = nh*W+nw
                    if (dh, dw) in [(-1,0),(1,0),(0,-1),(0,1)]:
                        esappend((b, 0))
                    else:
                        esappend((b, 1))

dist = dijkstra(N, es, ch*W+cw)
if dist[gh*W+gw] == INF:
    print(-1)
else:
    print(dist[gh*W+gw])
### BUGGY CODE ###

import math

n = list(map(int,input().split()))
hikaku = 0

for x in range(1,n[2]+1):
    m = math.floor(n[0] * x // n[1]) - n[0] * math.floor(x // n[1])
    if hikaku < m:
        hikaku = m

print(hikaku)


### FIXED CODE ###

import math

n = list(map(int,input().split()))
x = min(n[1]-1 , n[2])
if n[2] >= n[2]:
    print(math.floor(n[0] * x / n[1]))
### BUGGY CODE ###

from functools import lru_cache
N = int(input())
A = list(map(int, input().split()))

def search_wb():
    sub = 1
    max_abs = abs(A[0] - sub)
    for a in A:
        if max_abs < abs(a - sub):
            max_abs = abs(a-sub)
        sub += 1
    return max_abs, -max_abs

@lru_cache(maxsize=None)
def sunuke(b):
    ret = 0
    sub = 1
    for a in A:
        ret += abs(a - (b+ sub))
        sub += 1
    return ret


maxb, minb= search_wb()

while abs(maxb - minb) > 1:
    mid = (maxb + minb) // 2
    #print("max{} min{} mid{}".format(maxb, minb, mid))
    if sunuke(mid) >  sunuke(mid + 1):
        minb = mid
    else:
        maxb = mid


mins = sunuke(minb)
maxs = sunuke(maxb)
if mins < maxs:
    print(mins)
else:
    print(maxs)



### FIXED CODE ###

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

def sunuke(b):
    ret = 0
    sub = 1
    for a in A:
        ret += abs(a - (b+ sub))
        sub += 1
    return ret


B = []

sub = 1
for a in A:
    b = a - sub
    B.append(b)
    sub += 1

B.sort()
b1 = N // 2
if N < 3:
    print(sunuke(B[b1]))
    exit()

b2 = b1 + 1
b1_s = sunuke(B[b1])
b2_s = sunuke(B[b2])
if b1_s < b2_s:
    print(b1_s)
else:
    print(b2_s)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
ls = [[int(_) for _ in input().split()] for _ in range(q)]

flag = [0] * (n - 1)

for i in range(n - 1):
	if s[i:i+2] == 'AC':
		flag[i] = 1
	
for j in range(q):
	flgp = flag[ls[j][0] - 1:ls[j][1] - 1]
	print(sum(flgp))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
ls = [[int(_) for _ in input().split()] for _ in range(q)]

csm = [0]
cnt = 0

for i in range(n - 1):
	if s[i:i+2] == 'AC':
		cnt += 1
	csm.append(cnt)
	
for j in range(q):
	print(csm[ls[j][1] - 1] - csm[ls[j][0] - 1])
### BUGGY CODE ###

import heapq
def SME(start,end):
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    i = L
    while i < N :
        if None not in ANS[i:i+50] :
            i += 50
            continue
        if ANS[i] : 
            continue
            i += 1
        else : ANS[i] = min(Whole[i+1-L:i+1])
        i+=1
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.999
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

from collections import*
n,q=map(int,input().split())
s=input()
f=defaultdict(list)
for i,c in enumerate(s):
    f[c].append(i)
l=[1]*n
for _ in range(q):
    t,d=input().split()
    for i in f[t]:
        if d=='L':
            if i-1>=0:
                l[i-1]+=l[i]
        else:
            if i+1<n:
                l[i+1]+=l[i]
        l[i]=0
print(sum(l))

### FIXED CODE ###

def solve(mid,g):
    for t,d in zip(z[::2],z[1::2]):
        if s[mid]==t:
            mid-=(d<'R')or-1
    return mid==g
n,q,s,*z=open(0).read().split()
n,q=int(n),int(q)
s=' %s '%s
ok=0
ng=n+1
while abs(ok-ng)>1:
    mid=(ok+ng)//2
    if solve(mid,0):
        ok=mid
    else:
        ng=mid
a=ok
ok=n+1
ng=0
while abs(ok-ng)>1:
    mid=(ok+ng)//2
    if solve(mid,n+1):
        ok=mid
    else:
        ng=mid
print(max(0,ok-a-1))
### BUGGY CODE ###

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

sum = 0

for i in range(n):
  for j in range(i+1, n):
    sum += a[i]*a[j]
    
print(sum%(10**9+7))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
 
# required function 
def findProductSum(A, n): 
      
    # calculating array sum (a1 + a2 ... + an) 
    array_sum = 0
    for i in range(0, n, 1): 
        array_sum = array_sum + A[i] 
  
    # calcualting square of array sum 
    # (a1 + a2 + ... + an)^2 
    array_sum_square = array_sum * array_sum 
  
    # calcualting a1^2 + a2^2 + ... + an^2 
    individual_square_sum = 0
    for i in range(0, n, 1): 
        individual_square_sum += A[i] * A[i] 
  
    # required sum is (array_sum_square - 
    # individual_square_sum) / 2 
    return (array_sum_square - 
            individual_square_sum)
mod = 10**9+7
  
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
  
print(modinv(2)*int(findProductSum(a, n))%mod)
### BUGGY CODE ###

import sys


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


sys.setrecursionlimit(20000000)
MOD = 10 ** 9 + 7


def main():
    L = input()

    pow = [0] * (len(L) + 1)
    pow[0] = 1
    for i in range(1, len(L) + 1):
        pow[i] = pow[i - 1] * 3 % MOD

    def cnt(s):
        if len(s) == 1:
            if s[0] == "1":
                return 3
            else:
                return 1
        if s[0] == "0":
            return cnt(s[1:]) % MOD
        else:
            return (cnt(s[1:]) * 2) % MOD + pow[len(s) - 1]

    answer = cnt(L) % MOD

    print(answer)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import queue


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


sys.setrecursionlimit(20000000)
MOD = 10 ** 9 + 7


def main():
    L = list(input())

    pow = [0] * (len(L) + 1)
    pow[0] = 1
    for i in range(1, len(L) + 1):
        pow[i] = pow[i - 1] * 3 % MOD
    N = len(L)
    if L[-1] == "0":
        answer = 1
    else:
        answer = 3
    for i in range(1, N):
        if L[N - i - 1] == "1":
            answer = answer * 2 + pow[i]
            answer %= MOD
        else:
            continue
    print(answer)


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

import itertools

N=int(input())
L=list(itertools.permutations(map(int,input().split())))
ANS=-1
for l in L:
  ll = list(l)
  TMP = ll[0]
  for i in range(1, N):
    TMP = (ll[i] + TMP) / 2.0
  if ANS <= TMP:
    ANS = TMP
print(ANS)


### FIXED CODE ###

N=int(input())
L=list(map(int,input().split()))
L.sort()
ANS = L[0]
for i in range(1, N):
  ANS = (L[i] + ANS) / 2.0
  
print(ANS)
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

ab = []
for i in range(x):
    for j in range(y):
        ab.append(a[i] + b[j])
ab.sort(reverse = True)

abc = []
for i in range(min(3000, len(ab))):
    for j in range(z):
        abc.append(ab[i] + c[j])
abc.sort(reverse = True)

for i in range(k):
    print(abc[i])


### FIXED CODE ###

x,y,z,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

ab = []
for i in range(x):
    for j in range(y):
        ab.append(a[i] + b[j])
ab.sort(reverse = True)

abc = []
for i in range(min(k,len(ab))):
    for j in range(z):
        abc.append(ab[i] + c[j])

abc.sort(reverse = True)

for i in range(k):
    print(abc[i])
### BUGGY CODE ###

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

c = [1000000000]*(N-K+10)
for i in range(N - K + 1):
    if (len(x[i:i+K]) != K):
        c[i] = 1000000000
        continue
    p = x[i:i+K]
    lr = abs(p[0]) + abs(p[-1] - p[0])
    rl = abs(p[-1]) + abs(p[0] - p[-1])
    if lr < rl:
        c[i] = lr
    else:
        c[i] = rl

print(min(c))


### FIXED CODE ###

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

ans = 10**18
for i in range(N - K + 1):
    p1 = x[i]
    p2 = x[i+K-1]
    lr = abs(p1) + abs(p2 - p1)
    rl = abs(p2) + abs(p1 - p2)
    if lr < rl:
        ans = min(ans,lr)
    else:
        ans = min(ans,rl)
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split())) 
x=0
for j in range(len(A)):
    for i in range(len(A)):
        if(j!=i):
            if(A[j]==A[i]):
                x+=1
                break
                
if(x==0):
    print('YES')
else:
    print('NO')
    

### FIXED CODE ###

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

def has(seq):
    return len(seq) != len(set(seq))

if(has(A)):
    print('NO')
else:
    print('YES')
### BUGGY CODE ###

def base10toN(num, base):
    converted_string, modstring = "", ""
    currentnum = num
    if not num:
        return '0'
    while currentnum:
        mod = currentnum % base
        currentnum = currentnum // base
        converted_string = chr(48 + mod + 7*(mod > 10)) + converted_string
    return converted_string
n=int(input())
popcount=[]
for i in range(1,2*10**5+1):
  temp=base10toN(i,2)
  ans=0
  for j in range(len(temp)):
    if temp[j]=='1':
      ans+=1
  popcount.append(ans)
x=input()
xint=int(x, 2)
ones=0
ans1=[]
for i in range(n):
  if x[i]=='1':
    ones+=1
for i in range(n):
  counter=0
  if x[i]=='0':
    temp=xint+pow(2,n-1-i)
    temp1=ones+1
  else:
    temp=xint-pow(2,n-1-i)
    temp1=ones-1
  ans=0
  while temp!=0:
    temp=temp%temp1
    temp1=popcount[temp-1]
    ans+=1
  ans1.append(str(ans))
print(' '.join(ans1))
    

### FIXED CODE ###

def base10toN(num, base):
    converted_string, modstring = "", ""
    currentnum = num
    if not num:
        return '0'
    while currentnum:
        mod = currentnum % base
        currentnum = currentnum // base
        converted_string = chr(48 + mod + 7*(mod > 10)) + converted_string
    return converted_string
n=int(input())
pop=[0]*(2*10**5+1)
for i in range(1,2*10**5+1):
  temp=base10toN(i,2)
  ans=0
  for j in range(len(temp)):
    if temp[j]=='1':
      ans+=1
  r=i%ans
  pop[i]=pop[r]+1
x=input()
ones=0
ans1=[]
for i in range(n):
  if x[i]=='1':
    ones+=1
dividemore=0
divideless=0
for i in range(n):
  if x[i]=='1':
    dividemore=(pow(2,n-1-i,ones+1)+dividemore)%(ones+1)
    if ones>=2:
      divideless=(pow(2,n-1-i,ones-1)+divideless)%(ones-1)
for i in range(n):
  counter=0
  if x[i]=='0':
    temp=(dividemore+pow(2,n-1-i,ones+1))%(ones+1)
  else:
    if ones==1:
      ans1.append('0')
      continue
    else:
      temp=(divideless-pow(2,n-1-i,ones-1))%(ones-1)
  ans1.append(str(pop[temp]+1))
print(' '.join(ans1))