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

N = int(input())
X = str(input())

from functools import lru_cache


@lru_cache(maxsize=200000)
def popcount(bits: str):
    return len([elm for elm in bits if elm == '1'])


@lru_cache(maxsize=100000000000)
def mod(a, b):
    return a % b

@lru_cache(maxsize=1000000000)
def f(num):
    if num == 0:
        return 0
    else:
        # if not cache.get(num % pc, None) is None:
        #     return cache[num % pc]
        # pc = popcount('{:b}'.format(num))
        pc = popcount(''.join(sorted('{:b}'.format(num))))
        ret = 1 + f(mod(num, pc))
        # cache[num % pc] = ret
        return ret


def reverse_bit(bits: str, digit):
    def toggle(a):
        if a == '1':
            return '0'
        else:
            return '1'

    ret = list(bits)
    ret[digit-1] = toggle(bits[digit-1])
    return ''.join(ret)

def convert(x: str):
    ans = 0
    i = 0
    for elm in list(x)[::-1]:
        if elm == '1':
            ans += 2 ** i
        i += 1
    return ans


answers = {}

for i in range(1, N+1):
    bits = reverse_bit(X, i)
    # pc = popcount(bits)
    # print(f'# {bits} {convert(bits)} {pc}')
    x = convert(bits)
    if not answers.get(x, None) is None:
        print(answers[x])
        continue
    ret = f(x)
    answers[x] = ret
    print(ret)

### FIXED CODE ###

n = int(input())
# for i in range(n):
#     print('0', end='')
# print(flush=True)
s = input()
x = int(s, base=2)
popcount = s.count('1')
y_zero = x % (popcount + 1)
if popcount > 1:
    y_one = x % (popcount - 1)
dp = [-1] * n
dp[0] = 0
 
 
def calc(y):
    if dp[y] != -1:
        return dp[y]
    dp[y] = 1 + calc(y % bin(y).count('1'))
    return dp[y]
 
 
ans = [0] * n
rem_zero = 1
if popcount > 1:
    rem_one = popcount - 2
for i in range(n):
    if s[n - 1 - i] == '0':
        ans[n - 1 - i] = 1 + calc((y_zero + rem_zero) % (popcount + 1))
    elif popcount > 1:
        ans[n - 1 - i] = 1 + calc((y_one + rem_one) % (popcount - 1))
    else:
        ans[n - 1 - i] = 0
    rem_zero = rem_zero * 2 % (popcount + 1)
    if popcount > 1:
        rem_one = rem_one * 2 % (popcount - 1)
for i in range(n):
    print(ans[i])
### BUGGY CODE ###

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

from collections import deque
s = deque(s)

for qi in q:
    if qi[0] == "1":
        s.reverse()
    if len(qi) != 1:
        if qi[1] == '1':
            s.appendleft(qi[2])
        elif qi[1] == "2":
            s.append(qi[2])
print(''.join(s))

### FIXED CODE ###

from collections import deque

s = deque(input())
q = int(input())
flg = 0

for _ in range(q):
  Q = [x for x in input().split()]
  if Q[0] == '1':
    flg += 1
  else:
    if (Q[1] == '1' and flg%2==0) or (Q[1] == '2' and flg%2==1):
      s.appendleft(Q[2])
    else:
      s.append(Q[2])
if flg%2==1:
  s.reverse()

print('' . join(s))
### BUGGY CODE ###

x = int(input())
div = []
for i in range(1, int(x**0.5)+1):
    if x % i == 0:
        div.append(i)
        if i != x // i:
            div.append(x//i)

def f():
    for d in div:
        a = 0
        while True:
            b = a - d
            if a**5 - b**5 == x:
                return a, b
            elif b > 0 and a**5 - b**5 > x:
                break
            a += 1

print(*f())

### FIXED CODE ###

x = int(input())

def f():
    for a in range(1, 200):
        for b in range(-200, a):
            if a**5 - b**5 == x:
                print(a, b)
                return

f()
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = "YES"
for i in range(n):
    for j in range(n-i-1):
        if a[i] == a[i+j+1]:
            ans = "NO"
            break

print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = "YES"
a.sort()
for i in range(n-1):
    if a[i] == a[i+1]:
        ans="NO"
print(ans)
### BUGGY CODE ###

X, Y, A, B, C = map(int, input().split())

p = sorted(list(map(int,input().split())))[-X:]
q = sorted(list(map(int,input().split())))[-Y:]
r = sorted(list(map(int,input().split())), reverse=True)

for i in r:
    p_min = p[0]
    q_min = q[0]

    if p_min > i and q_min > i:
        break

    p_min_diff = i - p_min
    q_min_diff = i - q_min

    if p_min_diff > q_min_diff and p_min_diff > 0:
        p.remove(p_min)
        p.append(i)
    elif q_min_diff >= p_min_diff and q_min_diff > 0:
        q.remove(q_min)
        q.append(i)

print(sum(p) + sum(q))

### FIXED CODE ###

X, Y, A, B, C = map(int, input().split())
 
p = sorted(list(map(int,input().split())), reverse=True)[:X]
q = sorted(list(map(int,input().split())), reverse=True)[:Y]
r = sorted(list(map(int,input().split())), reverse=True)
 
colored_p = []
colored_q = []
 
for i in r:
    p_min = p[len(p) - 1] if len(p) > 0 else colored_p[len(colored_p) - 1]
    q_min = q[len(q) - 1] if len(q) > 0 else colored_q[len(colored_q) - 1]
 
    if p_min > i and q_min > i:
        break
 
    p_min_diff = i - p_min
    q_min_diff = i - q_min
 
    if p_min_diff >= q_min_diff and p_min_diff > 0:
        if len(p) > 0:
            p.pop()
        colored_p.append(i)
    elif q_min_diff >= p_min_diff and q_min_diff > 0:
        if len(q) > 0:
            q.pop()
        colored_q.append(i)
 
print(sum(p) + sum(q) + sum(colored_p) + sum(colored_q))
### BUGGY CODE ###

n, k = map(int, input().split())
h = [0] + list(map(int, input().split())) + [float("inf")]*(k+1)
dp = [float("inf")]*(n+k+1)
dp[0], dp[1] = 0, 0
for i in range(1,n):
    for j in range(1, k+1):
        dp[i+j] = min(dp[i+j], dp[i] + abs(h[i+j]-h[i]))
print(dp[n])

### FIXED CODE ###

n, k = map(int, input().split())
h = [0] + list(map(int, input().split())) + [float("inf")]*(k+1)
dp = [float("inf")]*(n+k+1)
dp[0], dp[1] = 0, 0
for i in range(1,n):
    for j in range(1, k+1):
        dp[i+j] = min(dp[i+j], dp[i] + abs(h[i+j]-h[i]))
print(dp[n])
### BUGGY CODE ###

S = input()

MOD = 10**9+7

dp = [[0 for _ in range(13)] for _ in range(len(S) + 1)]


dp[0][0] = 1

for index in range(1, len(S) + 1):
    s = S[len(S) - index ]
    mul = (10 ** (index - 1)) % 13
    if s == '?':
        for pre_index in range(13):
            for i in range(10):
                next_i = (i * mul  +  pre_index ) % 13
                dp[index][next_i] += dp[index - 1][pre_index] 
    else:
        i = int(s)
        for pre_index in range(13):
            next_i = (i * mul +  pre_index ) % 13
            dp[index][next_i] += dp[index - 1][pre_index] 

    for i in range(13):
        dp[index][i] %= MOD



print(dp[len(S)][5])



### FIXED CODE ###

S = input()
 
MOD = 10**9+7
 
dp = [[0]*13 for _ in range(len(S) + 1)]
 
 
dp[0][0] = 1
 
for index in range(len(S)):
    if S[index] == '?':
        for pre_index in range(13):
            for i in range(10):
                next_i = (i +  pre_index * 10 ) % 13
                dp[index+1][next_i] += dp[index][pre_index] 
                dp[index+1][next_i] %= MOD

    else:
        for pre_index in range(13):
            i = int(S[index])
            next_i = (i +  pre_index  * 10) % 13
            dp[index+1][next_i] += dp[index][pre_index] 
            dp[index+1][next_i] %= MOD
 
 
 
print(dp[len(S)][5])
### BUGGY CODE ###

N = int(input())
Y = [[] for _ in range(26)]
c = 0

for i in range(N):
    s = input()
    o = ord(s[0])-97
    if s not in Y[o]:
        Y[o].append(s)
        c += 1
# print(Y)
print(c)

### FIXED CODE ###

N = int(input())
Y = []
for i in range(N):
    Y.append(input())
print(len(set(Y)))
### BUGGY CODE ###

(h,n),*c=[[*map(int,i.split())]for i in open(0)]
dp=[10**9]*(2*10**4+1)
c.sort()
dp[0]=0
for i in range(h):
    for a,b in c:
        if i+a<=2*10**4:
            dp[i+a]=min(dp[i+a],dp[i]+b)
        else:break    
print(min(dp[h:]))

### FIXED CODE ###

(h,n),*c=[[*map(int,i.split())]for i in open(0)]
dp=[10**9]*(2*10**4+1)
c.sort()
dp[0]=0
for i in range(h):
    for a,b in c:
        if i+a<=2*10**4:
            dp[i+a]=min(dp[i+a],dp[i]+b)
        else:break    
print(min(dp[h:]))
### BUGGY CODE ###

s = str(input())
q = int(input())
for i in range(q):
    l = list(map(str, input().split()))
    if l[0] == '1':
        s = s[::-1]
    elif l[0] == '2' and l[1] == '1':
        s = l[2] + s
    elif l[0] == '2' and l[1] == '2':
        s = s + l[2]
print(s)

### FIXED CODE ###

import sys
from collections import deque

readline = sys.stdin.readline
readlines = sys.stdin.readlines

s = readline().rstrip()
q = readline()
queries = readlines()
s = deque(s)
tot_1 = 0
for i in queries:
    if i[0] == '1':
        tot_1 += 1
        continue
    c = i[4]
    if (tot_1 + int(i[2])) % 2 == 0:
        s.append(c)
    else:
        s.appendleft(c)
ans = "".join(s) if tot_1 % 2 == 0 else "".join(reversed(s))
print(ans)
### BUGGY CODE ###

X = int(input())

A = X // 100

for i_100 in range(A + 1):
    for i_101 in range(A + 1 - i_100):
        for i_102 in range(A + 1 - i_100 - i_101):
            for i_103 in range(A + 1 - i_100 - i_101 - i_102):
                for i_104 in range(A + 1 - i_100 - i_101 - i_102 - i_103):
                    for i_105 in range(A + 1 - i_100 - i_101 - i_102 - i_103 - i_104):
                        if i_100 + i_101 + i_102 + i_103 + i_104 + i_105 == A:
                            if i_100 * 100 + i_101 * 101 + i_102 * 102 + i_103 * 103 + i_104 * 104 + i_105 * 105 == X:
                                print("1")
                                exit()

print("0")




### FIXED CODE ###

X = int(input())

A100 = 0
A105 = 0
for i in range(1001):
    A100 += 100
    A105 += 105
    if A100 <= X <= A105:
        print("1")
        exit()

print("0")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

from math import gcd

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

def eratosthenes(limit):
    import math
    if not isinstance(limit, int):
        raise TypeError('n is int type.')
    if limit < 2:
        raise ValueError('n is more than 2')
    prime = []
    sqrt_limit = math.sqrt(limit)
    prime_numbers_list = [i + 1 for i in range(1, limit)]
    while True:
        p = prime_numbers_list[0]
        if sqrt_limit <= p:
            return prime + prime_numbers_list
        prime.append(p)
        prime_numbers_list = [e for e in prime_numbers_list if e % p != 0]
    return prime_numbers_list

def main():
    a.sort()

    g = 0
    for aa in a:
        g = gcd(g,aa)
    if g > 1:
        print('not coprime')
        exit()

    if a[-1]==1:
        print('pairwise coprime')
        exit()

    prime_numbers_list = eratosthenes(a[-1])
    count = [0]*len(prime_numbers_list)

    for aa in a:
        for i, prime in enumerate(prime_numbers_list):
            if aa % prime ==0:
                count[i] += 1
                if count[i]==2:
                    print('setwise coprime')
                    exit()
                break

    print('pairwise coprime')

main()




### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

from math import gcd
n = int(input())
a = list( map(int, input().split()))


g = 0
for aa in a:
    g = gcd(g,aa)
if g > 1:
    print('not coprime')
    exit()

MAXN = 10**6+10

def eratosthenes3(limit):
    sieve = [i for i in range(limit+1)]
    p = 2
    while p*p <= limit:
        if sieve[p] == p:
            for q in range(2*p,limit+1,p):
                if sieve[q] == q:
                    sieve[q] = p
        p += 1

    return sieve

sieve = eratosthenes3(MAXN)

st = set()
for aa in a:
    tmp = set()
    while aa > 1:
        tmp.add(sieve[aa])
        aa //= sieve[aa]
    for p in tmp:
        if p in st:
            print('setwise coprime')
            exit()
        st.add(p)
print('pairwise coprime')
### BUGGY CODE ###

n,c = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
ab = list(zip(a,b))
dp = [[0 for i in range(c+1)] for j in range(n+1)]
mod = 10**9+7
for i in range(c+1):
  dp[0][i] = 1
for i in range(1,n+1):
  a,b = ab[i-1]
  for j in range(a,b+1):
    for k in range(c+1):
      dp[i][k] = (dp[i][k]+pow(j,k,mod))%mod
ans = [[0 for i in range(c+1)] for j in range(n+1)]
ans[0][0] = 1
for i in range(1,n+1):
  for j in range(c+1):
    for k in range(j+1):
      ans[i][j] += dp[i][k]*ans[i-1][j-k]
    ans[i][j] %= mod
print(ans[n][c])

### FIXED CODE ###

n,c = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
ab = list(zip(a,b))
table = [[0 for i in range(c+1)] for j in range(401)]
mod = 10**9+7
for j in range(c+1):
  if j == 0:
    for i in range(401):
      table[i][j] = 1
  else:
    for i in range(401):
      table[i][j] = table[i][j-1]*i%mod
dp = [[0 for i in range(c+1)] for j in range(n+1)]
for i in range(c+1):
  dp[0][i] = 1
for i in range(1,n+1):
  a,b = ab[i-1]
  for j in range(a,b+1):
    for k in range(c+1):
      dp[i][k] = (dp[i][k]+table[j][k])%mod
ans = [[0 for i in range(c+1)] for j in range(n+1)]
ans[0][0] = 1
for i in range(1,n+1):
  for j in range(c+1):
    for k in range(j+1):
      ans[i][j] = (ans[i][j]+dp[i][k]*ans[i-1][j-k])%mod
print(ans[n][c])
### BUGGY CODE ###

import math
from decimal import *
mod = 10 ** 9 + 7


N = int(input())

sosuu = []
for i in range(2, N+1):
    for j in range(2,i+1):
        if j == i:
            sosuu.append(i)
        if i % j == 0:
            break


soinsuu_num = [0 for i in range(len(sosuu))]

for i in range(1, N+1):
    if i == 1:
        continue
    temp = i
    for j in range(len(sosuu)):
        while temp % sosuu[j] == 0 and temp != 1:
            soinsuu_num[j] += 1
            temp = Decimal(temp) / Decimal(sosuu[j])

ans = 1
for i in soinsuu_num:
    if i != 0:
        ans = ans * (i + 1) % mod

print(ans)

### FIXED CODE ###

import math
from decimal import *
mod = 10 ** 9 + 7


N = int(input())

sosuu = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
for i in range(2, N+1):
    if i % 2 == 0 or i % 3 == 0 or i == 5 or i % 7 == 0 or i % 11 == 0 or i%13 == 0 or i%17 == 0\
            or i%19 == 0 or i%23 == 0 or i%29 == 0 or i%31 == 0 or i%37 == 0:
        continue
    for j in range(2,i+1):
        if j == i:
            sosuu.append(i)
        if i % j == 0:
            break

soinsuu_num = [0 for i in range(len(sosuu))]

for i in range(1, N+1):
    if i == 1:
        continue
    temp = i
    for j in range(len(sosuu)):
        while temp % sosuu[j] == 0 and temp != 1:
            soinsuu_num[j] += 1
            temp = Decimal(temp) / Decimal(sosuu[j])
        if temp == 1:
            break

ans = 1
for i in soinsuu_num:
    if i != 0:
        ans = ans * (i + 1) % mod

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

N = int(input())
s = []
for i in range(N):
    s.append(list(input()))

ans = 0
for i in range(N):
    for j in range(N):
        if not i == j:
            si = sorted(s[i])
            sj = sorted(s[j])
            if (si == sj):
                ans += 1
print(int(ans/2))

### FIXED CODE ###

N = int(input())
s = []
ans = 0
mydict = {}
for i in range(N):
    s = "".join(sorted(list(input())))
    if (s in mydict.keys()):
        ans += mydict[s]
        mydict[s] += 1
    else:
        mydict[s] = 1
print(ans)
### BUGGY CODE ###

def main():
    s = input().rstrip()
    s = s[::-1] + "0"
    n = len(s)
    dp = [[10**18]*2 for _ in range(2)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(2):
            x = int(s[i]) + j
            if x < 10:
                dp[(i+1)%2][0] = min(dp[(i+1)%2][0], dp[i%2][j] + x + 0)
            if 0 < x:
                dp[(i+1)%2][1] = min(dp[(i+1)%2][1], dp[i%2][j] + 10 - x)
        for j in range(2):
            dp[i%2][j] = 10**18
    print(dp[n%2][0])

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    s = input().rstrip()
    s = "0" + s
    dp = [0, float("inf")]
    for c in s:
        x = int(c)
        dp = [min(dp[0] + x, dp[1] + (10-x)), min(dp[0] + x+1, dp[1] + (10-x) - 1)]
    print(dp[0])

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

def main ():
  N = int(input())
  A = list(map(int,input(). split ()))
  if 0 in A:
    print(0)
    return

  prod = 1
  for a in A:
    prod *= a

  if prod > 1000000000000000000:
    print(-1)
    return
  
  print(prod)
  
main ()

### FIXED CODE ###

def main ():
  count = int(input())
  c = list(map(int,input().split()))

  if 0 in c:
    print(0)
    return

  result = 1
  for a in c:
    result *= a
    if result > 1000000000000000000:
      print(-1)
      return

  print(result)

main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
mod = 10 ** 9 + 7
n, m, k = map(int, input().split())
nm = n * m
fact = [1] * (nm + 1)

for i in range(1, nm + 1):
    fact[i] = fact[i - 1] * i


def C(n, k):
    x = fact[n]
    x *= pow(fact[n-k], mod - 2, mod)
    x *= pow(fact[k], mod - 2, mod)
    return x


def F(x):
    s1 = x * x * (x + 1) // 2
    s2 = x * (x + 1) * (2 * x + 1) // 6
    return (s1 - s2)


res = (m ** 2 * F(n) + n ** 2 * F(m))
res *= C(n * m - 2, k - 2)
print(res % mod)


### FIXED CODE ###

# -*- coding: utf-8 -*-
mod = 10 ** 9 + 7
n, m, k = map(int, input().split())
nm = n * m
fact = [1] * (nm + 1)

for i in range(1, nm + 1):
    fact[i] = fact[i - 1] * i % mod


def C(n, k):
    x = fact[n]
    x *= pow(fact[n-k], mod - 2, mod)
    x %= mod
    x *= pow(fact[k], mod - 2, mod)
    x %= mod
    return x


def F(x):
    s1 = x * x * (x + 1) // 2
    s2 = x * (x + 1) * (2 * x + 1) // 6
    return (s1 - s2) % mod


res = (m ** 2 % mod * F(n) % mod + n ** 2 * F(m) % mod) % mod
res *= C(n * m - 2, k - 2)
res %= mod
print(res)
### BUGGY CODE ###

import bisect

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

A.sort()
B.sort()
C.sort()

ans = 0
for i in range(N):
    up = A[i]
    middleIndex = bisect.bisect(B, up)
    if middleIndex < N:
        for j in range(middleIndex, N):
            middle = B[j]
            lowIndex = bisect.bisect(C, middle)
            if lowIndex < N:
                cnt = N - lowIndex
                ans += cnt

print(ans)


### FIXED CODE ###

import bisect
import itertools

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

A.sort()
B.sort()
C.sort()

ans = 0
dp = [0] * N
for i in range(N):
    up = A[i]
    middleIndex = bisect.bisect(B, up)
    if middleIndex < N:
        if i == 0:
            for j in range(middleIndex, N):
                middle = B[j]
                lowIndex = bisect.bisect(C, middle)
                if lowIndex < N:
                    cnt = N - lowIndex
                    dp[j] = cnt
                    ans += cnt
                else:
                    dp[j] = 0
            dp = list(itertools.accumulate(dp[::-1]))
        else:
            ans += dp[-middleIndex-1]

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

n = int(input())
S = input()
p = 10**9+7
DP = [[0 for j in range(n+1)] for i in range(n+1)]
for j in range(n):
    DP[1][j] = 1
for i in range(2, n+1):
    A = [0]
    for j in range(n):
        A.append(A[-1]+DP[i-1][j])
    for j in range(n-i+1):
        if S[i-2] == '<':
            DP[i][j] = (A[n-(i-1)+1]-A[j+1]) % p
        else:
            DP[i][j] = A[j+1] % p
print(DP[n][0])


### FIXED CODE ###

n = int(input())
S = input()
p = 10**9+7
DP = [[0 for j in range(n+1)] for i in range(n+1)]
for j in range(n):
    DP[1][j] = 1
for i in range(2, n+1):
    A = [0]
    for j in range(n):
        A.append(A[-1]+DP[i-1][j])
    for j in range(n-i+1):
        if S[i-2] == '<':
            DP[i][j] = (A[n-(i-1)+1]-A[j+1]) % p
        else:
            DP[i][j] = A[j+1] % p
print(DP[n][0])
### BUGGY CODE ###

from collections import Counter
S = str(input())
N = len(S)

smod = [int(S[i:])%2019 for i in range(N)]
smod.append(0)

cmod = Counter(smod)

ans = 0
for i in cmod.values():
    ans += i*(i-1)/2
print(int(ans))

### FIXED CODE ###

from collections import Counter
S = str(input())
N = len(S)

#smod = [int(S[i:])%2019 for i in range(N)]
smod = [0]
tmod = 0
keta = 1
for i in range(N):
    temp = tmod + int(S[(N-1)-i])*keta
    #print(temp)
    tmod = temp%2019
    smod.append(tmod)
    keta = keta*10%2019


cmod = Counter(smod)
#print(cmod)

ans = 0
for i in cmod.values():
    ans += i*(i-1)/2
print(int(ans))
### BUGGY CODE ###

n, w = map(int, input().split())
W = []
V = []
for _ in range(n):
    s, t = map(int, input().split())
    W.append(s)
    V.append(t)

Dp = [[0 for _ in range(w+1)] for _ in range(n+1)]

for i in range(n):
    for j in range(w+1):
        #対象となる重さjよりも、見ているものの重さが小さい時
        if W[i] <= j:
            Dp[i+1][j] = max(Dp[i][j], Dp[i][j-W[i]]+V[i])
        else:
            Dp[i+1][j] = Dp[i][j]

ans = Dp[-1][-1]
print(ans)

### FIXED CODE ###

n, w = map(int, input().split())
W = []
V = []
for _ in range(n):
    s, t = map(int, input().split())
    W.append(s)
    V.append(t)

Dp = [[0 for _ in range(w+1)] for _ in range(n+1)]

for i in range(n):
    for j in range(w+1):
        #対象となる重さjよりも、見ているものの重さが小さい時
        if W[i] <= j:
            Dp[i+1][j] = max(Dp[i][j], Dp[i][j-W[i]]+V[i])
        else:
            Dp[i+1][j] = Dp[i][j]

ans = Dp[-1][-1]
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp =[1e10+5]*n
dp[0] = 0

for i in range(n):
    for j in range(1, k+1):
        if i-j < 0:
            break
        dp[i] = min(dp[i], dp[i-j] + abs(h[i] - h[i-j]))
print(dp[n-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp =[1e10+5]*n
dp[0] = 0

for i in range(n):
    for j in range(1, k+1):
        if i-j < 0:
            break
        dp[i] = min(dp[i], dp[i-j] + abs(h[i] - h[i-j]))
print(dp[n-1])
### BUGGY CODE ###

n = int(input())
count = 0
for i in range(1, n+1):
    k = 1
    hantei = 0
    s = list(map(int, list(str(i))))
    for j in range(len(s)):
        if s[j] != 3 and s[j] != 7 and s[j] != 5:
            hantei = 1
            break
        else:
            k *= s[j]
    if hantei == 0 and k%105 == 0:
        count += 1

print(count)

### FIXED CODE ###

n = int(input())
def check(s):
    if int(s) > n:
        return 0
    if all(s.count(i)>0 for i in '753'):
        count = 1
    else:
        count = 0
    for i in '753':
        count += check(s+i)
    return count
print(check('0'))
### BUGGY CODE ###

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

loop = []
trace = []
ai = 1
for i in range(N+1):
    if ai in trace:
        loop = trace[trace.index(ai):]
        trace = trace[:trace.index(ai)]
        break
    trace.append(ai)
    ai = A_list[ai-1]

if len(trace) > K:
    print(trace[K])
else:
    ind = K - len(trace)
    ind = ind % len(loop)
    print(loop[ind])

### FIXED CODE ###


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

loop = []
trace = [0] * (N+1)
visited = set()

ai = 1
for i in range(N+1):
    if ai in visited:
        ind = trace.index(ai)
        loop = trace[ind:i]
        trace = trace[:ind]
        break
    visited.add(ai)
    
    trace[i] = ai # ??
    ai = A_list[ai-1]


if len(trace) > K:
    print(trace[K])
else:
    ind = K - len(trace)
    ind = ind % len(loop)
    print(loop[ind])