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

import sys
input = sys.stdin.readline
S=input()
N=int(len(S))
for _ in list(S):
    A=S
    S=S.replace("0110","")
    S=S.replace("0101","")
    S=S.replace("10","")
    S=S.replace("01","")
    if A==S:
        break
print(N-int(len(S)))

### FIXED CODE ###

S=input()
print(min(S.count("0"),S.count("1"))*2)
### BUGGY CODE ###

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

mycnt = 0

for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1,N):
            if (L[i] < L[j] + L[k]) and (L[j] < L[k] + L[i]) and (L[k] < L[i] + L[j]):
                mycnt += 1
                #print(L[i], L[j],L[k])
print(mycnt)

### FIXED CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort(reverse=True)
 
ck = [0]*(N-2)
#print(L)

ans = 0
for i in range(N-2):
  j = i + 1
  k = N - 1
  #print(i,j,k)
  while j < k:
    if L[i]-L[j]-L[k] < 0:
      ans += k-j
      j += 1 
    else:
      k -=1
  
print(ans)
### BUGGY CODE ###

N,M,K = list(map(int,input().split(' ')))
friend = {}
bad = {}
friend_list = [0]*(N+1)
bad_list = [0]*(N+1)
group = {}

parent = [i for i in range(N+1)]

def find(i):
    while parent[i] != i:
        i = parent[i]
    return i

def union(i, j):
    i = find(i)
    j = find(j)
    parent[j] = i



for i in range(M):
    A,B = list(map(int,input().split(' ')))
    if A<B:
        friend[A*(10**5+1)+B]=1
    else:
        friend[A*(10**5+1)+B]=1
    friend_list[A]+=1
    friend_list[B]+=1
    
    union(A,B)

for i in range(K):
    A,B = list(map(int,input().split(' ')))
    if A<B:
        bad[A*(10**5+1)+B]=1
    else:
        bad[A*(10**5+1)+B]=1
    if find(A)==find(B):
        bad_list[A]+=1
        bad_list[B]+=1
    
    #union(A,B)



#print(parent)
#print('parent')
for i in range(1,N+1):
    oya = find(i)
    #print(oya)
    if oya in group:
        group[oya] = group[oya]+1
    else:
        group[oya]=1
#print('friend')
#print(friend_list)
#print('bad')
#print(bad_list) 
#print(group)

kouho = [0]*N

for i in range(1,N+1):
    oya = find(i)
    abc = group[oya]-friend_list[i]-bad_list[i]-1
    kouho[i-1] = abc

for k in kouho:
    print(k,end=" ")
print()


### FIXED CODE ###

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

friend_list = [0]*(N+1)
bad_list = [0]*(N+1)
group = {}

parent = [i for i in range(N+1)]

def find(i):
    rireki = []
    while parent[i] != i:
        rireki.append(i)
        i = parent[i]
    for r in rireki:
        parent[r]=i
    return i

def union(i, j):
    i = find(i)
    j = find(j)
    parent[j] = i



for i in range(M):
    A,B = list(map(int,input().split(' ')))
    friend_list[A]+=1
    friend_list[B]+=1
    
    union(A,B)

for i in range(1,N+1):
    oya = find(i)
    parent[i] = oya
    #print(oya)
    if oya in group:
        group[oya] = group[oya]+1
    else:
        group[oya]=1

for i in range(K):
    A,B = list(map(int,input().split(' ')))
    if find(A)==find(B):
        bad_list[A]+=1
        bad_list[B]+=1
    
    #union(A,B)



#print(parent)
#print('parent')

#print('friend')
#print(friend_list)
#print('bad')
#print(bad_list) 
#print(group)

kouho = [0]*N

for i in range(1,N+1):
    oya = find(i)
    abc = group[oya]-friend_list[i]-bad_list[i]-1
    kouho[i-1] = abc

for k in kouho:
    print(k,end=" ")
print()

#print(parent)
### BUGGY CODE ###

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


### FIXED CODE ###

import math

n = int(input())
s = 1
frag = 0
a = list(map(int, input().split()))
if(0 in a):
    print(0)
else:
    for i in range(len(a)):
        s *= a[i]
        if(s > 10**18):
            frag = 1
            break
    if(frag):
        print(-1)
    else:
        print(s)
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]

    # L[i][j]: このマスが光る時に左方向に照らされるマスの個数
    L = [[0]*W for _ in range(H)]
    R = [[0]*W for _ in range(H)]

    for i in range(H):
        for j in range(1,W):
            if S[i][j] == '.':
                if S[i][j-1] == '.': 
                    L[i][j] = L[i][j-1] + 1
            if S[i][W-j-1] == '.':
                if S[i][W-j] == '.': 
                    R[i][W-j-1] = R[i][W-j] + 1
    
    # U[i][j]: このマスが光る時に上方向に照らされるマスの個数
    U = [[0]*W for _ in range(H)]
    D = [[0]*W for _ in range(H)]

    for j in range(W):
        for i in range(1,H):
            if S[i][j] == '.':
                if S[i-1][j] == '.': 
                    U[i][j] = U[i-1][j] + 1
            if S[H-i-1][j] == '.':
                if S[H-i][j] == '.': 
                    D[H-i-1][j] = D[H-i][j] + 1
    ans = 0
    
    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                tmp = 1
                tmp += L[i][j] + R[i][j] + U[i][j] + D[i][j]
                ans = max(tmp,ans)
    
    print(ans)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]

    # L[i][j]: このマスが光る時に左方向に照らされるマスの個数
    L = [[0]*W for _ in range(H)]
    R = [[0]*W for _ in range(H)]

    for i in range(H):
        for j in range(1,W):
            if S[i][j] == '.':
                if S[i][j-1] == '.': 
                    L[i][j] = L[i][j-1] + 1
            if S[i][W-j-1] == '.':
                if S[i][W-j] == '.': 
                    R[i][W-j-1] = R[i][W-j] + 1
    
    # U[i][j]: このマスが光る時に上方向に照らされるマスの個数
    U = [[0]*W for _ in range(H)]
    D = [[0]*W for _ in range(H)]

    for j in range(W):
        for i in range(1,H):
            if S[i][j] == '.':
                if S[i-1][j] == '.': 
                    U[i][j] = U[i-1][j] + 1
            if S[H-i-1][j] == '.':
                if S[H-i][j] == '.': 
                    D[H-i-1][j] = D[H-i][j] + 1
    ans = 0
    
    for i in range(H):
        for j in range(W):
            tmp = 1
            tmp += L[i][j] + R[i][j] + U[i][j] + D[i][j]
            ans = max(tmp,ans)
    
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

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

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

jobs.sort(key = lambda x: x[0])

ans = 0
heap = []
for day in range(1,M+1):
	for i in jobs:		
		if i[0] == day:
			heappush(heap, -i[1])
		elif i[0] > day:
			break
    
	if len(heap) != 0:
		ans += -heappop(heap)

print(ans)

### FIXED CODE ###

from heapq import heappop, heappush
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
X = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x: x[0])

hq = []
ans, j = 0, 0

for i in range(1, M + 1):  # M - i 日後にするバイトを考える
    while (j < N) and (X[j][0] <= i):
        heappush(hq, -X[j][1])  # 候補の追加
        j += 1
    if len(hq):
        ans += -heappop(hq)  # 候補があるとき、候補から最大値を取り出す

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

N, M = map(int, raw_input().split())
A = []
for i in range(M):
    a = int(raw_input())
    A.append(a)

dp = []
dp = [0 for i in range(N + 1)]
dp[0] = 1

for i in range(N):
    if (i + 1) not in A and (i + 1) <= N:
        dp[i + 1] += dp[i]
    if (i + 2) not in A and (i + 2) <= N:
        dp[i + 2] += dp[i]


print str(dp[N]%1000000007)

### FIXED CODE ###

N, M = map(int, raw_input().split())
A = []
A = [0 for i in range(N + 1)]
for i in range(M):
    a = int(raw_input())
    A[a] = -1

dp = []
dp = [0 for i in range(N + 1)]
dp[0] = 1

for i in range(N):
    if (i + 1) <= N and A[i + 1] == 0:
        dp[i + 1] += dp[i]
    if (i + 2) <= N and A[i + 2] == 0:
        dp[i + 2] += dp[i]


print str(dp[N]%1000000007)
### BUGGY CODE ###

t1,t2=map(int,input().split())
a1,a2=map(int,input().split())
b1,b2=map(int,input().split())
if a1==b1 and b2==a2:print(0)
elif t1*(a1-b1)+t2*(-b2+a2)==0:print('infinity')
else:
    if t1*(a1-b1)+t2*(-b2+a2)<0:a1,a2,b1,b2=b1,b2,a1,a2
    if t1*(a1-b1)>0:print(0)
    else:
        #(ng,ok]type
        ok,ng=10**100000,-1
        ng,ok=ok,ng
        eps=10**(-8)
        while abs(ok-ng)>1:
            mid=(ok+ng)//2
            if t1*(b1-a1)-mid>=0:ok=mid
            else:ng=mid
        print(2*(mid//(t1*(a1-b1)+t2*(-b2+a2))+1)-1)

### FIXED CODE ###

t1,t2=map(int,input().split())
a1,a2=map(int,input().split())
b1,b2=map(int,input().split())
p=a1-b1
q=a2-b2
if p*t1+q*t2==0:print('infinity');exit()
elif p<0:p,q=-p,-q
#p>0
if p*t1+q*t2>0:print(0)
else:
    a=p*t1
    d=-(a+q*t2)
    print(2*(a//d)+int(not(not a%d)))
### BUGGY CODE ###

import numpy as np

n = int(input())
p = np.array(list(map(int, input().split())))

ans = 1

for i in range(1, p.shape[0]):
    tmp = p.copy()
    tmp = tmp - p[i]
    if tmp[:i+1].min() >= 0:
        ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
m = float('inf')
ans = 0

for p in P:
    if p <= m:
        ans += 1
        m = p

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

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    N, Q = LI()
    events = []
    for _ in range(N):
        s, t, x = LI()
        s -= x + 0.5
        t -= x + 0.5
        events.append([s, x])
        events.append([t, -x])
    for _ in range(Q):
        d = II()
        events.append([d, 0])
    events.sort()
    dst = {INF}
    for t, x in events:
        if x == 0: # query
            y = min(dst)
            if y == INF:
                y = -1
            print(y)
        elif x > 0: # add
            dst.add(x)
        else: # x < 0, delete
            dst.remove(-x)
    return

main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        s, t, x = LI()
        s -= x
        t -= x
        XST.append([x, s, t])
    D = []
    for _ in range(Q):
        D.append(II())
    ans = [-1] * Q
    nexts = [-1] * Q
    XST.sort()
    for x, s, t in XST:
        i = bisect_left(D, s)
        end = bisect_left(D, t)
        while i < end:
            if nexts[i] == -1:
                ans[i] = x
                nexts[i] = end
                i += 1
            else:
                i = nexts[i]
    for y in ans:
        print(y)
    return

main()
### BUGGY CODE ###

import numpy as np
n=int(input())
a= [int(i) for i in input().split()]
b=np.array(a)
for i in range(1,n+1):
    print(np.count_nonzero(b==i))

### FIXED CODE ###

n=int(input())
a= [int(i) for i in input().split()]
b=[0]*n
for i in a:
    b[i-1]+=1
for j in range(n):
    print(b[j])
### BUGGY CODE ###

from collections import Counter
n = int(input())
s = []
for i in range(n):
    s.append(input())

ans = 0
for i in range(n):
    for j in range(i+1,n):
        if Counter(s[i]) == Counter(s[j]):
            ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
d = {}
for _ in range(n):
    s = ''.join(sorted(input()))
    if s not in d:
        d[s] = 0
    d[s] += 1



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

import heapq
def sol(inp=input):
    n,m=map(int,inp().split())
    G={i+1:set() for i in range(n)}
    for _ in range(m):
        i,j=map(int,inp().split())
        G[i].add(j)
    s,t=map(int,inp().split())
    cache_kenken={}
    def kenken(v):
        if v not in cache_kenken:
            cache_kenken[v]=set(v2 for v1 in G[v] for v2 in G[v1])
        return cache_kenken[v]
    def kenkenpa(v):
        return set(v3 for v2 in kenken(v) for v3 in G[v2])
    visited={s}
    revisited=set()
    v_steps=[]
    visited_pa={s}
    que=[]
    heapq.heappush(que,(0,s))
    while len(que)>0:
        step,u=heapq.heappop(que)
        for v in kenkenpa(u):
            if v not in visited:
                visited.add(v)
                v_steps.append((step+1,v))
                heapq.heappush(que,(step+1,v))
            if v==t:
                return step+1
            if v not in visited:
                visited.add(v)
    return -1
print(sol())

### FIXED CODE ###

import heapq
def sol(inp=input):
    s=3
    n,m=map(int,inp().split())
    G={(i+1,j):set() for i in range(n) for j in range(s)}
    for _ in range(m):
        u,v=map(int,inp().split())
        for i in range(s):
            G[(u,i)].add((v,(i+1)%s))
    s,t=map(int,inp().split())
    visited={(s,0)}
    que=[]
    heapq.heappush(que,(0,(s,0)))
    while len(que)>0:
        step,u=heapq.heappop(que)
        for v in G[u]:
            if v not in visited:
                visited.add(v)
                heapq.heappush(que,(step+1,v))
            if v==(t,0):
                return (step+1)//3
    return -1
print(sol())
### BUGGY CODE ###

MOD=998244353
N=int(input())
A=[int(input()) for _ in range(N)]

TOTAL=pow(3,N,MOD)
ASum=sum(A)

dp=[[0 for _ in range(ASum+1)] for _ in range(2)]
dp[0][0] = 2
dp[0][A[0]] = 1

dpOther=[[0 for _ in range(ASum+1)] for _ in range(2)]
dpOther[0][0] = 1
dpOther[0][A[0]] = 1

prev=0
current=1
curMax=A[0]

bEven = (ASum%2==0)

for n in range(1,N):
	curMax += A[n]
	current = n % 2
	prev = (n+1) % 2
	for e in range(curMax+1):
		dp[current][e] = dp[prev][e]*2
		if A[n] <= e:
			dp[current][e] += dp[prev][e-A[n]]
		while MOD < dp[current][e]:
			dp[current][e] -= MOD

		if bEven:
			dpOther[current][e] = dpOther[prev][e]
			if A[n] <= e:
				dpOther[current][e] += dpOther[prev][e-A[n]]
			while MOD < dpOther[current][e]:
				dpOther[current][e] -= MOD

sumStart = 0
plus = 0

if bEven:
	# 合計が偶数
	sumStart=ASum//2
	plus = (dpOther[current][ASum//2]*3) % MOD
else:
	# 合計が奇数の場合、ceil
	sumStart=ASum//2+1

exceptCnt=0
for s in range(sumStart,ASum+1):
	exceptCnt = (exceptCnt + dp[current][s]*3) % MOD

exceptCnt -= plus

print((TOTAL - exceptCnt) % MOD )



### FIXED CODE ###

import numpy as np

MOD=998244353
N=int(input())
A=np.array([int(input()) for _ in range(N)])
TOTAL=pow(3,N,MOD)
ASum=sum(A)
sumEnd=0
sumEnd=ASum//2+1

dp=np.array([0 for _ in range(sumEnd)],dtype=np.int64)
dp[0] = 1

for n in range(N):
	dp[A[n]:] += dp[:-A[n]]*2 % MOD

plus = 0
if ASum % 2 == 0:
	# 合計が偶数
	dpOther=np.array([0 for _ in range(sumEnd+1)],dtype=np.int64)
	dpOther[0] = 1
	for n in range(N):
		dpOther[A[n]:] += dpOther[:-A[n]] % MOD
	plus = (dpOther[ASum//2]*3) % MOD

exceptCnt=0
for s in range(0,sumEnd):
	exceptCnt = (exceptCnt + dp[s]*3) % MOD

exceptCnt -= plus
print((TOTAL - exceptCnt) % MOD )
### BUGGY CODE ###

N = int(input())
A = list(int(x) for x in input().split())
ans = []
for i in range(N):
    b = A.index(i + 1)
    ans.append(b)
for i in range(N):
    c = ans[i] + 1
    print(c)

### FIXED CODE ###

N = int(input())
A = list(int(x) for x in input().split())
ans = [None] * N
for i in range(N):
    ans[A[i] - 1] = i + 1
for i in range(N):
    print(ans[i])
### BUGGY CODE ###

import math
import os
import sys
from collections import deque

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

H, W, K = list(map(int, sys.stdin.readline().split()))
A = np.array([list(sys.stdin.readline().rstrip()) for _ in range(H)], dtype='S1')

[sh], [sw] = np.where(A == b'S')
A = (A == b'.').tolist()


def step(h, w):
    return math.ceil(min(h, w, H - h - 1, W - w - 1) / K)


def ok(h, w):
    return 0 <= h < H and 0 <= w < W


dh = [0, 1, 0, -1]
dw = [1, 0, -1, 0]

# 最初の魔法でどこまで端にいけるか
que = deque([(sh, sw, K)])
seen = [[0] * W for _ in range(H)]
seen[sh][sw] = True
min_step = step(sh, sw)
while que:
    sh, sw, k = que.popleft()
    for hh, ww in zip(dh, dw):
        h = sh + hh
        w = sw + ww
        if not ok(h, w) or not A[h][w] or seen[h][w]:
            continue
        if k > 0:
            min_step = min(min_step, step(h, w))
            seen[h][w] = True
            que.append((h, w, k - 1))
print(min_step + 1)


### FIXED CODE ###

import math
import os
import sys
from collections import deque

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

H, W, K = list(map(int, sys.stdin.readline().split()))
A = [sys.stdin.readline().rstrip() for _ in range(H)]

sh = sw = -1
for h, r in enumerate(A):
    if 'S' in r:
        sh = h
        sw = r.index('S')


def step(h, w):
    return math.ceil(min(h, w, H - h - 1, W - w - 1) / K)


def ok(h, w):
    return 0 <= h < H and 0 <= w < W


dh = [0, 1, 0, -1]
dw = [1, 0, -1, 0]

# 最初の魔法でどこまで端にいけるか
que = deque([(sh, sw, K)])
seen = [[0] * W for _ in range(H)]
seen[sh][sw] = True
min_step = step(sh, sw)
while que:
    sh, sw, k = que.popleft()
    for hh, ww in zip(dh, dw):
        h = sh + hh
        w = sw + ww
        if not ok(h, w) or A[h][w] == '#' or seen[h][w]:
            continue
        if k > 0:
            min_step = min(min_step, step(h, w))
            seen[h][w] = True
            que.append((h, w, k - 1))
print(min_step + 1)
### BUGGY CODE ###

N, K, Q = map(int, input().split())
person = [K] * N

for i in range(Q):
    ok_person = int(input()) - 1
    for j in range(N):
        if j != ok_person:
            person[j] -= 1

for i in range(N):
    if person[i] > 0:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

import numpy as np

N, K, Q = map(int, input().split())
person = np.asarray([K] * N)

ok_person = [int(input()) for i in range(Q)]
false_num = len(ok_person)
person -= false_num
#print(person)
for i in ok_person:
    person[i-1] += 1
#    print(person)

#print(person)

for i in range(N):
    if person[i] > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import math

K = int(input())

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

print(ans)

### FIXED CODE ###

def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a

K = int(input())

ans = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            ans += gcd(gcd(a, b),c)

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

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

A.sort()
flag=[0]*N
ans=0
for i in range(N):
    if i!=N-1:
        if A[i]==A[i+1]:
            flag[i]=1
    
    for j in range(i+1,N):
        if flag[j]==1:
            continue
        else:
            if A[j]%A[i]==0:
                flag[j]=1
print(flag.count(0))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort()
flag=[0]*N

ans=0
M=A[-1]
B=[0]*(M+1)
for i in A:
    B[i]+=1

for i in A:
    if B[i]==1:
        ans+=1
    for j in range(i,M+1,i):
        B[j]+=1
print(ans)
### BUGGY CODE ###


def main():
    n,k = map(int,input().split())
    dests =[0 for _ in range(n)]
    telepos = list(map(int,input().split()))
    for i,t in enumerate(telepos):
        dests[i] = t-1
    print(solve(dests,k))




def solve(dests,k,here = 0):
    here = 0
    telepo_times = 0
    cycle_start = -1
    cycle_end = -1
    cycle_length = -1
    visited = []
    ids = dict()


    #循環検出！同じ町にいつ戻ってくるのか
    while telepo_times < k:
        #print("現在地は",here)
        if here in visited:
            cycle_start = ids[here]
            #print(cycle_start,"でループが始まった")
            cycle_end = telepo_times - 1
            #print(cycle_end,"でループが終わった")
            cycle_length = cycle_end - cycle_start + 1
            #print("サイクルの長さは",cycle_length,"だ")
            break
        ids[here] = telepo_times

        visited.append(here)
        telepo_times += 1
        here = dests[here]
    if cycle_length == -1:
        return here + 1

    cycle_index = (k-cycle_start) % cycle_length
    return visited[cycle_start + cycle_index] + 1




    #telepo_times = 0
    #while telepo_times < (k - cycle_start)%cycle_length:
    #    telepo_times += 1
    #    here = dests[here]







if __name__ == '__main__':
    main()


### FIXED CODE ###


def main():
    n,k = map(int,input().split())
    dests =[0 for _ in range(n)]
    telepos = list(map(int,input().split()))
    for i,t in enumerate(telepos):
        dests[i] = t-1
    print(solve(dests,k))




def solve(dests,k,here = 0):
    here = 0
    telepo_times = 0
    cycle_start = -1
    cycle_end = -1
    cycle_length = -1
    visited = dict()
    visited2 = []


    #循環検出！同じ町にいつ戻ってくるのか
    while telepo_times < k:
        #print("現在地は",here)
        if here in visited:
            cycle_start = visited[here]
            #print(cycle_start,"でループが始まった")
            cycle_end = telepo_times - 1
            #print(cycle_end,"でループが終わった")
            cycle_length = cycle_end - cycle_start + 1
            #print("サイクルの長さは",cycle_length,"だ")
            break
        #ids[here] = telepo_times

        visited[here] = telepo_times
        visited2.append(here)
        telepo_times += 1
        here = dests[here]
    if cycle_length == -1:
        return here + 1

    cycle_index = (k-cycle_start) % cycle_length
    return visited2[cycle_start + cycle_index] + 1




    #telepo_times = 0
    #while telepo_times < (k - cycle_start)%cycle_length:
    #    telepo_times += 1
    #    here = dests[here]







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

from functools import reduce

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
ans = 0

def gcd(a, b):
    # 大きい方を被除数、小さい方を除数とする
    dividend = max(a, b)
    divider = min(a, b)

    if divider == 0:
        return dividend

    # 最大公約数を見つけるまで繰り返す
    while dividend % divider != 0:
        # 除算を行い、その除数を次回の被除数、剰余を次回の除数として処理を繰り返す
        r = dividend % divider
        dividend = divider
        divider = r

    # 一方がもう一方を割り切れた時点で、その除数を最大公約数とみなせる
    return divider


def lcm(a, b):
    return (a * b) // gcd(a, b)

L = reduce(lcm, a)

# print(L)

for i in range(n):
    ans += (L // a[i])
    # ans %= mod

print(ans % mod)

### FIXED CODE ###

from functools import reduce

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
ans = 0

def gcd(a, b):
    # 大きい方を被除数、小さい方を除数とする
    dividend = max(a, b)
    divider = min(a, b)

    if divider == 0:
        return dividend

    # 最大公約数を見つけるまで繰り返す
    while dividend % divider != 0:
        # 除算を行い、その除数を次回の被除数、剰余を次回の除数として処理を繰り返す
        r = dividend % divider
        dividend = divider
        divider = r

    # 一方がもう一方を割り切れた時点で、その除数を最大公約数とみなせる
    return divider


def lcm(a, b):
    return (a * b) // gcd(a, b)

def modinv(x):
    return pow(x, mod-2, mod)

b = list(set(a))
# for i in range(n):

# L = reduce(lcm, a)
L = reduce(lcm, b)

# print(L)

for i in range(n):
    # ans += (L // a[i])
    ans += L * modinv(a[i])

print(ans % mod)
### BUGGY CODE ###

from statistics import median

test = [0, 1, 2, 3, 4, 5]

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

for i in range(len(x)):
    print(median(x[:i] + x[i+1:]))


### FIXED CODE ###

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

y = sorted(x)
a = y[len(x)//2]
b = y[(len(x)//2) - 1]

for i in range(n):
    if x[i] <= b:
        print(a)
    else:
        print(b)