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

from collections import defaultdict
N,K,L=list(input().split(" "))
N=int(N)
K=int(K)
L=int(L)

class deep_search:
    def __init__(self,n):
        self.n=n
        self.stack=[]
        self.mem=[]
        self.group={}
        self.dict=defaultdict(lambda:[])

    def unit(self,x,y):
        self.dict[x].append(y)
    def search(self):
        for v in range(1,self.n+1):
            if v not in self.mem:
                self.stack.append(v)
                self.mem.append(v)
                self.group[v]=v
                while self.stack!=[]:
                    w=self.stack.pop()
                    for ww in self.dict[w]:
                        if ww not in self.mem:
                            self.mem.append(ww)
                            self.group[ww]=v
                            self.stack.append(ww)
        return self.group
    
utl=deep_search(N)
utf=deep_search(N)

for i in range(K):
    p,q=map(int,list(input().split(" ")))
    utl.unit(p,q)
for i in range(L):
    r,s=map(int,list(input().split(" ")))
    utf.unit(r,s)
road_g=utl.search()
train_g=utf.search()
count=defaultdict(lambda:0)

for i in range(1,N+1):
    l=[road_g[i],train_g[i]]
    count[str(l)]+=1
for i in range(1,N+1):
    l=[road_g[i],train_g[i]]
    print(count[str(l)],end=" ")

### FIXED CODE ###

from collections import defaultdict
class Unionfind:
    def __init__(self,n):
        self.n=n
        self.roots=[i for i in range(self.n)]


    def root(self,x):
        if self.roots[x]==x:
            return x
        else:
            self.roots[x]=self.root(self.roots[x])
            return self.roots[x]
    def unite(self,x,y):
        if self.root(x)==self.root(y):
            return
        else:
            if self.root(x)>self.root(y):
                self.roots[self.root(x)]=self.root(y)
            else:
                self.roots[self.root(y)]=self.root(x)
    
    def same(self,x,y):
        return self.root(x)==self.root(y)

N,K,L=list(input().split(" "))
N=int(N)
K=int(K)
L=int(L)
road=Unionfind(N)
train=Unionfind(N)
for i in range(K):
    p,q=map(int,list(input().split(" ")))
    road.unite(p-1,q-1)
for i in range(L):
    r,s=map(int,list(input().split(" ")))
    train.unite(r-1,s-1)



count=defaultdict(lambda:0)
point=[]
for i in range(N):
    a=road.root(i)
    b=train.root(i)
    l=[a,b]
    point.append(l)
    count[str(l)]+=1
for i in point:
    print(count[str(i)],end=" ")
### BUGGY CODE ###

import sys
def main():    
    input = sys.stdin.readline
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    l = []
    for i in range(n):
        cur = i
        l2 = []
        l3 = []
        score = 0
        cnt = 0
        while True:
            if p[i] - 1 in l2:
                score += c[p[i] - 1]
                l3.append(score)
                break
            l2.append(i)
            score += c[p[i] - 1]
            l3.append(score)
            i = p[i] - 1
            cnt += 1
        l.append([l3, cnt + 1])
    A = []
    for i in range(n):
        x, y = l[i][0], l[i][1]
        ans = 0
        if x[-1] < 0:
            if k >= y:
                ans = max(x)
            else:
                if k % y == 0:
                    pass
                else:
                    ans = max(x[:k % y])
        else:
            ans = x[-1] * (k // y)
            if k % y == 0:
                pass
            else:
                ans += max(x[:k % y])
        A.append(ans)
    print(max(A))
if __name__ == "__main__":
    main()

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
l = [[] for i in range(n)]
for i in range(n):
    l2 = [i + 1]
    cnt = 0
    while True:
        l2.append(p[l2[-1] - 1])
        cnt += c[l2[-1] - 1]
        l[i].append(cnt)
        if l2[-1] == i + 1:
            break
ans = -float("inf")
for i in range(n):
    le = len(l[i])
    for j in range(min(k, le)):
        cnt = l[i][j]
        if l[i][-1] > 0:
            cnt += (k - j - 1) // le * l[i][-1]
        ans = max(ans, cnt)
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
c = 0
for i in range(len(s) - 2):
    for j in range(i + 1, len(s) - 1):
        for k in range(j + 1, len(s)):
            if j - i == k - j:
                continue
            if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
                c += 1
print(c)

### FIXED CODE ###

n = int(input())
s = input()
c = s.count('R') * s.count('G') * s.count('B')
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        k = j + (j - i)
        if k >= n:
            continue
        if s[i] == s[j] or s[j] == s[k] or s[k] == s[i]:
            continue
        c -= 1
print(c)
### BUGGY CODE ###

mod = 1000000007
eps = 10**-9


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

    def STfunc(A, B):
        ret = set()
        for a in A:
            ret.add(a)
        for b in B:
            ret.add(b)
        return ret

    # クエリは0-indexedで[l, r)
    class SparseTable():
        def __init__(self, A):
            # A: 処理したい数列
            self.N = len(A)
            self.K = self.N.bit_length() - 1
            self.table = [set()] * (self.N * (self.K + 1))
            for i, a in enumerate(A):
                self.table[i] = a
            for k in range(1, self.K + 1):
                for i in range(self.N):
                    j = i + (1 << (k - 1))
                    if j <= self.N - 1:
                        self.table[i + k * self.N] = STfunc(self.table[i + (k - 1) * self.N],
                                                            self.table[j + (k - 1) * self.N])

        def query(self, l, r):
            # [l, r)の最小値を求める
            k = (r - l).bit_length() - 1
            return STfunc(self.table[l + k * self.N], self.table[r - (1 << k) + k * self.N])

    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    C = [{c} for c in C]

    ST = SparseTable(C)
    for _ in range(Q):
        l, r = map(int, input().split())
        #print(ST.query(l-1, r))
        print(len(ST.query(l-1, r)))


if __name__ == '__main__':
    main()


### FIXED CODE ###

mod = 1000000007
eps = 10**-9


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

    class Bit:
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s

        def add(self, i, x):
            while i <= self.size:
                self.tree[i] += x
                i += i & -i

        def lower_bound(self, w):
            if w <= 0:
                return 0
            x = 0
            k = 1 << (self.size.bit_length() - 1)
            while k:
                if x + k <= self.size and self.tree[x + k] < w:
                    w -= self.tree[x + k]
                    x += k
                k >>= 1
            return x + 1

    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    query = []
    for q in range(Q):
        query.append(list(map(int, input().split())))
        query[-1].append(q)
    query.sort(key=lambda x: x[1])

    last = [0] * (N+1)
    for i, c in enumerate(C):
        if i > query[0][1]-1:
            break
        last[c] = i+1

    bit = Bit(N)
    for i in range(1, N+1):
        if last[i]:
            bit.add(last[i], 1)
    r_prev = query[0][1]
    ans = [0] * Q
    for l, r, q in query:
        if r > r_prev:
            for i in range(r_prev+1, r+1):
                j = last[C[i-1]]
                if j:
                    bit.add(j, -1)
                last[C[i-1]] = i
                bit.add(i, 1)
            r_prev = r
        ans[q] = bit.sum(r) - bit.sum(l-1)

    for a in ans:
        print(a)


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

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

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

for i in range(M):
    A[A.index(max(A))] //= 2

print(sum(A))

### FIXED CODE ###

import heapq
import math

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

A = list(map(lambda x: -x, map(int, input().split())))
heapq.heapify(A)

for i in range(M):
    tmp = heapq.heappop(A)
    tmp = math.ceil(tmp / 2)
    heapq.heappush(A, tmp)

print(-sum(A))
### BUGGY CODE ###

import itertools
import bisect

def main():
    N = int(input())
    S = input()
    d = {'R': [], 'G': [], 'B': []}
    for i, c in enumerate(S):
        d[c].append(i)
    #print(d)
    #answer = set()
    cnt = 0
    for xx, yy, zz in itertools.permutations(('R', 'G', 'B'), 3):
        x, y, z = d[xx], d[yy], d[zz]
        for i in x:
            y_start = bisect.bisect_left(y, i)
            for jj in range(y_start, len(y)):
                j = y[jj]
                assert i < j
                z_start = bisect.bisect_left(z, j)
                for kk in range(z_start, len(z)):
                    k = z[kk]
                    assert j < k
                    if k-j == j-i:
                        continue
                    #assert k > j > i
                    #answer.add((i+1, j+1, k+1))
                    cnt += 1
    print(cnt)
    #assert len(answer) == cnt
    #print(answer)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import itertools
import bisect

def main():
    N = int(input())
    S = input()
    d = {'R': [], 'G': [], 'B': []}
    for i, c in enumerate(S):
        d[c].append(i)
    #print(d)
    #answer = set()
    cnt = 0
    for xx, yy, zz in itertools.permutations(('R', 'G', 'B'), 3):
        x, y, z = d[xx], d[yy], d[zz]
        for i in x:
            y_start = bisect.bisect_left(y, i)
            for jj in range(y_start, len(y)):
                j = y[jj]
                assert i < j
                z_start = bisect.bisect_left(z, j)
                z_point = bisect.bisect_left(z, 2*j-i)
                #print(z_point, z)
                if (len(z) <= z_point) or (z[z_point] - j != j - i):
                    cnt += len(z) - z_start
                else:
                    cnt += len(z) - z_start - 1
                # for kk in range(z_start, len(z)):
                #     k = z[kk]
                #     assert j < k
                #     if k-j > j-i:
                #         #超えたのでもうチェックしなくていい
                #         cnt += len(z) - kk
                #         break
                #     elif k-j == j-i:
                #         cnt += len(z) - kk - 1
                #         break
                #     else:
                #         #assert k > j > i
                #         #answer.add((i+1, j+1, k+1))
                #         cnt += 1
    print(cnt)
    #assert len(answer) == cnt
    #print(answer)

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

class PriorityQueue:

    def __init__(self):
        self.q = {}

    def insert(self, k):
        self.q[k] = self.q.get(k, 0) + 1

    def extractMax(self):
        result = max(self.q)
        self.q[result] -= 1
        if self.q[result] == 0:
            del self.q[result]
        return result


if __name__ == '__main__':

    q = PriorityQueue()
    while True:
        al = input().split()

        if al[0] == "insert":
            q.insert(int(al[1]))
        elif al[0] == "extract":
            print(q.extractMax())
        elif al[0] == "end":
            break



### FIXED CODE ###

import heapq

heap = []

while True:

    inst = input()
    if inst[0] == "i":
        heapq.heappush(heap, -int(inst[7:]))
    elif inst[1] == "x":
        print(-heapq.heappop(heap))
    else:
        break
### BUGGY CODE ###

#dojkstra (prioroty queue ver.)
import queue
G=[]
#infの値に注意
inf=3*10**15
V, E, R=map(int,input().strip().split(' '))
rlis=list(map(int,input().strip().split(' ')))

for i in range(V):
    G.append([])
for i in range(E):
    at,bt,ct=map(int,input().strip().split(' '))
    G[at-1].append([ct,bt-1])
    G[bt-1].append([ct,at-1]) #無向グラフのときはon


def dijkstra(s):
    d=[inf]*V
    d[s]=0
    q=queue.PriorityQueue()
    q.put([0,s])
    while q.empty()==False:
        dq,v=q.get()
        if d[v]<dq:
            continue
        for i in range(len(G[v])):
            ec, et=G[v][i]
            #print(ec,et)
            if d[et]>d[v]+ec:
                d[et]=d[v]+ec
                q.put([d[et],et])
    return d

dist=[]
for i in range(V):
    dist.append(dijkstra(i))

ans=inf
def dfs(i,p,d):
    global ans
    if i==R:
        if d<ans:
            ans=d
        return
    for j in range(R):
        if visited[j]==False:
            visited[j]=True
            if p==-1:
                dfs(i+1,j,0)
            else:
                #print(rlis[p]-1,rlis[i]-1)
                dfs(i+1,j,d+dist[rlis[p]-1][rlis[j]-1])
            visited[j]=False

            
visited=[False]*V

dfs(0,-1,0)
            
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

#dojkstra
import itertools
import queue
G=[]
#infの値に注意
inf=3*10**15
V, E, R=map(int,input().strip().split(' '))
rlis=list(map(int,input().strip().split(' ')))

cost=[[inf]*V for i in range(V)]
for i in range(E):
    fr, to, co=map(int,input().strip().split(' '))
    cost[fr-1][to-1]=co
    cost[to-1][fr-1]=co
def dijkstra(s):
    d=[inf]*V
    used=[False]*V
    d[s]=0
    while True:
        v=-1
        for u in range(V):
            if used[u]==False and(v==-1 or d[u]<d[v]):
                v=u
        if v==-1:
            break
        used[v]=True
        for u in range(V):
            d[u]=min(d[u],d[v]+cost[v][u])
    return d

dist=[None] * V
for i in rlis:
    dist[i-1]=dijkstra(i-1)

ans=inf
for rperm in itertools.permutations(rlis):
    a_tmp=0
    for j in range(R-1):
        a_tmp+=dist[rperm[j]-1][rperm[j+1]-1]
    ans=min(ans,a_tmp)

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

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

C = N // (A + B) + (0 if N % (A + B) == 0 else 1)

blue = 0
total = 0
for n in range(C):
    addition = min(N - total, A + B)
    total += addition
    blue += min(addition, A)

print(blue)

### FIXED CODE ###

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

C = N // (A + B)
D = N % (A + B)

R = C * A + min(A, D)
print(R)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [[int(i) for i in input().split()] for i in range(m)]
bc.sort(key = lambda x:x[1], reverse = True)


for i in range(m):
        a.sort()
        bc_temp = bc[i]
        for j in range(bc_temp[0]):
                if a[j] < bc_temp[1]:
                        a[j] = bc_temp[1]
                elif a[j] > bc_temp[1]:
                        break

print(sum(a)) 

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [[int(i) for i in input().split()] for i in range(m)]

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

a.sort()

a_count = 0
for b, c in bc:
        if c > a[a_count]:
                for i in range(b):
                        if c > a[a_count]:
                                a[a_count] = c
                                a_count += 1    
                        else:
                                break
                        if a_count == n:
                                        break

        else:
                break
        if a_count == n:
                break        

print(sum(a))
### BUGGY CODE ###

N, Q = map(int, input().split())
edges = [input().split() for _ in range(N-1)]
operations = [input().split() for _ in range(Q)]

tree = {}
result = [0]*N
numbers = []

for o in operations:
    result[int(o[0])-1] += int(o[1])

for e in edges:
    parent = int(e[0])
    sun = int(e[1])

    if sun in numbers:
        result[parent-1] += result[sun-1]
        numbers.append(parent)
    else:
        result[sun-1] += result[parent-1]
        numbers.append(sun)

print(' '.join(map(str, result)))

### FIXED CODE ###

N, Q = map(int, input().split())

tree = [[] for _ in range(N)]
result = [0]*N

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

for _ in range(Q):
    p, x = map(int, input().split())
    result[p-1] += x

for i in range(N - 1):
    for j in tree[i]:
        result[j-1] += result[i]

print(' '.join(map(str, result)))
### BUGGY CODE ###

h, n = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(n)]

dp = [float('inf')] * (h+1)
dp[0] = 0

for i in range(h):
    for d, c in magic:
        next_index = min(i+d, h)
        dp[next_index] = min(dp[next_index], dp[i]+c)
        #print(d, c, dp)

print(dp[-1])

### FIXED CODE ###

h, n = map(int, input().split())
magic = [tuple(map(int, input().split())) for _ in range(n)]
#magic = [list(map(int, input().split())) for _ in range(n)]

dp = [float('inf')] * (h+1)
dp[0] = 0

for i in range(h):
    for d, c in magic:
        next_index = min(i+d, h)
        dp[next_index] = min(dp[next_index], dp[i]+c)
        #print(d, c, dp)

print(dp[-1])
### BUGGY CODE ###

tmp =input().split()
H,W,D=int(tmp[0]),int(tmp[1]),int(tmp[2])

list = [[0 for x in range(W)] for y in range(H)]
dict ={}
for i in range(H):
    tmp = input().split()
    list[i] =tmp
    for d in range(W):
        dict[list[i][d]] = str(i)+' '+str(d)

Q = int(input())

test = [[0 for x in range(2)] for y in range(Q)]
for j in range(Q):
    tmp = input().split()
    sum = 0
    Lj = int(tmp[0])
    Rj = int(tmp[1])
    count = int((Rj-Lj)/D)
    for k in range(count):
        posi1 = dict[str(Lj+D*k)].split()
        posi2 = dict[str(Lj+D*(k+1))].split()
        sum += abs(int(posi2[0])-int(posi1[0])) + abs(int(posi2[1])-int(posi1[1]))
    print(sum)

### FIXED CODE ###

tmp =input().split()
H,W,D=int(tmp[0]),int(tmp[1]),int(tmp[2])

list = [[0 for x in range(W)] for y in range(H)]
dictx ={}
dicty ={}
for i in range(H):
    tmp = input().split()
    for d in range(W):
        dictx[tmp[d]] = i
        dicty[tmp[d]] = d
cost ={}
def calcost(R):
    if int(R)<=D:
        cost[R] = 0
        return 0
    else:
        costs = abs(dictx[R]-dictx[str(int(R)-D)]) + abs(dicty[R]-dicty[str(int(R)-D)])
        cost[R] = costs + cost[str(int(R)-D)]
        return cost[R]

for n in range(1,H*W+1):
    calcost(str(n))
Q = int(input())
for j in range(Q):
    tmp = input().split()
    print(str(cost[tmp[1]]-cost[tmp[0]]))
### BUGGY CODE ###

# Library
alp = "abcdefghijklmnopqrstuvwxyz"
#

s = input()
t = input()
ss = s * 2
index = 0
next_char = [[-1 for j in range(len(s))] for i in range(26)]
# nc[i, j]: j文字目以降(1-indexed)で'a'+i がいつ出てくるか

for i in range(26):
    for j in range(len(s)):
        next_char[i][j] = ss.find(alp[i], j) - (j - 1)
        # print("next " + alp[i] + " is " + str(next_char[i][j]))


for i in range(len(t)):
    tmp = next_char[ord(t[i]) - ord('a')][index % len(s)]
    if tmp <= 0:
        index = -1
        break
    else:
        index += tmp
        # print(index)


print(index)


### FIXED CODE ###

# Library
import bisect

alp = "abcdefghijklmnopqrstuvwxyz"
#

s = input()
t = input()
ss = s * 2
index = -1
cir = 0
letter = []
res = 0

for i in range(len(ss)):
    letter.append([ss[i], i])

# Sort出来る.
letter.sort()

for i in range(len(t)):
    search = [t[i], index]
    tmp_ind = bisect.bisect(letter, search)
    # print("now searching " + str(search))
    # print("find: " + str(tmp_ind))
    # print("found: " + str(letter[tmp_ind]))
    if tmp_ind == len(ss):
        res = -1
        break
    if t[i] != letter[tmp_ind][0]:
        # Not exist
        res = -1
        break
    index += (letter[tmp_ind][1] - index)
    if index >= len(s):
        cir += 1
        index -= len(s)
    # print("cir,index : " + str(cir) + " " + str(index))
    res = cir * len(s) + index + 1

print(res)
### BUGGY CODE ###

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

Sum = 0

A.sort()
sosuu = []

for i in range(N):

    if i > 0:
        if A[i] == A[i-1]:
            continue

    flag = True

    for j in range(len(sosuu)):
        if A[i] % sosuu[j] == 0:
            flag = False
            break

    if flag:
        if i + 1 < N:
            if A[i] != A[i+1]:
                Sum += 1
        else:
            Sum += 1
        
        sosuu.append(A[i])

print(Sum)


### FIXED CODE ###

from collections import defaultdict

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

DP = [0] * (10 ** 6 + 1)

A.sort()
Sum = 0

d = defaultdict(int)
for key in A:
    d[key] += 1

for i in range(N):

    if DP[A[i]] == 0:
        for j in range(1, 10 ** 6):
            if A[i] * j <= 10 ** 6:
                DP[A[i] * j] = 1
            else:
                break

        if d[A[i]] == 1:
            Sum += 1
print(Sum)
### BUGGY CODE ###

N = int(input())
S = [input() for i in range(N)]

dic = {i:0 for i in S}
  
for i in S:
  dic[i] += 1
  
ans = [] 
for i in dic:
  if dic[i] == max(dic.values()):
    ans.append(i)
ans.sort()
for i in ans:
  print(i)

### FIXED CODE ###

N = int(input())
S = [input() for i in range(N)]
S.sort()

dic = {}
for i in S:
  dic[i] = 0
for i in S:
  dic[i] += 1
M = max(dic.values())
for i in dic:
  if dic[i] == M:
    print(i)
### BUGGY CODE ###

n = int(input())
L = list(map(int, input().split()))
x = [0] * 1010
for l in L:
  x[l] += 1

ans = 0;
for a in range(1, 1001):
  if x[a] == 0:
    continue
  for b in range(a, 1001):
    if x[b] == 0:
      continue
    for c in range(b, 1001):
      if x[c] == 0:
        continue
      if c >= a + b:
        break
      if a == b == c:
        ans += x[a] * (x[b]-1) * (x[c]-2) // 6
      elif a == b:
        ans += x[a] * (x[b]-1) * x[c] // 2
      elif b == c:
        ans += x[a] * x[b] * (x[c]-1) // 2
      else:
        ans += x[a] * x[b] * x[c]

print(ans)

### FIXED CODE ###

n = int(input())
L = list(map(int, input().split()))
x = [0] * 1010
for l in L:
  x[l] += 1

ans = 0;
for a in range(1, 1001):
  if x[a] == 0:
    continue
  for b in range(a, 1001):
    if x[b] == 0:
      continue
    for c in range(b, 1001):
      if x[c] == 0:
        continue
      if c >= a + b:
        break
      if a == b == c:
        ans += x[a] * (x[b]-1) * (x[c]-2) // 6
      elif a == b:
        ans += x[a] * (x[b]-1) * x[c] // 2
      elif b == c:
        ans += x[a] * x[b] * (x[c]-1) // 2
      else:
        ans += x[a] * x[b] * x[c]

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

from collections import deque
n,x,y=map(int,input().split())
edge=[[] for _ in range(n)]
for i in range(n-1):
    edge[i+1].append(i)
    edge[i].append(i+1)
edge[x-1].append(y-1)
edge[y-1].append(x-1)
ans=[[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    dist=[-1]*n
    dist[i]=0
    que=deque([i])
    while que:
        now=que.popleft()
        for j in edge[now]:
            if dist[j]==-1:
                dist[j]=dist[now]+1
                que.append(j)
    for j in range(n):
        ans[i][j]=dist[j]
aa=[0]*n
for i in ans:
    for j in i:
        aa[j]+=1
for i in aa[1:]:
    print(i//2)

### FIXED CODE ###

from collections import deque
n,x,y=map(int,input().split())
edge=[[] for _ in range(n)]
for i in range(n-1):
    edge[i+1].append(i)
    edge[i].append(i+1)
edge[x-1].append(y-1)
edge[y-1].append(x-1)
ans=[[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    dist=[-1]*n
    dist[i]=0
    que=deque([i])
    while que:
        now=que.popleft()
        for j in edge[now]:
            if dist[j]==-1:
                dist[j]=dist[now]+1
                que.append(j)
    for j in range(n):
        ans[i][j]=dist[j]
aa=[0]*n
for i in ans:
    for j in i:
        aa[j]+=1
for i in aa[1:]:
    print(i//2)
### BUGGY CODE ###

N,K=map(int,input().split())
t=list(map(int,input().split()))
g=[1]
for i in range(N):
  gs=set(g)
  if t[g[i]-1] in gs:
    h=g.index(t[g[i]-1])
    s=i+1-h
    break
  g.append(t[g[i]-1])
if K>h:
  K=(K-h)%s+h
print(g[K])

### FIXED CODE ###

N, K = map(int, input().split())
T_list = list(map(int, input().split()))
T_list = [T_list[i]-1 for i in range(N)]
point = 0
syuuki = 0

if K < N:
  i = 0
  while i < K:
    point = T_list[point]
    i += 1  

else:
  i = 0
  while i < N:
    point = T_list[point]
    if point == 0:
      syuuki = i+1
      break
    i += 1
  second_point = point
  
  if syuuki != 0:
    L = K % syuuki

  else:
    j = 0
    while j < N:
      point = T_list[point]
      if point == second_point:
        syuuki = j+1
        break
      j += 1
    L = (K-i) % syuuki

  k = 0
  while k < L:
    point = T_list[point]
    k += 1
  
print(point+1)