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

from itertools import combinations
from functools import reduce
from operator import xor

def checkxor(a,b):
    zero = set()
    for i in range(1,len(a)+1):
        for x in combinations(a,i):
            zero.add(reduce(xor,x))
    for i in range(1,len(b)+1):
        for x in combinations(b,i):
            if reduce(xor,x) not in zero:
                return False
    return True

T = int(input())
for i in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = input()
    if S[-1] == '1':
        print('1')
    elif S.count('0') == len(S):
        print('0')
    else:
        zeros = []
        ones = []
        for j in range(len(S)):
            if S[j] == '1':
                ones.append(A[j])
                current = 1
                break
        for k in range(j+1,len(S)):
            if S[k] == '1':
                if current == 1:
                    ones.append(A[k])
                else:
                    if checkxor(zeros,ones) == False:
                        print('1')
                        break
                    else:
                        ones.append(A[k])
                        current = 1
            else:
                if current == 0:
                    zeros.append(A[k])
                else:
                    zeros.append(A[k])
                    current = 0
        if checkxor(zeros,ones) == False:
            print('1')
        else:
            print('0')

### FIXED CODE ###

T = int(input())
for i in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = input()
    base = []
    for i in range(1,N+1):
        temp = A[-i]
        for x in base:
            temp = min(temp,temp^x)
        if temp != 0:
            if S[-i] == '1':
                print('1')
                break
            else:
                base.append(temp)
    else:
        print('0')
### BUGGY CODE ###

def bit_add(bit, i, x):
    i += 1
    n = len(bit)
    while i <= n:
        bit[i - 1] += x
        i += i & -i


def bit_sum(bit, i):
    result = 0
    i += 1
    while i > 0:
        result += bit[i - 1]
        i -= i & -i
    return result


def main():
    from sys import stdin
    from builtins import int, list, map, range
    readline = stdin.readline
    N, D, A = map(int, readline().split())
    XH = []
    for _ in range(N):
        X, H = map(int, readline().split())
        XH.append((X, (H + A - 1) // A))

    D *= 2
    XH.sort()
    X = [x for x, h in XH]
    result = 0
    bit = [0] * (N + 1)
    for i in range(N):
        x, h = XH[i]
        h -= bit_sum(bit, i)
        if h <= 0:
            continue
        result += h
        bit_add(bit, i, h)

        t = x + D
        ok = i
        ng = N
        while ng - ok != 1:
            m = ok + (ng - ok) // 2
            if X[m] <= t:
                ok = m
            else:
                ng = m
        bit_add(bit, ng, -h)
    print(result)


main()


### FIXED CODE ###

N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]

XH.sort()
q = []
t = 0
result = 0
for x, h in XH:
    while True:
        if len(q) == 0:
            break
        if x <= q[0][0]:
            break
        t -= q[0][1]
        q.pop(0)
    h -= t
    if h < 0:
        continue
    c = (h + A - 1) // A
    result += c
    t += c * A
    q.append((x + 2 * D, c * A))
print(result)
### BUGGY CODE ###

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

data=[((A[0],0),(-1,-1)) for i in range(2**N)]
for i in range(1,2**N):
    test=set([])
    for j in range(0,N):
        if i>>j&1==1:
            a,b=data[i-2**j]
            test.add(a)
            test.add(b)
    test.add((A[i],i))
    test=list(test)
    test.sort()
    data[i]=(test[-1],test[-2])

ans=[data[i][0][0]+data[i][1][0] for i in range(2**N)]
for i in range(2,2**N):
    ans[i]=max(ans[i],ans[i-1])

for i in range(1,2**N):
    print(ans[i])


### FIXED CODE ###

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

data=[[(A[0],0),(-1,-1)] for i in range(2**N)]
for i in range(1,2**N):
    for j in range(N):
        if i>>j&1==1:
            a,b=data[i-2**j]
            if a[0]>data[i][0][0]:
                data[i][1]=data[i][0]
                data[i][0]=a
            elif a[0]>data[i][1][0] and a[1]!=data[i][0][1]:
                data[i][1]=a
            if b[0]>data[i][0][0]:
                data[i][1]=data[i][0]
                data[i][0]=b
            elif b[0]>data[i][1][0] and b[1]!=data[i][0][1]:
                data[i][1]=b
    a=(A[i],i)
    if a[0]>data[i][0][0]:
        data[i][1]=data[i][0]
        data[i][0]=a
    elif a[0]>data[i][1][0] and a[1]!=data[i][0][1]:
        data[i][1]=a


ans=[data[i][0][0]+data[i][1][0] for i in range(2**N)]
for i in range(2,2**N):
    ans[i]=max(ans[i],ans[i-1])

for i in range(1,2**N):
    print(ans[i])
### BUGGY CODE ###

S = list(input())

count = 0
i = 0
while len(set(S))>1:
    if S[i] != S[i+1]:
        S.remove('0')
        S.remove('1')
        count += 2
        if i != 0:
            i -= 1
    else:
        i += 1
print(count)

### FIXED CODE ###

S = list(input())
one = S.count('1')
zero = S.count('0')

print(2*min(one,zero))
### BUGGY CODE ###

def divisors(M):#Mの約数列 O(n^(0.5+e))
    import math
    d=[]
    i=1
    while math.sqrt(M)>=i:
        if M%i==0:
            d.append(i)
            if i**2!=M:
                d.append(M//i)
        i=i+1
    d.sort()
    return d

import numpy as np
N=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
A=np.array([a[i]^a[i-1] for i in range(0,N)])
B=np.array([b[i]^b[i-1] for i in range(0,N)])
d=divisors(N)
perioda=N
for i in range(0,len(d)):
    test=np.roll(A,-d[i])
    if all(test==A):
        perioda=min(perioda,d[i])

periodb=N
for i in range(0,len(d)):
    test=np.roll(B,-d[i])
    if all(test==B):
        periodb=min(periodb,d[i])

if perioda==periodb:
    A=A[:perioda]
    B=B[:periodb]
    ans=-1
    for i in range(0,perioda):
        if all(A==B):
            ans=i
            break
        A=np.roll(A,-1)
    if ans!=-1:
        for i in range(0,N//perioda):
            print(ans+perioda*i,a[ans+perioda*i]^b[0])

### FIXED CODE ###

def divisors(M):#Mの約数列 O(n^(0.5+e))
    import math
    d=[]
    i=1
    while math.sqrt(M)>=i:
        if M%i==0:
            d.append(i)
            if i**2!=M:
                d.append(M//i)
        i=i+1
    d.sort()
    return d

import numpy as np
N=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
A=np.array([a[i]^a[i-1] for i in range(0,N)])
B=np.array([b[i]^b[i-1] for i in range(0,N)])
d=divisors(N)
perioda=N
for i in range(0,len(d)):
    test=np.roll(A,-d[i])
    if all(test==A):
        perioda=min(perioda,d[i])

periodb=N
for i in range(0,len(d)):
    test=np.roll(B,-d[i])
    if all(test==B):
        periodb=min(periodb,d[i])

if perioda==periodb:
    A=A[:perioda]
    B=B[:periodb]
    kouho=[]
    for i in range(0,len(B)):
        if A[i]==B[0]:
            kouho.append(i)
    ans=-1
    for i in range(0,len(kouho)):
        test=np.roll(A,-kouho[i])
        if all(test==B):
            ans=kouho[i]
            break
    if ans!=-1:
        for i in range(0,N//perioda):
            print(ans+perioda*i,a[ans+perioda*i]^b[0])
### BUGGY CODE ###

#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    n, m = MI()
    a = LI()
    if n == 1:
        while m > 0:
            a[0] = a[0] // 2
            m -= 1
        print(a[0])
        return
    a.sort()
    a.reverse()
    while m > 0:
        while a[0] >= a[1]:
            a[0] = a[0] // 2
            m -= 1

        a.sort()
        a.reverse()
    print(sum(a))


main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import heapq


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    n, m = MI()
    a = LI()
    heap = []
    for i in range(n):
        heapq.heappush(heap, a[i] * -1)

    while m > 0:
        min_ = heapq.heappop(heap) * -1
        min_ = (min_ // 2) * -1
        heapq.heappush(heap, min_)
        m -= 1
    print(sum(heap) * -1)


main()
### BUGGY CODE ###

INF=100000000
N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*N
for i in range(1,N):
    dp[i]=min(dp[j]+abs(h[j]-h[i]) for j in range(max(i-K,0),i))
print(dp[N-1])

### FIXED CODE ###

INF=100000000
N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*N
for i in range(1,N):
    dp[i]=min(dp[j]+abs(h[j]-h[i]) for j in range(max(i-K,0),i))
print(dp[N-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
s = input()
dp = [[0]*(n+1) for y in range(n+1)]
ans = 0

for i in range(n):
    a = n-1-i
    for j in range(n):
        b = n-1-j
        if s[a] == s[b]:
            dp[a][b] = dp[a+1][b+1] + 1
for i in range(n):
    for j in range(n):
        now = min(dp[i][j], j-i)
        ans = max(ans, now)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
s = input()
dp = [[0]*(n+1) for y in range(n+1)]
ans = 0

for i in range(n):
    a = n-1-i
    for j in range(n):
        b = n-1-j
        if s[a] == s[b]:
            dp[a][b] = dp[a+1][b+1] + 1
for i in range(n):
    for j in range(n):
        now = min(dp[i][j], j-i)
        ans = max(ans, now)
print(ans)
### BUGGY CODE ###

p_num = int(input())
p = list(map(int,input().split()))

count = 0
for i in range(p_num):
    for j in range(i+1):
        if p[i] > p[j]:
            break
    else:
        count += 1
        

print(count)


### FIXED CODE ###

p_num = int(input())
p = list(map(int,input().split()))

count = 1
min_num = p[0]


for i in p[1:]:
    if i < min_num:
        min_num = i
        count += 1
        

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

N, K = list(map(int, input().split()))
H = sorted([int(input()) for _ in range(N)])

ans = float("inf")

for i in range(N-K+1):
    tree = H[i:i+K]
    ans =min(ans, tree[-1]-tree[0])
print(ans)

### FIXED CODE ###

N, K = list(map(int, input().split()))
H = [int(input()) for _ in range(N)]
H.sort()
ans = []

for i in range(N-K+1):
    ans.append(H[i+K-1]-H[i])
print(min(ans))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
ans = []
for i in range(n-1):
    for j in range(i+1, n):
        ans.append((a[i]*a[j])%mod)
print(sum(ans)%mod)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
x = sum(a)-a[0]
ans = 0
for i in range(n-1):
    ans += (a[i]*x)%mod
    x -= a[i+1]
print(ans%mod)
### BUGGY CODE ###

n = int(input())
s = input()
i = 0
ans = 0
while i < n:
  if s[i] == 'A' and s[i:i+3] == 'ABC':
    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
i = 0
ans = 0
while i < n:
  if s[i]=='A' and s[i:i+3]=='ABC':
    ans += 1
    i += 3
  else:
    i += 1
print(ans)
### BUGGY CODE ###

class Unionfind:

    __slots__ = ['parents','sizes']

    def __init__(self, n):
        self.parents = list(range(n))
        self.sizes = [1]*n

    def root(self, x):
        if self.parents[x] == x:
            return x
        else:
            root_x = self.root(self.parents[x])
            self.parents[x] = root_x
            return root_x

    def unite(self, x, y):
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.sizes[x] += self.sizes[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.root(x) == self.root(y)

    # 集合自体の数 ({1,2}, {3}, {4} : kind -> 3)
    def kind(self):
        for v in range(N):
            self.root(v)
        return len(list(set(self.parents)))

    # xが属する集合の要素の数　({1,2,3} : size(2) -> 3)
    def size(self, x):
        self.sizes[x] = self.sizes[self.root(x)]
        return self.sizes[x]

N, K, L = map(int,input().split())
road = Unionfind(N)
train = Unionfind(N)

for _ in range(K):
    p, q = map(int,input().split())
    p -= 1; q -= 1
    road.unite(p, q)

for _ in range(L):
    r, s = map(int,input().split())
    r -= 1; s -= 1
    train.unite(r, s)

ans_list = []

r = [set() for _ in range(N)]
t = [set() for _ in range(N)]
for i in range(N):
    r[road.root(i)].add(i)
    t[train.root(i)].add(i)

ans_list = []

for i in range(N):
    ans = len(r[road.root(i)] & t[train.root(i)])
    ans_list.append(ans)

print(*ans_list)

### FIXED CODE ###

from collections import defaultdict

class Unionfind:

    __slots__ = ['parents','sizes']

    def __init__(self, n):
        self.parents = list(range(n))
        self.sizes = [1]*n

    def root(self, x):
        if self.parents[x] == x:
            return x
        else:
            root_x = self.root(self.parents[x])
            self.parents[x] = root_x
            return root_x

    def unite(self, x, y):
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.sizes[x] += self.sizes[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.root(x) == self.root(y)

    # 集合自体の数 ({1,2}, {3}, {4} : kind -> 3)
    def kind(self):
        for v in range(N):
            self.root(v)
        return len(list(set(self.parents)))

    # xが属する集合の要素の数　({1,2,3} : size(2) -> 3)
    def size(self, x):
        self.sizes[x] = self.sizes[self.root(x)]
        return self.sizes[x]

N, K, L = map(int,input().split())
road = Unionfind(N)
train = Unionfind(N)

for _ in range(K):
    p, q = map(int,input().split())
    p -= 1; q -= 1
    road.unite(p, q)

for _ in range(L):
    r, s = map(int,input().split())
    r -= 1; s -= 1
    train.unite(r, s)

cnt = defaultdict(int)

for i in range(N):
    key = (road.root(i), train.root(i))
    cnt[key] += 1

ans_list = []
for i in range(N):
    key = (road.root(i), train.root(i))
    ans = cnt[key]
    ans_list.append(ans)

print(*ans_list)
### BUGGY CODE ###

def aaa(n,m):
    count1 = 1
    count2 = 1
    l1 = [0]*n
    l2 = [0]*m
    if n % 2 == 1:
        count1 = count1 + n//2
        count2 = count2 + n//2 + 1
    else:
        count1 = count1 + n//2
        count2 = count2 + n//2
    if m % 2 == 1:
        count1 = count1 + m//2 + 1
        count2 = count2 + m//2
    else:
        count1 = count1 + m//2
        count2 = count2 + m//2
    l3 = [count1,count2]
    l1 = l1 + l3 + l2
    return l1
s = list(input())
j = 0
a = 0
b = 0
l = []
for i in range(len(s)):
    if s[i] == "R" and j == 0:
        a = a + 1
    elif s[i] == "R" and j == 1:
        l = l + aaa(a-1,b-1)
        a = 1
        b = 0
        j = 0
    else:
        b = b + 1
        j = 1
l = l + aaa(a-1,b-1)
for x in l:
    print(x,end=" ")

### FIXED CODE ###

def aaa(n,m):
    count1 = 1
    count2 = 1
    if n % 2 == 1:
        count1 = count1 + n//2
        count2 = count2 + n//2 + 1
    else:
        count1 = count1 + n//2
        count2 = count2 + n//2
    if m % 2 == 1:
        count1 = count1 + m//2 + 1
        count2 = count2 + m//2
    else:
        count1 = count1 + m//2
        count2 = count2 + m//2
    l3 = [count1,count2]
    return l3
s = list(input())
n = len(s)
j = 0
a = 0
b = 0
l = [0]*n
for i in range(len(s)):
    if s[i] == "R" and j == 0:
        a = a + 1
    elif s[i] == "R" and j == 1:
        l[c-1] = aaa(a-1,b)[0]
        l[c] = aaa(a-1,b)[1]
        a = 1
        b = 0
        j = 0
    elif s[i] == "L" and j == 0:
        j = 1
        c = i
    elif s[i] == "L" and j == 1:
        b = b + 1
l[c-1] = aaa(a-1,b)[0]
l[c] = aaa(a-1,b)[1]
for x in l:
    print(x,end=" ")
### BUGGY CODE ###

h, w, m = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(m)]

max = 0
for i in range(1, h+1):
  for j in range(1, w+1):
    count = 0
    for k in l:
      if k[0] == i or k[1] == j:
        count += 1
    if count > max:
      max = count

print(max)

### FIXED CODE ###

from collections import defaultdict

h, w, m = map(int, input().split())

cnt_h = [0] * h #各行の爆破対象マス
cnt_w = [0] * w #各列の爆破対象マス
dic = defaultdict(int) #

for _ in range(m): #爆破対象のマスそれぞれ
  h_m, w_m = map(int, input().split()) #位置を取得
  cnt_h[h_m -1] += 1 #行のカウント
  cnt_w[w_m -1] += 1 #列のカウント
  dic[(h_m - 1, w_m - 1)] += 1 #マス（交差地点）を保持

max_h = max(cnt_h)
max_w = max(cnt_w)

mh = []
mw = []

for i in range(h):
  if max_h == cnt_h[i]:
    mh.append(i)
    
for j in range(w):
  if max_w == cnt_w[j]:
    mw.append(j)

for i in mh:
  for j in mw:
    if dic[(i, j)] == 0:
      print(max_h + max_w)
      exit()

print(max_h + max_w - 1)
### BUGGY CODE ###

import itertools as c
n,k=map(int,input().split())
for i in range(1,k+1):
  a=len(list(c.combinations(range(k-1),i-1)))%(10**9+7)
  b=len(list(c.combinations(range(n-k+1),i)))%(10**9+7)
  print((a*b)%(10**9+7))

### FIXED CODE ###

n,k=map(int,input().split())
import math as m
def c(t,r):
    if t>=r:
      return (m.factorial(t)//(m.factorial(t-r)*m.factorial(r)))%(10**9+7)
    else:
      return 0
for i in range(1,k+1):
  a=c(k-1,i-1)
  b=c(n-k+1,i)
  print((a*b)%(10**9+7))
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
while m > 0:
    M = max(a)
    tmp = a.index(M)
    a[tmp] = a[tmp] // 2
    m -= 1
print(sum(a))


### FIXED CODE ###

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

pq = []
for a in A:
    heapq.heappush(pq, -a)#'-'にすることで最大値を考えることができる！
#print(pq)
for _ in range(m):
    a = (-heapq.heappop(pq)) // 2
    heapq.heappush(pq, -a)
print(-sum(pq))
### BUGGY CODE ###

N = int(input())
import copy
A = [int(input()) for _ in range(N)]
for i in range(N):
    B = copy.copy(A)
    B.remove(B[i])
    print(max(B))

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
a = max(A)
i = A.index(a)

import copy
B = copy.copy(A)
B.remove(a)

for j in range(N):
    if j == i:
        print(max(B))
    else:
        print(a)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(n):
    if i % 2 == 0:
        b.append(a[i])
    else:
        b.insert(0, a[i])
if n % 2 == 1:
    b.reverse()
print(" ".join(map(str, b)))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0] * ((n + 1) // 2)
c = [0] * (n // 2)
for i in range(n):
    if i % 2 == 0:
        b[i // 2] = a[i]
    else:
        c[i // 2] = a[i]
if n % 2 == 0:
    c.reverse()
    s = c + b
else:
    b.reverse()
    s = b + c
print(" ".join(map(str, s)))
### BUGGY CODE ###

from operator import mul
from functools import reduce
N,a,b=map(int,input().split())
MOD=10**9+7
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
cnt=0
for i in range(1,N+1):
  cnt+=cmb(N,i)
A=cmb(N, a)
B=cmb(N, b)
cnt=cnt-A-B
ans=cnt%MOD
print(ans)

### FIXED CODE ###

N,a,b=map(int,input().split())
MOD=10**9+7
def comb(n,k):
  tmp=1
  for i in range(n-k+1,n+1):
    tmp*=i
    tmp%=MOD
  for i in range(1,k+1):
    tmp*=pow(i,MOD-2,MOD)
    tmp%=MOD
  return tmp
ans = pow(2,N,MOD) - 1 - comb(N,a) - comb(N,b)
print(ans%MOD)
### BUGGY CODE ###

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

cnt = 0
idx = 0
while 1:
  if (cnt+1) in A[idx:]:
    cnt += 1
    idx = A.index(cnt)

if cnt == 0:
  print(-1)
else:
  print(len(A)-cnt)

### FIXED CODE ###

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

k = 1
ans = 0

if 1 not in A:
  print(-1)
  exit()

for a in A:
  if a == k:
    k += 1
  else:
    ans += 1

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

n=int(input())
l=[list(map(int, input().split())) for i in range(n-1)]

#print(l)
for i in range(n-1):
    t=l[i][1]+l[i][0]
    for j in range(i+1,n-1):
        if l[j][1]>=t:
            t=l[j][1]+l[j][0]
        elif l[j][1]<t:
            if (t-l[j][1])%l[j][2]==0:
                t+=l[j][0]
            else:
                e=l[j][1]
                while t>l[j][1]:
                    l[j][1]+=l[j][2]
                t=l[j][1]+l[j][0]
                l[j][1]=e
    print(t)
print(0)

        

### FIXED CODE ###

n=int(input())
l=[list(map(int, input().split())) for i in range(n-1)]

#print(l)
for i in range(n-1):
    t=l[i][1]+l[i][0]
    for j in range(i+1,n-1):
        if l[j][1]>=t:
            t=l[j][1]+l[j][0]
        elif l[j][1]<t:
            if (t-l[j][1])%l[j][2]==0:
                t+=l[j][0]
            else:
                x=(t-l[j][1])//l[j][2]+1
                t=l[j][2]*x+l[j][1]+l[j][0]           
    print(t)
    #print(l)
print(0)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n, k = input_to_int_map()
    a = input_to_int_tuple()

    place = 1
    place_goned = [place]
    i = 0
    while i < n:
        place = a[place - 1]
        if place in place_goned:
            break

        place_goned.append(place)
        i += 1

    if k < len(place_goned):
        return place_goned[k]

    pre_loop_cnt = place_goned.index(place)
    move_cnt = k - pre_loop_cnt
    return place_goned[pre_loop_cnt:][move_cnt % len(place_goned[pre_loop_cnt:])]


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

# -*- coding: utf-8 -*-

# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n, k = input_to_int_map()
    a = {i + 1: int(val) for i, val in enumerate(input().split())}

    place = 1
    visit = {place}
    place_visits = [place]
    for i in range(k):
        place = a[place]
        if place in visit:
            left = place_visits.index(place)
            return place_visits[left + (k - left) % (i + 1 - left)]
        else:
            visit.add(place)
            place_visits.append(place)

    return place


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

import math
n,k=map(int,input().split())

s=math.ceil(n/k)
list_t=[]
for i in range(s+1):
  t=abs(n-i*k)
  list_t.append(t)
  
print(min(list_t))
  


### FIXED CODE ###

n,k=map(int,input().split())
s=n%k
print(min(s,abs(k-s)))