Harryxun/stf_run huggingface dataset:
n,k = map(int,input().split())
A = list(map(int,input().split()))
B = []
B.append(A[0])
c = 1
while True:
  b = A[c-1]
  c = A[b-1]
  B.append(c)
  if c == b:
    break
  if len(B) == len(A):
    break
B = B*(10**18)
print(B[k])

  


### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
pos = 0
visit = [0] * N
move = []
roop = []
while visit[pos]!=2:
    if visit[pos]==0:
        move.append(pos)
    else:
        roop.append(pos)
    visit[pos] += 1
    pos = A[pos] - 1
if len(move)>K:
    print(move[K]+1)
else:
    print(roop[(K-(len(move)-len(roop)))%len(roop)]+1)
M, K = map(int, input().split())

tmp = 0
X = list(range(K)) + list(range(K+1, 2**M))

if M == 1:
    if K == 0:
        print("1 1 0 0")
    else:
        print(-1)
elif 2**M > K:
    ans = X + [K] + X[::-1] + [K]
    print(*ans)
else:
    print(-1)


### FIXED CODE ###

M, K = map(int, input().split())

if M == 1:
    if K == 0:
        print("1 1 0 0")
    else:
        print(-1)
elif 2**M > K:
    X = list(range(K)) + list(range(K+1, 2**M))
    ans = " ".join(map(str, X + [K] + X[::-1] + [K]))
    print(ans)
else:
    print(-1)
import numpy as np
N,*A=map(int,open(0).read().split())
A=(np.array(A)//400).astype("int32")

color_num=0

colors=np.zeros(9)

for a in A:
  colors[a]+=1

c=np.count_nonzero(colors[:8])

min_color_num = 1 if (c==0 and colors[-1]>0) else c
max_color_num = min(8,c+max(int(colors[-1]),0))

print(min_color_num,max_color_num)

### FIXED CODE ###

N,*A=map(int,open(0).read().split())

colors = [0 for i in range(8)]
tyty = 0

for a in A:
  c = a//400
  if c>=8:
    tyty+=1
  else:
    colors[c]+=1

cNum = 8-colors.count(0)
    
minC = max(cNum,1)
maxC = cNum+tyty

print(minC,maxC)
n = int(input())
A = [[0]*10 for i in range(12)] 

for _ in range(n):
    b, f, r, v = map(int, input().split())
    A[(b-1)*3 + (f-1)][r-1] = v
for i, v in enumerate(A, 1):
    print(' '.join([str(p) for p in v]))
    if i == 3, 6, 9:
        print('####################')


### FIXED CODE ###

n = int(input())
A = [[0]*10 for i in range(12)] 

for _ in range(n):
    b, f, r, v = map(int, input().split())
    A[(b-1)*3 + (f-1)][r-1] += v
for i, v in enumerate(A, 1):
    print(' ' + ' '.join([str(p) for p in v]))
    if i == 3 or i == 6 or i == 9:
        print('####################')
# -*- coding: utf-8 -*-
# 整数の入力
import math


if __name__ == "__main__":
    
    INPUT = list(map(float, input().split()))


    print(math.floor(h1 * m1))


### FIXED CODE ###

# -*- coding: utf-8 -*-
from decimal import Decimal


if __name__ == "__main__":
    
    INPUT = list(map(str, input().split()))

    h1 = int(INPUT[0])
    m1 = int(Decimal(INPUT[1]) * 100)

    print( h1 * m1 // 100 )
def a():return input()#s
def ai():return int(input())#a,n or k
def ma():return map(int, input().split())#a,b,c,d or n,k
def ms():return map(str, input().split())#,a,b,c,d
def lma():return list(map(int, input().split()))#x or y
def lms():return list(map(str, input().split()))#x or y
a = ai()
x = lma()
dp =[0]+[float("INF")]*(a-1)
def cal(i):
    res = float("INF")
    if dp[i]< float("INF"): return dp[i]
    if(i==0) :return 0
    res = min(res,cal(i-1)+abs(x[i]-x[i-1]))
    if i >1 :res = min(res,cal(i-2)+abs(x[i]-x[i-2])) # i=1の時の処理
    dp[i] = res
    return dp[i]
print(cal(a-1))

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
dp = [0] + [10**10]*N
for i,h in enumerate(a):
    for j in range(i+1,min(i+3,N)):
        dp[j] = min(dp[j],dp[i]+abs(h-a[j]))
    #print(dp)
print(dp[N-1])
import math

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

if (2*xy[1]-xy[0]) % 3 == 0 and (2*xy[0]-xy[1]) % 3 == 0:
    a = (2*xy[1]-xy[0]) // 3
    b = (2*xy[0]-xy[1]) // 3
    ans = int(math.factorial(a+b)/(math.factorial(a)*math.factorial(b)))
    print(int(ans/(10**9 + 7)))
else:
    print(0)

### FIXED CODE ###

import math
from operator import mul
from functools import reduce

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
xy = list(map(int, input().split()))

if (2*xy[1]-xy[0]) % 3 == 0 and (2*xy[0]-xy[1]) % 3 == 0 and 2*xy[1]-xy[0] > -1 and 2*xy[0]-xy[1] > -1:
    a = (2*xy[1]-xy[0]) // 3
    b = (2*xy[0]-xy[1]) // 3
    print(cmb(a+b, a)%(10**9 + 7))
else:
    print(0)
n,a,b = [int(x) for x in input().split()]
mod = 10**9 + 7
import math
#再起限界突破
import sys
sys.setrecursionlimit(2000000000)
#メモ化再帰
from functools import lru_cache
@lru_cache(maxsize=2000000000)
def action(k):
    if k == 1:
        return 1
    else:
        return k * action(k-1)
ans = pow(2,n,mod)  - action(n)/action(n-a)/action(a) - action(n)/(action(n-b)*action(b)) - 1
print(int(ans%mod))

### FIXED CODE ###

n,a,b = [int(x) for x in input().split()]
mod = 10**9 + 7
def comb(x,y):
    child = 1
    mother = 1
    for i in range(y):
        child = child * (x-i)%mod
        mother = mother * (i+1)%mod
    return child * pow(mother,mod-2,mod) % mod
ans = pow(2,n,mod) - 1
ans -= comb(n,a)
ans %= mod
ans -= comb(n,b)
ans %= mod
print(ans)
S=input()
C=[]
count=0
for i in S:
    if i in {'A','C','G','T'}:
        count += 1
        continue
    elif i not in {'A','C','G','T'}:
        C.append(count)
        count=0
        continue
    
print(max(C))

### FIXED CODE ###

S=list(input())
Count=[]
for i in range(len(S)):
    if S[i] in ['A','C','T','G']:
        Count.append(1)
    else:
        Count.append(0)
c=0
m=[]
for i in range(len(S)):
    if Count[i]==1:
        c+=1
        m.append(c)
        continue
    else:
        c*=0
        m.append(c)
        continue


print(max(m))
_ = int(input())
members = input()

counts = []
for i in range(len(members)):
    count=0
    for j in range(len(members)):
        if i == j:
            continue
        else:
            if (members[j] == 'W' and i<j) or (members[j] == 'E' and i>j):
                continue
            else:
                count+=1
        if count > min(counts):
            break
    counts.append(count)
print(min(counts))

### FIXED CODE ###

n = int(input())
members = input()
m_e = members.count("E")
cost = m_e
costs = []
for i in range(n):
    if members[i]=="E":
        cost-=1
    if (i!=0 and members[i-1]=="W"):
        cost+=1
    costs.append(cost)
print(min(costs))
a, b, c, d = map(int,input().split())

# aとcの距離の絶対値ACを定義
if (a - c) <= 0:
    AC = (a-c)
else:
    AC = (c-a)

# BがAとCの間に入る場合のみ、AB間、BC間を定義
if a < b < c:
    AB = (b - a)
    BC = (c - b)
if c < b < a:
    AB = (a-b)
    BC = (b-c)

# AとCの距離がd以下ならYes！
if AC <= d:
    print('Yes')

# AB間、BC間ともにd以下ならYes！
if AB <= d and BC <= d:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

a, b, c, d = map(int,input().split())

# aとcの距離の絶対値ACを定義
if (a - c) >= 0:
    AC = (a-c)
else:
    AC = (c-a)

# BがAとCの間に入る場合のみ、AB間、BC間を定義
if a < b < c:
    AB = (b - a)
    BC = (c - b)
if c < b < a:
    AB = (a-b)
    BC = (b-c)

# AとCの距離がd以下ならYes！
if AC <= d:
    print('Yes')
# AB間、BC間ともにd以下ならYes！
elif AB <= d and BC <= d:
    print('Yes')
else:
    print('No')
import fileinput

for line in fileinput.input():
  a, b = map(int, line.strip().split())

print('{0} {1}'.format(a*b, 2a+2b))

### FIXED CODE ###

import fileinput

for line in fileinput.input():
  a, b = map(int, line.strip().split())

print('{0} {1}'.format(a*b, (2*a)+(2*b)))
[a, b] = [int(input()) for _ in range(2)]

print(a * b + ' ' + (a + b) * 2)

### FIXED CODE ###

[a, b] = [int(x) for x in input().split()]
print(a * b ,(a + b) * 2)
import sys
import math
def I():return int(sys.stdin.readline().replace("\n",""))
def I2():return map(int,sys.stdin.readline().replace("\n","").split())
def S():return str(sys.stdin.readline().replace("\n",""))
def L():return list(sys.stdin.readline().replace("\n",""))
def Intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def Lx(k):return list(map(lambda x:int(x)*-k,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":
    N ,W = I2()
    w = [0]*N
    v = [0]*W
    dp = [[0]*N+1 for i in range(W+1)]
    for i in range(N):
        a,b = I2()
        w[i] = a
        v[i] = b
    for i in range(N):
        for j in range(0,W+1):
            if(j >= w[i]):
                dp[i+1][j] = max(dp[i+1][j],dp[i][j-w[i]] + v[i])
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
            #print(dp)
    print(dp[N][W])

### FIXED CODE ###

import sys
import math
def I():return int(sys.stdin.readline().replace("\n",""))
def I2():return map(int,sys.stdin.readline().replace("\n","").split())
def S():return str(sys.stdin.readline().replace("\n",""))
def L():return list(sys.stdin.readline().replace("\n",""))
def Intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def Lx(k):return list(map(lambda x:int(x)*-k,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":
    N ,W = I2()
    w = [0]*N
    v = [0]*W
    dp = [[0]*(W+1)for _ in range(N+1)]
    for i in range(N):
        a,b = I2()
        w[i] = a
        v[i] = b
    for i in range(N):
        for j in range(0,W+1):
            if(j >= w[i]):
                dp[i+1][j] = max(dp[i+1][j],dp[i][j-w[i]] + v[i])
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
            #print(dp)
    print(dp[N][W])
N = map(int,input().split())

if N >=1000:
  print("ABD")

else:
  print("ABC")

### FIXED CODE ###

N = int(input())
if N < 1000:
    print("ABC")
else:
    print("ABD")
n=int(input())
k=int(input())
N=map(int,input().split())
count=0
for n1 in n:
  if N>=k:
    count+=1
  ekse:
    count+=0
print(count)

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
count = 0
for i in h:
    if i >= K:
      count+=1
print(count)
import sys 
sys.setrecursionlimit(100000) 
import queue

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(N-1):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    G[y-1].append(x-1)


dp = {}
def tdc(p, v):
    if G[v] == [p]:
        dp[(p, v)] = 1
        return 1
    res = 1
    for u in G[v]:
        if u == p: continue
        res *= (1+tdc(v, u)) 
        res %= M
    dp[(p, v)] = res
    return dp[(p, v)]

r = 1       
tdc(-1, r)

ans = [0]*N
ans[r] = dp[(-1, r)]

def buc(p, v):
    if G[v] == [p]: return 0
    nn = len(G[v])
    pf = [1]
    for u in G[v]:
        pf.append(pf[-1]*(dp[(v, u)]+1)%M)
    pb = [1]
    for u in G[v][::-1]:
        pb.append(pb[-1]*(dp[(v, u)]+1)%M)
    for i in range(nn):
        u = G[v][i]
        if u == p: continue
        dp[(u, v)] = pf[i] * pb[::-1][i+1] 
        dp[(u, v)] %= M
        ans[u] = dp[(v, u)]*(1+dp[(u, v)]) 
        ans[u] %= M
        buc(v, u)

buc(-1, r)

            
print('\n'.join(map(str, ans))) 

### FIXED CODE ###

import sys
 
sys.setrecursionlimit(100000)
 
 
def dfs1(v, p):
    val = 1
    pre_mul = [1]
    rev_mul = []
    for c in links[v]:
        if c == p:
            pre_mul.append(val)
            rev_mul.append(1)
            continue
        res = 1 + dfs1(c, v)
        val *= res
        val %= m
        pre_mul.append(val)
        rev_mul.append(res)
    dp[v] = val
    for i in range(len(rev_mul) - 2, -1, -1):
        rev_mul[i] *= rev_mul[i + 1]
        rev_mul[i] %= m
    rev_mul.append(1)
    pre_muls[v] = [pre_mul, rev_mul]
    return val
 
 
def dfs2(v, p, a):
    dp[v] = dp[v] * a % m
    pmv = pre_muls[v]
    for i, c in enumerate(links[v]):
        if c == p:
            continue
        pmc = pmv[0][i] * pmv[1][i + 1] % m
        pmc = pmc * a % m
        dfs2(c, v, pmc + 1)
 
 
n, m = map(int, input().split())
links = [[] for _ in range(n)]
dp = [0 for _ in range(n)]
pre_muls = [None for _ in range(n)]
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    x -= 1
    y -= 1
    links[x].append(y)
    links[y].append(x)
dfs1(0, None)
dfs2(0, None, 1)
print('\n'.join(map(str, dp)))
Num = [int(n) for n in input().rstrip().split()]

D = [int(n) for n in input().rstrip().split()]

for i in rang:e(Num[0],10000):
    if len(set([str(n) for n in D]) & set(str(i))) == 0:
        print(int(i))
        break


### FIXED CODE ###

Num = [int(n) for n in input().rstrip().split()]

D = [int(n) for n in input().rstrip().split()]

for i in range(Num[0],100000):
    if len(set([str(n) for n in D]) & set(str(i))) == 0:
        print(int(i))
        break
def gcd(x,y):
  n,m = min(x,y), max(x,y)
  while n!=0:
    n, m = m%n, n
  
  return m

def prime(N):
  p = [i+1 for i in range(N)]
  for i in range(2,N+1):
    p = [i_p for i_p in p if i_p%i!=0 or i_p/i==1]

  return p
def prime_factorization(N):
  n = N
  P = prime(int(N**0.5))
  p_f = [1]
  while n != 1:
    for p in P[1:]:
      if n%p == 0:
        p_f.append(p)
        n = n / p
        break
  return p_f
A, B = list(map(int, input().split(" ")))
print(len(set(prime_factorization(gcd(A, B))))

### FIXED CODE ###

def gcd(x,y):
  n,m = min(x,y), max(x,y)
  while n!=0:
    n, m = m%n, n
  
  return m

def prime_factorization(N):
  f = 2
  p_f = []
  while N%f==0:
    p_f.append(f)
    N //= f
  f = 3
  while f**2 <= N:
    if N%f==0:
      p_f.append(f)
      N //= f
    else: f+=2
  if N!=1: p_f.append(N)
  return p_f

A, B = list(map(int, input().split(" ")))
print(1+len(set(prime_factorization(gcd(A, B)))))
n,m=[int(i) for i in input().split()]
x=[int(i) for i in input().split()]
x.sort()
a=[]
if m==1:
    print("0")
else:
    for i in range(m-1):
        a.append(x[i+1]-x[i])
    a.sort(reverse=True)
    result=0
    print("0")
    for i in range(n-1):
        result+=a[i]
    print(max(x)-min(x)-result)

### FIXED CODE ###

n,m=[int(i) for i in input().split()]
x=[int(i) for i in input().split()]
x.sort()
a=[]
if m==1 or n>=m:
    print("0")
else:
    for i in range(m-1):
        a.append(x[i+1]-x[i])
    a.sort(reverse=True)
    if n==1:
        print(max(x)-min(x))
    else:
        result=0
        for i in range(n-1):
            result+=a[i]
        print(max(x)-min(x)-result)
N = int(input())

edges = []

for _ in range(N - 1):
    a, b = map(int,input().split())
    edges.append([a, b])

colors = [-1] * (N - 1)

def func(a, p_color=-1):
    edge_index = []
    for i in range(N - 1):
        _a, _b = edges[i]
        if _a == a:
            edge_index.append(i)

    color = 1
    for e_i in edge_index:
        if color == p_color:
            color += 1
        __a, __b = edges[e_i]
        colors[e_i] = color
        func(__b, color)
        color += 1

func(1)

print(max(colors))
for c in colors:
    print(c)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

N = int(input())

edges = [[] for _ in range(N)]

for i in range(N - 1):
    a, b = map(int,input().split())
    edges[a - 1].append([b - 1, i])

colors = [-1] * (N - 1)

def func(a, p_color=-1):
    color = 1
    for b, i in edges[a]:
        if color == p_color:
            color += 1
        colors[i] = color
        func(b, color)
        color += 1

func(0, -1)

print(max(colors))
for c in colors:
    print(c)
n = int(input())
l = [int(input()) for i in range(n)]
print("Yes" if (sum(l) - max(l)) > max(l) else "No")

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
print("Yes" if sum(l) - max(l) > max(l) else "No")
import collections

bluecard = []
redcard = []

n = int(input())
for i in range(n):
    bluecard.append(input())

m = int(input())
for i in range(m):
    redcard.append(input())

blue_count = collections.Counter(bluecard)
red_count = collections.Counter(redcard)
diff = blue_count - red_count
print(diff.most_common(1)[0][1])



### FIXED CODE ###

import collections

bluecard = []
redcard = []

n = int(input())
for i in range(n):
    bluecard.append(input())

m = int(input())
for i in range(m):
    redcard.append(input())

blue_count = collections.Counter(bluecard)
red_count = collections.Counter(redcard)
diff = blue_count - red_count
if len(diff.keys()) > 0:
    print(diff.most_common(1)[0][1])
else:
    print(0)
# coding: utf-8
# Your code here!
num =[]
ans =0
for i in range(3):
    x,y = map(int,input().split(" "))
    num.append(x)
    num.append(y)
for i in range(1,5):
    if num.count(i)==3:
        ans +=1
if ans>0:
    print("NO")
else:
    print("YES")


### FIXED CODE ###

# coding: utf-8
# Your code here!
N,K =map(int, input().split(" "))
ans =0
for i in range(1,N+1):
    if i%2==1:
        ans +=1
if ans>=K:
    print("YES")
else:
    print("NO")
n=int(input())
x=int(input())
if x = 0:
    break
elif 1 <= x <= 10:
    print(1000*x-n)
elif 11 < x:
    break 


### FIXED CODE ###

n=int(input())
a=n%1000
if a==0:
    print(0)
else:
    print(1000-a)
n = input()
v_list = [int(x) for x in input().split()]
c_list = [int(x) for x in input().split()]
total_profit = 0
for v, c in zip(v_list, c_list)
    profit = v -c
    if profit > 0:
        total_profit += profit
print(total_profit)

### FIXED CODE ###

import numpy as np
 
n = input()
v = np.array([int(x) for x in input().split()])
c = np.array([int(x) for x in input().split()])
 
profit = v - c
positive_profit = profit[profit > 0]
print(np.sum(positive_profit))
import sys

if __name__ == "__main__":
    dataset = [line.strip() for line in sys.stdin.readlines()]
    process(dataset)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)


def main():
    solve()


def solve():
    for data in get_dataset():
        print search(data)


def search(data):
    count = 0
    H = len(data)
    W = len(data[0])
    for i in xrange(H):
        for j in xrange(W):
            if data[i][j] == '.':
                continue
            _search(i, j, H, W, data[i][j], data)
            count += 1
    return count


def _search(i, j, H, W, cell, data):
    data[i][j] = '.'
    for a in xrange(i-1, i+2):
        if not -1 < a < H:
            continue
        for b in xrange(j-1, j+2):
            if not -1 < b < W:
                continue

            if a != i and b != j:
                continue

            if data[a][b] == '.':
                continue

            if cell == data[a][b]:
                _search(a, b, H, W, cell, data)
    return


def get_dataset():
    dataset = []
    while True:
        line = raw_input().rstrip().split()
        H = int(line[0])
        if H == 0:
            break

        data = []
        for i in xrange(H):
            data.append(list(raw_input().rstrip()))
        dataset.append(data)
    return dataset


if __name__ == '__main__':
    main()
a,b=map(int,input().split())
if ab%2==0:
  print('NO')
else:
  print('Yes')

### FIXED CODE ###

a,b=map(int,input().split())
if a*b%2==0:
  print('No')
else:
  print('Yes')
def main():
    _, __ = map(int, input().split())
    ___ = [[] for _ in range(_)]
    for _ in range(__):
        ____, _____ = map(lambda ______: int(_____) - 1, input().split())
        ___[____].append(_____)
        ___[_____].append(____)

    _______ = [False] * _
    ________ = ___________(0, ___, _______, 0)

    print(________)


def ___________(_____, ___, _______, _________):
    _______[_____] = True
    if all(_______):
        return _________ + 1

    for __________ in ___[_____]:
        if _______[__________]:
            continue
        _________ = ___________(__________, ___, _______, _________)
        _______[__________] = False

    return _________


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(m):
        u, v = map(lambda x: int(x) - 1, input().split())
        g[u].append(v)
        g[v].append(u)

    vis = [False] * n
    ans = dfs(0, g, vis, 0)

    print(ans)


def dfs(v, g, vis, count):
    vis[v] = True

    if all(vis):
        return count + 1

    for i in g[v]:
        if vis[i]:
            continue
        count = dfs(i, g, vis, count)
        vis[i] = False

    return count


if __name__ == '__main__':
    main()
import math
n = input()
a = list(map(int,input().split()))
ans = float("inf")
for i in a:
  ans = min(ans, len(bin(i)) - bin(i).rfind("1") - 1)
print(round(ans)

### FIXED CODE ###

import math
n = input()
a = list(map(int, input().split()))
ans = float("inf")
for i in a:
    ans = min(ans, len(bin(i)) - bin(i).rfind("1") - 1)
print(round(ans))
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N, S = sys.stdin.read().split()
    N = int(N)
    cnt0 = S.count("1")

    if cnt0 == 0:
        print(*[1]*N, sep="\n")
        raise 1
        return

    X = int(S, 2)

    def f2():
        cache = [-1] * max(9, cnt0+1)
        cache[0] = 0
        for i in range(4): cache[1<<i] = 1
        def f2(x):
            if cache[x] != -1:
                return cache[x]

            y = bin(x).count("1")
            z = 1 + f2(x % y)
            cache[x] = z

            return z
        f2.cache = cache
        return f2
    f2 = f2()

    dc = {}
    for k, v in (("0", 1), ("1", -1)):
        x = cnt0 + v
        y = X % x if x else 0
        dc[k] = (x, v, y, [1, N-1])

    ans = [0] * N
    for i in reversed(range(N)):
        si = S[i]
        cnt, v, n, m1 = dc[si]

        if cnt == 0:
            ans[i] = 0
            continue

        m2 = (m1[0]<<(m1[1]-i)) % cnt
        n = (n + v*m2) % cnt
        m1[0], m1[1] =  m2, i

        ans[i] = 1 + f2(n)

    print(*ans, sep="\n")


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from functools import lru_cache


@lru_cache(maxsize=2*10**5)
def f2(x):
    if x == 0: return 0
    y = bin(x).count("1")
    return 1 + f2(x % y)

def resolve():
    N = int(input())
    W = 16
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        print(*[1]*N, sep="\n")
        return

    X = int(S, 2)

    dc = {}
    for k, v in (("0", 1), ("1", -1)):
        x = cnt0 + v
        y = X % x if x else 0
        dc[k] = (x, v, y)

    ans = []
    for i, si in enumerate(S):
        cnt, v, n = dc[si]

        if cnt == 0:
            ans.append(0)
            continue

        ni = N - i - 1
        n = (n + v * pow(2, ni, cnt)) % cnt

        ans.append(1+f2(n))

    print(*ans, sep="\n")


if __name__ == "__main__":
    resolve()