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

s = input()
t = input()

# dp[i][j] : 文字列Sのi文字目までと文字列Tのj文字目まで(Sの最後index, Tの最後index, 値)

dp = [[(0,"") for i in range(len(t) + 2)] for j in range(len(s) + 2)]

dp[0][0] = (0,"")

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            if dp[i][j][0] + 1 > dp[i+1][j+1][0]:
                dp[i+1][j+1] = (dp[i][j][0] + 1, dp[i][j][1] + s[i])
            else:
                dp[i+1][j+1] = (dp[i][j+1][0], dp[i][j+1][1])
        if dp[i+1][j+1][0] < dp[i][j+1][0]:
            dp[i+1][j+1] = dp[i][j+1]
        if dp[i+1][j+1][0] < dp[i+1][j][0]:
            dp[i+1][j+1] = dp[i+1][j]
            
print(dp[len(s)][len(t)][1])



### FIXED CODE ###

s = input()
t = input()

# dp[i][j] : 文字列Sのi文字目までと文字列Tのj文字目まででの値(len, 例)

dp = [[0 for i in range(len(t) + 2)] for j in range(len(s) + 2)]

dp[0][0] = 0

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i][j] + 1, dp[i+1][j], dp[i][j+1])
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

st = ""
i = len(s) 
j = len(t)            
while i > 0 and j > 0:
    if s[i-1] == t[j-1]:
        st = t[j-1] + st
        i = i - 1
        j = j - 1
    elif dp[i][j] == dp[i-1][j]:
        i = i - 1
    else:
        j = j - 1

print(st)
### BUGGY CODE ###

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

# 昇順のカードとする
g_cards = list(map(int, input().split()))
cards = sorted(g_cards)

# 操作
for i in range(M):
	size, val = map(int, input().split())
	t_change = 0
	t_i = 0
	while((t_change < size) and (t_i < N)):
		# カード入れ替え
		if(cards[t_i] < val):
			cards[t_i] = val
			t_change += 1
		t_i += 1
	cards.sort()

print(sum(cards))

### FIXED CODE ###

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

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

# key-valueデータで管理
dict_cards = []
for card in g_cards:
	dict_cards.append([card, 1])

# 操作
for i in range(M):
	# sizeと同じ枚数のカードが増えたと考える
	size, val = map(int, input().split())
	dict_cards.append([val, size])

# 降順にする
s_dict_cards = sorted(dict_cards, key=lambda x: -x[0])

s_cards = []
for data in s_dict_cards:
	s_cards += [data[0]] * data[1]
	if(len(s_cards) >= N):
		break
# 出力
sum_val = sum(s_cards[:N])
print(sum_val)
### BUGGY CODE ###

n = int(input())
s = input()
x = []
for i in range(n):
    x.append(s[i:])

x.sort()

ans = 0
for i in range(n):
    for j in range(i+1, n):
        y = x[i]
        z = x[j]
        m = min(len(y), len(z), abs(len(y) - len(z)))
        tmp = 0
        for k in range(m):
            if y[k] == z[k]:
                tmp += 1
        if ans < tmp:
            ans = tmp
print(ans)

### FIXED CODE ###

n = int(input())
s = input()

dp = [ [0] * (n+1) for _ in range(n+1)]

for i in range(n-1, -1, -1):
    for j in range(n-1, -1, -1):
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + 1
        else:
            dp[i][j] = 0

ans = 0
for i in range(n):
    for j in range(n):
        tmp = min(dp[i][j], abs(i-j))
        if ans < tmp:
            ans = tmp
print(ans)
### BUGGY CODE ###

N = int(input())

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

V = []
for i in range(N):
    volume = 0
    for j in range(N):
        if j % 2 == 0:
            volume += A[(i + j) % N]
        else:
            volume -= A[(i + j) % N]
    print(volume ,end=' ')

print()

### FIXED CODE ###

N = int(input())

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


volume = 0
for j in range(N):
    if j % 2 == 0:
        volume += A[j]
    else:
        volume -= A[j]
print(volume ,end=' ')

for i in range(1, N):
    volume = 2 * A[i - 1] - volume
    print(volume ,end=' ')

print()
### BUGGY CODE ###

n = int(input())
array = []
for i in range(n+1):
    if '7' in str(i):
        if '5' in str(i):
            if '3' in str(i):
                if (str(i).count('7') + str(i).count('5') + str(i).count('3')) == len(str(i)):
                    array.append(i)
print(len(array))


### FIXED CODE ###

n = int(input())
def dfs(s):
        if int(s) > n:
                return 0
        ret = 0
        if s.count('7')>0 and s.count('5')>0 and s.count('3')>0:
            ret = 1
        for c in '753':
                ret += dfs(s + c)
        return ret
print(dfs('0'))
### BUGGY CODE ###

def resolve():
    '''
    code here
    '''
    import collections

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]
    max_num = 10**6
    fp = [[max_num for _ in range(W)] for _ in range(H)]
    
    que = collections.deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0
    next_y_x = []
    for i in range(5):
        for j in range(5):
            next_y_x.append([-2 + i, -2 + j])
    next_y_x.remove([0,0])

    while que:
        temp = que.popleft()
        w_num = temp[2]

        for dy, dx in next_y_x:
            ny = temp[0] + dy
            nx = temp[1] + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                if abs(dy) + abs(dx) == 1:
                    if grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                        que.appendleft([ny, nx, w_num])
                        fp[ny][nx] = w_num
                else:
                    nw = w_num +1
                    if grid[ny][nx] == '.' and fp[ny][nx] > nw:
                        que.append([ny, nx, nw])
                        fp[ny][nx] = nw

    if fp[Dh][Dw] != max_num:
        print(fp[Dh][Dw])
    else:
        print(-1)

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    '''
    code here
    '''
    from collections import deque

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [input() for _ in range(H)]
    max_num = 10**6
    fp = [[max_num] * W for _ in range(H)]

    que = deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while que:
        y, x, w_num = que.popleft()

        for dy, dx in walk:
            ny = y + dy
            nx = x + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                que.appendleft([ny, nx, w_num])
                fp[ny][nx] = w_num

        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            nw = w_num +1

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > nw:
                que.append([ny, nx, nw])
                fp[ny][nx] = nw

    if fp[Dh][Dw] != max_num:
        print(fp[Dh][Dw])
    else:
        print(-1)

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

n, m = map(int, input().split())
A = []
for i in range(m):
    A.append(int(input()))
    
dp = [0 for i in range(n + 1)]
dp[0] = 1

for i in range(n+1):
    if not i in A:
        if (dp[i-2] >= 1) and (i-2 >= 0):
            dp[i] += dp[i-2]
        if (dp[i-1] >= 1) and (i-1 >= 0):
            dp[i] += dp[i-1]
            
print(dp[-1] % (10 ** 9 + 7))

### FIXED CODE ###

n, m = map(int, input().split())
mod = 10 ** 9 + 7
A = []
for i in range(m):
    A.append(int(input()))
    
dp = [None for i in range(n + 1)]
dp[0] = 1

for a in A:
    dp[a] = 0
    
for i in range(1,n+1):
    if dp[i] != 0:
        dp[i] = 0
        if i >= 2:
            dp[i] += (dp[i-2] + dp[i-1]) % mod
        elif i == 1:
            dp[i] += dp[i-1] % mod
            
print(dp[-1])
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
ans = 0
for i in range(n):
    for j in range(i+1,n):
        ans += a[i]*a[j]
        ans = ans % (10**9+7)
print(ans)

### FIXED CODE ###

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

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
P = 10**9 + 7
N = 1000001 #使う最大値+1以上にする、値に注意3*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
for i in range(2,N):
  inv += [inv[P % i] * (P - int(P / i)) % P]
lcm=[0]*(max(a)+2)
for i in range(n):
  k=a[i]
  for j in range(1,int(a[i]**0.5)+1):
    cnt=0
    while k%(j+1)==0:
      k//=j+1
      cnt+=1
    lcm[j+1]=max(cnt,lcm[j+1])
  lcm[k]=max(1,lcm[k])
lcmn=1
for i in range(len(lcm)):
  if lcm[i]>0:
    lcmn*=i**lcm[i]%mod
lcmn%=mod
ans=0
for i in range(n):
  ans+=lcmn*inv[a[i]]%mod
print(ans%mod)


### FIXED CODE ###

from fractions import gcd
P = 10**9 + 7
N = 1000001 #使う最大値+1以上にする、値に注意3*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
for i in range(2,N):
  inv += [inv[P % i] * (P - int(P / i)) % P]
n=int(input())
a=list(map(int,input().split()))
lcm=a[0]
mod=10**9+7
for i in range(1,n):
  lcm=(lcm//gcd(lcm,a[i]))*a[i]
ans=0
lcm%=mod
for i in range(n):
  ans=(ans+lcm*inv[a[i]])%mod
print(ans%mod)
### BUGGY CODE ###

s = input()
n = int(input())

for i in range(n):
    q = input().split()
    if q[0] == '1':
        s = s[::-1]
    else:
        if q[1] == '1':
            s = q[2] + s
        else:
            s = s + q[2]

print(s)

### FIXED CODE ###

s = input()
n = int(input())
re = 1
head = ''
tail = ''

for i in range(n):
    q = input().split()
    if q[0] == '1':
        re = re * -1
    else:
        if re == 1:
            if q[1] == '1':
                head = q[2] + head
            else:
                tail = tail + q[2]
        else:
            if q[1] == '1':
                tail = tail + q[2]
            else:
                head = q[2] + head

print(head+s+tail) if re == 1 else print((head+s+tail)[::-1])
### BUGGY CODE ###

s = input()
k = int(input())
def unit(s):
    """sの両端を外した状態でいくつ変えるか
    """
    count = 0
    prev = s[0]
    for c in s[1:]:
        if c==prev:
            count += 1
            prev = None
        else:
            prev = c
    return count
if len(s)==2:
    if s[0]==s[1]:
        print(k)
    else:
        print(0)
elif k==1:
    print(unit(s))
elif len(s)==1:
    print(k//2)
elif not s:
    print(0)
elif s[0]!=s[-1]:
    print(k * unit(s))
else:
    s0 = unit(s[1:-1])
    s1 = unit(s[1:])
    s2 = unit(s[:-1])
    s3 = unit(s)
    import numpy as np
    a = [0,0]
    b = [0,0]
    a[0] = s3
    a[1] = s1
    for n in range(2,k+1):
        b[0] = min(a[1]+s3, a[0]+s2) + 1
        b[1] = min(a[1]+s0, a[0]+s1) + 1
        a = b
    print(a[0])

### FIXED CODE ###

# AGC039A

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


s = input()
k = int(input())

def sub(s):
    if not s:
        return 0
    # 連続する文字のカウント
    prev = s[0]
    counts = []
    count = 1
    for c in s[1:]:
        if c==prev:
            count += 1
        else:
            counts.append(count)
            count = 1
        prev = c
    if count>=2:
        counts.append(count)
    return sum([item//2 for item in counts])

if s[0]!=s[-1]:
    ans = k * sub(s)
elif all(s[0]==s[i] for i in range(1, len(s))):
    ans = (k * len(s)) // 2
else:
    i = 0
    while s[i]==s[-1]:
        i += 1
    ss = s[i:] + s[:i]
    ans = sub(s[:i]) + (k-1)*sub(ss) + sub(s[i:])
print(ans)
#     s1 = s[:-1] + "A"
#     c1 = sub(s1)
#     s2 = "B" + s[1:]
#     c2 = sub(s2)
### BUGGY CODE ###

N, K = map(int, input().split())
[*h] = map(int, input().split())
dp = [float('inf') for _ in range(N)]
dp[0] = 0
for i in range(1, N):
    dp[i] = min([dp[i-j]+abs(h[i]-h[i-j]) for j in range(1, min(i, K)+1)])
print(dp[N-1])

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))
dp = np.zeros(N, dtype=int)
for i in range(1, N):
  j = max(0, i-K)
  dp[i] = np.min(dp[j:i]+np.abs(h[i]-h[j:i]))
                 
print(dp[N-1])
### BUGGY CODE ###

import sys
from collections import Counter
import math
import heapq
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

n = ni()
s = input()
d = {}
ln = len(s)
flag = False
for l in range(ln//2)[::-1]:
    for i in range(ln - l):
        c = s[i:i+l+1]
        if c not in d.keys():
            d[c] = i
        else:
            ll = len(c)
            if i >= d[c] + ll:
                print(len(c))
                flag = True
                break
    if flag:
        break
if flag is False:
    print(0)





### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

n = ni()
s = input()
dp = [[0] * 5005 for _ in range(5005)]
for i in range(n)[::-1]:
    for j in range(n)[::-1]:
        if s[i] != s[j]:
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i+1][j+1] + 1
ans = 0
for i in range(n):
    for j in range(n):
        if i >= j: continue
        now = min(dp[i][j], j-i)
        ans = max(ans, now)
print(ans)
### BUGGY CODE ###

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

n, m = map(int, input().split())
a = []
for _ in range(m):
    a.append(int(input()))

memo = {0:1}

for i in range(n):
    for j in range(i+1,min(i+2,n)+1):
        if j in a:
            continue
        if memo.get(i) is None:
            memo[i]=0
        if memo.get(j) is None:
            memo[j]=memo[i]
        else:
            memo[j]+=memo[i]
            


print(memo[n] % 1000000007)

### FIXED CODE ###

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

n, m = map(int, input().split())
a = []
for _ in range(m):
    a.append(int(input()))
a=set(a)

memo = [0]*(n+1)
memo[0]=1
if not(1 in a):
    memo[1]=1

for i in range(2,n+1):
    #print(i)
    if i in a:
        continue
    #print(memo[i-1],memo[i-2])
    memo[i]=memo[i-2]+memo[i-1]
            

#print(memo)
print(memo[n]% 1000000007)
### BUGGY CODE ###

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

cnt=0
if (a>0 and b<0) or (a<0 and b>0):
  ans="Zero"
elif a==0 or b==0:
  ans="Zero"
elif a>0 and b>0:
  ans="Positive"
elif a<0 and b<0:
  a,b=a*-1,b*-1
  for i in range(b,a+1):
    cnt+=1
  if cnt%2==0:
    ans="Positive"
  else:
    ans="Negative"
    
print(ans)

### FIXED CODE ###

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

if (a>0 and b<0) or (a<0 and b>0):
  ans="Zero"
elif a==0 or b==0:
  ans="Zero"
elif a>0 and b>0:
  ans="Positive"
elif a<0 and b<0:
  if (a%2==0 and b%2==0) or (a%2!=0 and b%2!=0):
    ans="Negative"
  else:
    ans="Positive"
    
print(ans)
### BUGGY CODE ###

import numpy as np
k = int(input())

ans = 0
for a in range(1,k+1):
  for b in range(1,k+1):
    tmp = np.gcd(a,b)
    for c in range(1,k+1):
      ans += np.gcd(tmp,c)

print(ans)


### FIXED CODE ###

import math
k = int(input())

ans = 0
for a in range(1,k+1):
  for b in range(1,k+1):
    tmp = math.gcd(a,b)
    for c in range(1,k+1):
      ans += math.gcd(c,tmp)

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

N,Q = map(int,input().split())
S = input()
 
for i in range(Q):
    l, r = map(int,input().split())
    str = S[l-1:r]
    print(str.count("AC"))

### FIXED CODE ###

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

count_list = [0]*(N+1)

for i in range(N):
    if S[i:i+2] == 'AC':
        count_list[i+1] = count_list[i] + 1
    else:
        count_list[i+1] = count_list[i]

for i in range(Q):
    l, r = map(int,input().split())
    print(count_list[r-1] - count_list[l-1])
### BUGGY CODE ###

S = input()
s, t = len(S), len(S)
words = ['dream', 'dreamer', 'erase', 'eraser']
while True:
  flg = True
  for i in range(t, -1, -1):
    if S[i:t] in words:
      t = i 
      flg = False
  if flg:
    print('NO')
    break
  if t == 0:
    print('YES')
    break

### FIXED CODE ###

S = input()
t = len(S)
words = ['dream', 'dreamer', 'erase', 'eraser']
while True:
  flg = True
  for i in range(t, -1, -1):
    if S[i:t] in words:
      t = i 
      flg = False
  if flg:
    print('NO')
    break
  if t == 0:
    print('YES')
    break
### BUGGY CODE ###

N = int(input())
L = [int(i) for i in input().split()]

def CheckTriangle(e):
  a,b,c=e
  return(a<b+c)*(b<c+a)*(c<a+b)

d = dict()
for i in range(0,N-2):
  for j in range(i+1,N-1):
    for k in range(j+1,N):
      e = tuple(sorted((L[i],L[j],L[k])))
      if CheckTriangle(e):
        d[e] = 1

print(len(d))

### FIXED CODE ###

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

from bisect import bisect_left 
cnt = 0
for i in range(0,N):
  for j in range(i+1,N):
    t = L[i]+L[j]
    idx = bisect_left(L,t)
    cnt += max(0,idx-j-1)
print(cnt)
### BUGGY CODE ###

if __name__ == "__main__":
    n, m = map(int, input().split())

    nexts = [[] for i in range(n)]
    
    for i in range(m):
        ai, bi = map(int, input().split())
        ai -= 1
        bi -= 1
        nexts[ai].append(bi)
        nexts[bi].append(ai)


    red_set = [0]
    new_red_set = []
    #blue_set = [x + 1 for x in range(n - 1)]
    #new_blue_set = blue_set
    blues = [0 for i in range(n)] # 0 is unceked
    blues[0] = 1 # 1 is checked

    arrows = [0] * n

    while 0 in blues:
        for r in red_set:
            for nxt in nexts[r]:
                if blues[nxt] == 0:
                    blues[nxt] = 1
                    if nxt not in new_red_set:
                        new_red_set.append(nxt)
                    arrows[nxt] = r

        red_set = new_red_set
        new_red_set = []
    
    print("Yes")
    for arrow in arrows[1:]:
        print(arrow + 1)
    

### FIXED CODE ###

from sys import stdin
from collections import deque
input = stdin.readline


def main():
    n, m = map(int, input().split())

    nexts = [[] for i in range(n)]
    
    for _ in range(m):
        ai, bi = map(int, input().split())
        ai -= 1
        bi -= 1
        nexts[ai].append(bi)
        nexts[bi].append(ai)

    blues = [-1] * n # 1 is in blues
    blues[0] = 0 # 0 is not in blues
    checked = [0] * n

    red_deque = deque([0])

    while len(red_deque) > 0:
        rd = red_deque[0]
        red_deque.popleft()
        if checked[rd] == 0:
            checked[rd] = 1
            for nxt in nexts[rd]:
                if blues[nxt] == -1:
                    blues[nxt] = rd
                    red_deque.append(nxt)

    print("Yes")
    for blue in blues[1:]:
        print(blue + 1)
    

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

import math
from functools import reduce

def gcd(*numbers):
	return reduce(math.gcd, numbers)

K = int(input())
S=0
for i in range(1,K+1):
	for h in range(1,K+1):
		for g in range(1,K+1):
			S+=gcd(g,h,i)

print(S)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
	return reduce(math.gcd, numbers)

K = int(input())
S=0
for i in range(1,K+1):
	for h in range(i,K+1):
		for g in range(h,K+1):

			if i==h and h==g:
				S+=gcd(g,h,i)
			elif i==h or h==g or g==i:
				S+=3*gcd(g,h,i)
			else:
				S+=6*gcd(g,h,i)
			
print(S)
### BUGGY CODE ###

N, Q = map(int,input().split())
S = input()
count = 0

for i in range(Q):
  l, r = map(int,input().split())
  Si = S[l-1:r]
  
  len_Si = len(Si)
  for i in range(len_Si-1):
    if Si[i] == 'A'and Si[i+1] == 'C':
      count += 1
  print(count)
  count = 0

### FIXED CODE ###

N, Q = map(int,input().split())
S = input()
t=[0]*(N+1)
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1] - t[l-1])
### BUGGY CODE ###

N = int(input())
H = [int(x) for x in input().split()]
C = [0]*N
for i in range(N):
  for j in range(i,N-1):
    if H[j] >= H[j+1]:
      C[i] += 1
    else:
      break
print(max(C))
    

### FIXED CODE ###

N = int(input())
H = [int(x) for x in input().split()]
m = 0
count = 0
for i in range(N-1):
  if H[i] >= H[i+1]:
    count += 1
  else:
    count = 0
  if count > m:
    m = count
print(m)
### BUGGY CODE ###

import sys
import math
import itertools

def main():
  n,k = map(int, input().split())
  a = list(map(int,sys.stdin.readline().split()))

  now = 0
  times = 0
  visit =[[0],[0]]

  for _ in range(k):
    times += 1
    now = a[now] - 1
    roop = 0
    roop_start = 0

    if now in visit[0]:
      roop_start = visit[1][visit[0].index(now)] #ループが始めった待ちの最初に訪れた時に何回ループしていたかをroop_startに代入
      roop = times - roop_start #何個の町でループしてるかをroopに代入
      break
    else:
      visit[0].append(now)
      visit[1].append(times)

  if roop > 0:
    k = (k - roop_start) % roop

  # print(roop_start)
  # print(roop)
  # print(k)
  # print(visit[0])
  print(visit[0][roop_start + k] + 1)

  # now = 0
  # for _ in range(roop_start):
  #   now = a[now] - 1

  # for _ in range(k):
  #   now = a[now] -1

  # print(now+1)


if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys
import math
import itertools

def main():
  n,k = map(int, input().split())
  a = list(map(int,sys.stdin.readline().split()))

  now = 0
  times = 0
  visit =[[0],[-1 for _ in range(n)]]
  visit[1][0] = 0
  roop = 0
  roop_start = 0

  for _ in range(k):
    times += 1
    now = a[now] - 1

    if visit[1][now] != -1:
      roop_start = visit[1][now] #ループが始めった待ちの最初に訪れた時に何回ループしていたかをroop_startに代入
      roop = times - roop_start #何個の町でループしてるかをroopに代入
      break
    else:
      visit[0].append(now)
      visit[1][now] = len(visit[0]) - 1

  if roop > 0:
    k = (k - roop_start) % roop

  # print(roop_start)
  # print(roop)
  # print(k)
  # print(visit[0])
  print(visit[0][roop_start + k] + 1)

  # now = 0
  # for _ in range(roop_start):
  #   now = a[now] - 1

  # for _ in range(k):
  #   now = a[now] -1

  # print(now+1)


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

import numpy as np
N, M = map(int, input().split())
L = [list(input().split()) for i in range(M)]
AC = np.array([L[j] for j in range(M) if [L[j][0], 'AC'] not in L[:j]])
print(np.count_nonzero(AC == 'AC', axis = 1), np.count_nonzero(AC == 'WA', axis = 1))

### FIXED CODE ###

N, M = map(int, input().split())
P = [0] * (N + 1)
S = [0] * (N + 1)
for i in range(M):
  x, p = input().split()
  s = int(x)
  if P[s] == 0:
    if p == 'AC':
      P[s] = 1
    else:
      S[s] += 1
A = sum([S[i] for i in range(N + 1) if P[i] == 1])
print(P.count(1), A)
### BUGGY CODE ###

n = int(input())
str = ['']*n
ans=0
for i in range(n):
    s=input()
    if s not in str:
        str[i]=s
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
str=[]

for i in range(n):
    str.append(input())

ans = len(set(str))

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

from bisect import bisect_left
from collections import defaultdict

N = int(input())

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

res = 0
pre_b = -1

num_a = defaultdict(int)
pre_num_c = defaultdict(int)
dict_C = defaultdict(int)

for b in B:
    dict_C[b] = C.count(b)
    num_a[b] = bisect_left(A, b)
    pre_num_c[b] = bisect_left(C, b)

for b in B:
    if b == pre_b:
        res += num_a_b * num_c_b
        continue
    num_a_b = num_a[b] # a < b となるAの要素数
    num_c_b = N - pre_num_c[b] # c > b となるAの要素数
    if pre_num_c[b] != N and C[pre_num_c[b]] == b:
        num_c_b -= dict_C[b]
    res += num_a_b * num_c_b
    pre_b = b
print(res)



### FIXED CODE ###

from bisect import bisect_left
from collections import defaultdict

N = int(input())

A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
num_a = 0
num_c = 0
res = 0
pre_b = -1

dict_C = defaultdict(int)


for b in B:
    if b == pre_b:
        res += num_a * num_c
        continue
    num_a = bisect_left(A, b) # a < b となるAの要素数
    pre_num_c = bisect_left(C, b)
    num_c = N - pre_num_c # c > b となるAの要素数
    if pre_num_c != N and C[pre_num_c] == b:
        num_c = N - bisect_left(C, b+1)
    res += num_a * num_c
    pre_b = b
print(res)