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

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

visited = [1]
for i in range(K):
    next_town = al[visited[i] - 1]
    if next_town in set(visited):
        loop_sta = visited.index((next_town))  # visited_townsにおけるループ開始のインデックス
        loop_end = len(visited)  # visited_townsにおけるループの終わりのインデックス
        loop_length = loop_end - loop_sta  # 繰り返すループの長さ
        amari = (K - loop_sta) % loop_length
        ans = visited[loop_sta + amari]
        print(ans)
        exit()
    else:
        visited.append(next_town)
        continue

else:
    print(visited[-1])



### FIXED CODE ###

from collections import defaultdict


def inpl():
    return list(map(int, input().split()))


N, K = inpl()
aa = inpl()

s = 1

route = [s]
ed = set([s])

for i in range(1, K + 1):
    s = aa[s - 1]
    if s in ed:
        Li = route.index(s)
        Ri = len(route)
        idx = Li + (K - Li) % (Ri - Li)
        print(route[idx])
        break
    else:
        route.append(s)
        ed.add(s)
        continue
else:
    print(s)
### BUGGY CODE ###

def lcs(X, Y):
    m, n = len(X), len(Y)
    c = [[0 for i in range(n+1)] for j in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[j-1]:
                c[i][j] = c[i-1][j-1] + 1
            else:
                c[i][j] = max(c[i-1][j], c[i][j-1])
    return c[m][n]

q = int(input())
for i in range(q):
    X = input()
    Y = input()
    print(lcs(X, Y))


### FIXED CODE ###

def lcs(X, Y):
    global c
    m, n = len(X), len(Y)
    c = [[0 for i in range(n+1)] for j in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[j-1]:
                c[i][j] = c[i-1][j-1] + 1
            else:
                c[i][j] = max(c[i-1][j], c[i][j-1])
    return c[m][n]

def lcs_improved(X, Y):
    hist = [0] # yの文字cまでを見た時に, hist[i]以降の文字列において, 共通文字のうち, 一番小さいindexのもの
    for c in Y:
        for i in range(len(hist)-1, -1, -1):
            next_match_i = X.find(c, hist[i])+1
            if next_match_i:
                if i+1 < len(hist):
                    hist[i+1] = min(hist[i+1], next_match_i)
                else:
                    hist.append(next_match_i)
    return len(hist)-1

q = int(input())
for i in range(q):
    X = input()
    Y = input()
    print(lcs_improved(X, Y))
### BUGGY CODE ###

n=int(input())
arr=list(map(int,input().split()))
t=1
for i in range(n):
    t*=arr[i]
    
if t>10**18:
    t=-1
print(t)

### FIXED CODE ###

n=int(input())
arr=list(map(int,input().split()))
t=1
arr.sort()
for i in range(n):
    t*=arr[i]
    if arr[i]==0:
        t=0
        break
    elif t>10**18:
        t=-1
        break
print(t)
### BUGGY CODE ###

def main():
    height, width, target_count = [int(x) for x in input().split()]
    count_by_height = [0] * height
    count_by_width = [0] * width
    bomb_is = [[False] * width for _ in range(height)]
    for _ in range(target_count):
        bom_h, bom_w = [int(x) - 1 for x in input().split()]
        count_by_height[bom_h] += 1
        count_by_width[bom_w] += 1
        bomb_is[bom_h][bom_w] = True
        # 最大らしき十字はわかるが，交差点にあるかどうかが不明だ。
        # 最大になりそうな十字がいっぱい（前マスに爆弾，など）だと，
        # 結局 O(H*W) で間に合わなそう。3秒あるけど 10^10 じゃあなあ。
        # DP ぽくはあるが，どう DP を作るかだ。

    # h, w にでいくつ爆破できるか。
    # dp = [[0] * width for _ in range(height)]
    # dp[0][0] = count_by_height[0] + count_by_width[0] - bomb_is[0][0]
    ans = 0
    for x in range(height):
        for y in range(width):
            now = count_by_height[x] + count_by_width[y] - bomb_is[x][y]
            ans = max(ans, now)
            # if x < height - 1:
            #     dp[x + 1][y] = (
            #         now + count_by_height[x + 1] - count_by_height[x])
            # if y < width - 1:
            #     dp[x][y + 1] = (
            #         now + count_by_width[y + 1] - count_by_width[y])
    # print(dp)
    return ans


if __name__ == '__main__':
    ans = main()
    print(ans)


### FIXED CODE ###

from collections import defaultdict


def main():
    height, width, target_count = [int(x) for x in input().split()]
    count_by_height = defaultdict(int)
    count_by_width = defaultdict(int)
    bomb_is = set()
    for _ in range(target_count):
        bom_h, bom_w = [int(x) - 1 for x in input().split()]
        count_by_height[bom_h] += 1
        count_by_width[bom_w] += 1
        bomb_is.add((bom_h, bom_w))
    max_h = max(v for v in count_by_height.values())
    max_w = max(v for v in count_by_width.values())
    max_h_index = [i for i, x in count_by_height.items() if x == max_h]
    max_w_index = [i for i, x in count_by_width.items() if x == max_w]
    no_cross = any(
        (hh, ww) not in bomb_is for hh in max_h_index for ww in max_w_index)
    return max_h + max_w - (not no_cross)


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

N,Q = map(int,input().split())
c = [-1]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for i in range(Q):
    l,r = map(int,input().split())
    queries.append(r*10**15+l*10**8+i)
queries.sort()
curR = 0
#A1 ... AnのBIT(1-indexed)
BIT = [0]*(N+1)

#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return
for j in range(Q):
    SUM = queries[j]
    r = SUM // 10**15
    SUM %= 10**15
    l = SUM // 10**8
    SUM %= 10**8
    i =SUM
    while curR < r:
        curR += 1
        last = lastAppeared[c[curR]]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[c[curR]] = curR
        BIT_update(curR,1)
    ans[i] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])

### FIXED CODE ###

N,Q = map(int,input().split())
BIT = [0]*(N+1)

def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [-1]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for q in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,q))
queries.sort(key = lambda x:x[1])

curR = 0
for i in range(Q):
    l,r,q = queries[i]
    while curR < r:
        curR += 1
        new = c[curR]
        last = lastAppeared[new]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[new] = curR
        BIT_update(curR,1)
    ans[q] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])
### BUGGY CODE ###

import numpy as np

n, m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()

if n >= m:
    print(0)
else:
    npx = np.array(x)
    li = list(np.diff(npx, n = 1))

    for i in range(n-1):
        li.remove(max(li))

    print(sum(li))


### FIXED CODE ###

import numpy as np
import heapq

n, m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()

if n >= m:
    print(0)
else:
    npx = np.array(x)
    li = list(np.diff(npx, n = 1))

    print(sum(heapq.nsmallest(len(li)-n+1, li)))
### BUGGY CODE ###

S = input()

count = 0
mod_check = [0] * 2019
mod_check[0] = 1
check_S = 0
for i in reversed(S):
    check_S += int(i) * (10 ** count)
    mod = check_S % 2019
    # mod_check.setdefault(mod, 0)
    mod_check[mod] += 1
    count += 1
mod_match = 0
for x in mod_check:
    mod_match += x * (x - 1) // 2
print(mod_match)


### FIXED CODE ###

S = input()

count = 0
mod_check = [0] * 2019
mod_check[0] = 1
check_S = 0
d = 1
for i in reversed(S):
    check_S += int(i) * d
    check_S %= 2019
    mod_check[check_S] += 1
    d *= 10
    d %= 2019
    count += 1
mod_match = 0
for x in mod_check:
    mod_match += x * (x - 1) // 2
print(mod_match)
### BUGGY CODE ###

import numpy as np

h, w, k = map(int, input().split())
s = []
for i in range(h):
    string = input()
    temp = []
    for j in range(w):
        temp.append(int(string[j]))
    s.append(temp)

s_arr = np.array(s)

ans = 10**9
for i in range(2**(h-1)):
    bin_str = format(i, '0'+str(h-1)+'b')
    kouryo = np.array([[0 for _ in range(w)]])
    cnt = 0
    start = 0
    for j in range(h-1):
        if bin_str[j] == '1':
            cnt += 1
            kouryo = np.concatenate((kouryo, s_arr[start:j+1].sum(axis=0, keepdims=True)), axis=0)
            start=j+1
    kouryo = np.concatenate((kouryo, s_arr[start:].sum(axis=0, keepdims=True)), axis=0)

    wa = np.array([0 for _ in range(len(kouryo))])
    for j in range(w):
        if np.any(kouryo[:, j]>k): cnt += 10**9
        if cnt >= 10**9: break
        wa = wa + kouryo[:, j]
        if np.any(wa>k):
            cnt += 1
            wa = kouryo[:, j]
    ans = min(ans, cnt)
print(ans)

### FIXED CODE ###

import numpy as np

h, w, k = map(int, input().split())
s = []
for i in range(h):
    string = input()
    temp = []
    for j in range(w):
        temp.append(int(string[j]))
    s.append(temp)

s_arr = np.array(s)

ans = 10**9
for i in range(2**(h-1)):
    bin_str = format(i, '0'+str(h-1)+'b')
    kouryo = np.array([[0 for _ in range(w)]])
    cnt = 0
    start = 0
    for j in range(h-1):
        if bin_str[j] == '1':
            cnt += 1
            kouryo = np.concatenate((kouryo, s_arr[start:j+1].sum(axis=0, keepdims=True)), axis=0)
            start=j+1
    kouryo = np.concatenate((kouryo, s_arr[start:].sum(axis=0, keepdims=True)), axis=0)

    if cnt > ans: continue
    if np.any(kouryo>k): continue

    wa = np.array([0 for _ in range(len(kouryo))])
    for j in range(w):
        wa += kouryo[:, j]
        if np.max(wa)>k:
            cnt += 1
            if cnt > ans: break
            wa = kouryo[:, j]
    ans = min(ans, cnt)
print(ans)
### BUGGY CODE ###

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

# dp[i][j][k]: 寿司が残り1個の皿がi枚, 残り2個の皿がj枚, 残り3個の皿がk枚から寿司をすべてなくす操作回数の期待値
dp = [[[0 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]

one = A.count(1)
two = A.count(2)
three = A.count(3)

# i, j, kを全通り回す
for k in range(three + 1):
    # 3個の皿がk個のとき
    for j in range(two + three - k + 1):
        # 2枚の皿は
        # 初期のtwo
        # 3個の皿がk枚のとき、three-k枚が2枚になっている
        for i in range(one + (two + (three - k) - j) + 1):
            # 1枚の皿は
            # 初期のone
            # 3枚の皿がk枚、2枚の皿がj枚のとき、two+three-k-j枚が1枚になっている
            if i == 0 and j == 0 and k == 0:
                continue
            tmp = n
            if i > 0:
                tmp += i * dp[i - 1][j][k]
            if j > 0:
                tmp += j * dp[i + 1][j - 1][k]
            if k > 0:
                tmp += k * dp[i][j + 1][k - 1]
            
            dp[i][j][k] = tmp / (i + j + k)

print(dp[i][j][k])

### FIXED CODE ###

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

# dp[i][j][k]: 寿司が残り1個の皿がi枚, 残り2個の皿がj枚, 残り3個の皿がk枚から寿司をすべてなくす操作回数の期待値
dp = [[[0.0 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]

one = A.count(1)
two = A.count(2)
three = A.count(3)

# i, j, kを全通り回す
for k in range(three + 1):
    # 3個の皿がk個のとき
    for j in range(two + three - k + 1):
        # 2枚の皿は
        # 初期のtwo
        # 3個の皿がk枚のとき、three-k枚が2枚になっている
        for i in range(one + two + three - k - j + 1):
            # 1枚の皿は
            # 初期のone
            # 3枚の皿がk枚、2枚の皿がj枚のとき、two+three-k-j枚が1枚になっている
            if i == 0 and j == 0 and k == 0:
                continue
            tmp = 1.0*n
            if i > 0:
                tmp += i * dp[i - 1][j][k]
            if j > 0:
                tmp += j * dp[i + 1][j - 1][k]
            if k > 0:
                tmp += k * dp[i][j + 1][k - 1]
            
            dp[i][j][k] = tmp / (i + j + k)

print(dp[one][two][three])
### BUGGY CODE ###

from itertools import accumulate 
n, k = map(int, input().split())
p = [int(x) - 1 for x in input().split()]
c = list(map(int, input().split()))
ans = -(10 ** 18)
 
for i in range(n):
    pos = i
    scores = []
    while True:
        pos = p[pos]
        scores.append(c[pos])
        if pos == i:
            break
    m = len(scores)
    s = list(accumulate(scores))
    for j in range(min(m, k)):
        x = (k - j - 1) // m
        ans = max(ans, s[j], s[j] + s[-1] * x)
 
print(ans)

### FIXED CODE ###

from itertools import accumulate 
#acumulate [a[0], a[0]+a[1], a[0]+...]
 
n, k = map(int, input().split())
p = [int(x) - 1 for x in input().split()]
c = list(map(int, input().split()))
ans = -(10 ** 18)
 
for i in range(n):
    pos = i
    scores = []
    while True:
        pos = p[pos]
        scores.append(c[pos])
        if pos == i:
            break
    m = len(scores)
    s = list(accumulate(scores))
    for j in range(min(m, k)):
        x = (k - j - 1) // m
        ans = max(ans, s[j], s[j] + s[-1] * x)
 
print(ans)
### BUGGY CODE ###

s=input()
x,y=map(int,input().split())
XY=[[]for i in range(2)]
a=0
b=0
for i in range(len(s)):
  if s[i]=="T":
    XY[b].append(a)
    a=0
    b=(b+1)%2
  else:
    a=a+1
XY[b].append(a)
xx=sum(XY[0])
yy=sum(XY[1])
dpx=[[0]*(2*xx+5) for i in range(len(XY[0])+1)]#x=0とj=xx+2を対応させる
dpy=[[0]*(2*yy+5) for i in range(len(XY[1])+1)]#y=0とj=yy+2を対応させる
dpx[1][xx+XY[0][0]+2]=1
for i in range(1,len(XY[0])):
  for j in range(2*xx+5):
    if dpx[i][j]==1:
      dpx[i+1][j-XY[0][i]]=1
      dpx[i+1][j+XY[0][i]]=1
dpy[0][yy+2]=1
for i in range(len(XY[1])):
  for j in range(2*yy+5):
    if dpy[i][j]==1:
      dpy[i+1][j-XY[1][i]]=1
      dpy[i+1][j+XY[1][i]]=1
if x+xx+2<0 or 2*xx+4<x+xx+2 or y+yy+2<0 or 2*yy+4<y+yy+2:
  print("No")
  exit()
if dpx[-1][x+xx+2]==1 and dpy[-1][y+yy+2]==1:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

s=input()
x,y=map(int,input().split())
XY=[[]for i in range(2)]
a=0
b=0
for i in range(len(s)):
  if s[i]=="T":
    XY[b].append(a)
    a=0
    b=(b+1)%2
  else:
    a=a+1
XY[b].append(a)
xx=sum(XY[0])
yy=sum(XY[1])
dpx=[[0]*(2*xx+5) for i in range(len(XY[0])+1)]#x=0とj=xx+2を対応させる
dpy=[[0]*(2*yy+5) for i in range(len(XY[1])+1)]#y=0とj=yy+2を対応させる
dpx[1][xx+XY[0][0]+2]=1
for i in range(1,len(XY[0])):
  for j in range(2*xx+5):
    if dpx[i][j]==1:
      dpx[i+1][j-XY[0][i]]=1
      dpx[i+1][j+XY[0][i]]=1
dpy[0][yy+2]=1
for i in range(len(XY[1])):
  for j in range(2*yy+5):
    if dpy[i][j]==1:
      dpy[i+1][j-XY[1][i]]=1
      dpy[i+1][j+XY[1][i]]=1
if x+xx+2<0 or 2*xx+4<x+xx+2 or y+yy+2<0 or 2*yy+4<y+yy+2:
  print("No")
  exit()
if dpx[-1][x+xx+2]==1 and dpy[-1][y+yy+2]==1:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

from collections import deque as dq
L=dq(list(input()))
for _ in range(int(input())):
    S=input().split()
    if S == ['1']:
        L.reverse()
    else:
        if S[1]=='1':
        	L.appendleft(S[2])
        else:
        	L.append(S[2])
print(''.join(L))
          
          

### FIXED CODE ###

import os
import sys
from io import BytesIO, IOBase
from collections import deque as dq

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
##############################################################################
from collections import deque as dq
L=dq(list(input()))
C=0
for _ in range(int(input())):
    S=input().split()
    if S == ['1']:
        C+=1
    elif C%2==0:
        if S[1]=='1':
        	L.appendleft(S[2])
        else:
        	L.append(S[2])
    elif C%2!=0:
        if S[1]=='1':
        	L.append(S[2])
        else:
        	L.appendleft(S[2])
if C%2!=0:
    L.reverse()
print(''.join(L))
### BUGGY CODE ###

from collections import deque

def hoge(A,B):
    sum = 0
    for i in range(B):
        sum += A
        A -= 1
    return sum

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

L.sort(reverse=True)

List = deque()
Sum = 0

for i in range(1, N - 1):
    for j in range(i + 1, N):
        List.append(L[i] + L[j])

for i in range(N - 2):
    for j in range(hoge(N-2,i),len(List)):
        if List[j] > L[i]:
            Sum += 1

print(Sum)

### FIXED CODE ###

import bisect

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

Sum = 0
L.sort(reverse=False)

for i in reversed(range(2,N)):
    for j in reversed(range(1,i)):
        hoge = 0
        hoge = j - bisect.bisect(L, L[i] - L[j])
        if hoge < 0:
            hoge = 0
        Sum += hoge

print(Sum)
### BUGGY CODE ###

s = input()

prev = []
for i in range(len(s)):
    prev.append(s[i])
while True:
    result = []
    i = 0
    while i < (len(prev)-1):
        if prev[i] != prev[i+1]:
            i += 2
        else:
            result.append(prev[i])
            i += 1
    if i == (len(prev) - 1):
        result.append(prev[-1])
    if prev == result:
        break
    prev = result
print(len(s) - len(result))


### FIXED CODE ###

s = input()
count = 0
for i in s:
    count += 1 if '1' == i else -1
print(len(s) - abs(count))
### BUGGY CODE ###

from bisect import bisect_left
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
AB = [[int(i) for i in input().split()] for _ in range(N)]

AB.sort(key=lambda x: x[1], reverse=True)

s = [i for i in range(1, M + 1)]
ret = 0
for a, b in AB :
    if a > s[-1] :
        continue
    
    a = bisect_left(s, a)
    s = s[:a] + s[a+1:]
    ret += b
    if not s :
        break
print(ret)


### FIXED CODE ###

from heapq import heappush, heappop

N, M = map(int, input().split())
AB = [[] for _ in range(M+1)]

for _ in range(N) :
    a, b = map(int, input().split())
    if a <= M :
        AB[M-a].append(b)
    
q = []
for a in range(M+1) :
    for b in AB[a] :
        heappush(q, b)
        if len(q) > a + 1 :
            heappop(q)
            
print(sum(q))
### BUGGY CODE ###

import math

k = int(input())
mp = [[-1] * k for _ in range(k)]

c1, c2 = 0, 0


def gcd(a, b):
    global c1, c2
    if b == 0:
        return a
    if mp[a - 1][b - 1] == -1:
        mp[a - 1][b - 1] = gcd(b, a % b)
        c1 += 1
        return mp[a - 1][b - 1]
    c2 += 1
    return mp[a - 1][b - 1]


ans = 0

for i in range(1, k + 1):
    for j in range(1, k + 1):
        for k in range(1, k + 1):
            ans += gcd(k, gcd(j, i))

print(ans)

### FIXED CODE ###

import math

k = int(input())
mp = [[-1] * k for _ in range(k)]

def gcd(a, b):
    if b == 0:
        return a
    if mp[a - 1][b - 1] == -1:
        mp[a - 1][b - 1] = gcd(b, a % b)
        return mp[a - 1][b - 1]
    return mp[a - 1][b - 1]


ans = 0

for i in range(1, k + 1):
    for j in range(1, k + 1):
        for k in range(1, k + 1):
            ans += gcd(k, gcd(j, i))

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

n, k = [int(item) for item in input().split()]
a = sorted([int(item) for item in input().split()], reverse=True)
max_k = min(sum(a), 5000)

def check_needed(index):
    memo = [[0] * (max_k + 1) for _ in range(n+1)]
    memo[0][0] = 1
    for i in range(n):
        for j in range(max_k + 1):
            if memo[i][j] == 1: 
                memo[i+1][j] = 1 
                if i != index and j+a[i] <= max_k:
                    memo[i+1][j+a[i]] = 1 
    return (1 in memo[n][max(k-a[index], 0):k])

l = -1
r = n
while r-l > 1:
    mid = (l+r) // 2
    if not check_needed(mid):
        r = mid
    else:
        l = mid
if sum(a) < k:
    print(n)
else:
    print(n - r)

### FIXED CODE ###

n, k = [int(item) for item in input().split()]
a = sorted([int(item) for item in input().split()], reverse=True)

count = 0
asum = 0
for item in a:
    if asum + item < k:
        asum += item
        count += 1
    else:
        count = 0

print(count)
### BUGGY CODE ###

a,b,c,d,e,f = map(int,input().split())
A =a* 100
B =b* 100
l = []
for i in range(f//A+1):
    for j in range(f//B+1):
        if i*A+j*B <=f:
            W = i*A+j*B
            s = (W//100)*e
            # print(s)
            r = f - W
            for I in range(s//c+1):
                for J in range(s//d+1):
                    if I*c + J*d<=s and I*c + J*d+W <= f and W>0:
                        S =I*c + J*d
                        l.append([100*S/(W+S),W+S,S])
l.sort()

l = l[::-1]
# print(l[:10])
print(l[0][1],l[0][2])

### FIXED CODE ###

a,b,c,d,e,f = map(int,input().split())
A =a* 100
B =b* 100
l = []
for i in range(f//A+1):
    for j in range(f//B+1):
        if i*A+j*B <=f:
            W = i*A+j*B
            s = (W//100)*e
            # print(s)
            r = f - W
            for I in range(s//c+1):
                for J in range(s//d+1):
                    if I*c + J*d<=s and I*c + J*d+W <= f and W>0:
                        S =I*c + J*d
                        l.append([100*S/(W+S),W+S,S])
l.sort()

l = l[::-1]
# print(l[:10])
print(l[0][1],l[0][2])
### BUGGY CODE ###

N, X, M = map(int, input().split())
NN = N
li = []
while X not in li and N != 0:
    li.append(X)
    X = X ** 2 % M
    N -= 1
    
if N == 0:
    print(sum(x for x in li))

elif N != 0 and X in li:
    l = len(li)
    s = li.index(X)
    T = l - s
    q = (NN - s) // T
    r = (NN - s) % T
    print(sum(li[i] for i in range(s)) + sum(li[i] for i in range(s, len(li))) * q
              + sum(li[i] for i in range(s, s + r)))

### FIXED CODE ###

N, X, M = map(int, input().split())
NN = N
li = []
isused = [False] * M
while isused[X] == False and N != 0:
    li.append(X)
    isused[X] = True
    X = (X ** 2) % M
    N -= 1
    
if N == 0:
    print(sum(li))

elif N != 0 and X in li:
    l = len(li)
    s = li.index(X)
    T = l - s
    q = (NN - s) // T
    r = (NN - s) % T
    print(sum(li) + sum(li[i] for i in range(s, len(li))) * (q-1) + sum(li[i] for i in range(s, s + r)))
### BUGGY CODE ###

N = int(input())
X = str(input())
X10 = int(X,2)

one_num = X.count("1")

for i in range(N):
    target = int(X[i])
    if target == 0:
        plus = pow(2,N-i-1)
        ones = one_num + 1
    else:
        plus = -pow(2,N-i-1)
        ones = one_num-1
    Xnow = X10+plus
    count = 0
    if Xnow == 0:
        print(count)
        continue
    Xnow = Xnow%ones
    count+=1
    for j in range(1000):
        if Xnow == 0:
            break
        Xnow2 = bin(Xnow)
        ones = Xnow2.count("1")
        Xnow = Xnow%ones
        count+=1
    print(count)


### FIXED CODE ###

N = int(input())
x2 = input()
x10 = int(x2, 2)
popc =  x2.count("1")
#print("x10", x10)
#print("popc", popc)
#popc: Nを2進数で表したときの1の個数

#以下で1つフリップさせた時の入力に対する余りを事前に計算
if popc <= 1:
    xp = x10%(popc+1)
    xm = 0
else:
    xp = x10%(popc+1)
    xm = x10%(popc-1)
#print("xp", xp)
#print("xm", xm)

#以下でフリップさせた場所のみを計算
for i in range(N):
    if x2[i] == "1":
        if popc == 1:
            print(0)
            continue
        tmp = (xm - pow(2, N-i-1, popc-1))%(popc-1)
    else:
        tmp = (xp + pow(2, N-i-1, popc+1))%(popc+1)
        
    #print("tmp", tmp)
    ans = 1
    while tmp > 0:
        tmp %= bin(tmp).count("1")
        ans += 1
    print(ans)