Harryxun/stf_run huggingface dataset:
from math import log2
N, M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
B = max(max(Ai) for Ai in A)
if M == 1:
    if all(A[i][0] <= A[i+1][0] for i in range(N-1)):
        print("0")
    else:
        print("-1")
    exit(0)
logB = log2(B)
logBi = int(logB)
INF = 10**18
def gen(P, t):
    if t <= logB:
        for k in range(t):
            for i in range(M-1):
                P[i+1] += P[i]
    else:
        for k in range(t):
            for i in range(logBi+2):
                P[i+1] += P[i]
        for i in range(logBi+2, M):
            P[i] = INF
T = [0]*N
ans = 0
P = [0]*M
for i in range(N-1):
    a0, a1 = A[i][:2]
    b0, b1 = A[i+1][:2]
    if a0 < b0:
        continue
    if a0 > b0:
        ans = -1
        break
    t0 = T[i]
    v = max(t0*a0 + a1 - b1, 0)
    if v % b0 > 0:
        T[i+1] = t1 = (v + b0-1) // b0
        ans += t1
        continue

    t1 = v // b0
    if t0 < t1:
        P[:] = A[i+1]
        gen(P, t1 - t0)
        if P < A[i]:
            t1 += 1
    else:
        P[:] = A[i]
        gen(P, t0 - t1)
        if A[i+1] < P:
            t1 += 1
    T[i+1] = t1
    ans += t1
print(ans)


### FIXED CODE ###

import sys
readline = sys.stdin.readline
from math import log2
from itertools import accumulate
N, M = map(int, readline().split())
A = [list(map(int, readline().split())) for i in range(N)]
B = max(max(Ai) for Ai in A)
if M == 1:
    if N == 1 or all(A[i][0] < A[i+1][0] for i in range(N-1)):
        print("0")
    else:
        print("-1")
    exit(0)
logB = log2(B)
logBi = int(logB)
INF = 10**18
INFL = [INF]*(M - logBi-2)
def gen(P, t, L = min(logBi+2, M)):
    if t <= logB:
        for k in range(t):
            P[:] = accumulate(P)
    else:
        V = [1]*L
        for k in range(1, L):
            V[k] = V[k-1] * (t + k - 1)//k

        for i in range(L-1, 0, -1):
            P[i] += sum(P[j] * V[i-j] for j in range(i))
        if logBi+2 < M:
            P[logBi+2:] = INFL
T = [0]*N
ans = 0
P = [0]*M
for i in range(N-1):
    a0, a1 = A[i][:2]
    b0, b1 = A[i+1][:2]
    if a0 < b0:
        continue
    if a0 > b0:
        ans = -1
        break
    t0 = T[i]
    v = max(t0*a0 + a1 - b1, 0)
    if v % b0 > 0:
        T[i+1] = t1 = (v + b0-1) // b0
        ans += t1
        continue

    t1 = v // b0
    if t0 <= t1:
        P[:] = A[i+1]
        gen(P, t1 - t0)
        if P <= A[i]:
            t1 += 1
    else:
        P[:] = A[i]
        gen(P, t0 - t1)
        if A[i+1] <= P:
            t1 += 1
    T[i+1] = t1
    ans += t1
print(ans)
N = int(input())
S = input()
K = input()

moji = S[K-1]

for s in S:
  if moji == s:
    print(moji, end='')
  else:
    print('*', end='')
print()

### FIXED CODE ###

N = int(input())
S = input()
K = int(input())
 
moji = S[K-1]
ns = ''
for s in S:
  if moji == s:
    ns += moji
  else:
    ns += '*'
print(ns)
import sys
sys.setrecursionlimit(50000)
I=lambda:map(int,input().split())
n,m=I()
g=[[]for _ in range(n+1)]
v=[1 for _ in range(n+1)]
v[1]=0

for _ in range(m):
  a,b=I()
  g[a]+=[b]
  g[b]+=[a]

def dfs(x):
  for j in g[x]:
    if v[j]:
      v[j]=0
      return [j]+dfs(j)
      break
  else:
    return []
z=dfs(1)[::-1]+[1]+dfs(1)
print(len(z))
print(*z)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
I=lambda:map(int,input().split())
n,m=I()
g=[set() for _ in range(n+1)]
v=[1 for _ in range(n+1)]
v[1]=0

for _ in range(m):
  a,b=I()
  g[a].add(b)
  g[b].add(a)

def dfs(x):
  for j in g[x]:
    if v[j]:
      v[j]=0
      l=dfs(j)
      l.append(j)
      return l
      break
  else:
    return []
z=dfs(1)+[1]+dfs(1)[::-1]
print(len(z))
print(*z)
import numpy as np
def f(n, a):
    b = np.subtract.outer(a, a)
    c = np.triu(np.ones_like(b), 1) > 0
    if any(b[c] == 0):
        print('NO')
    else:
        print('YES')


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

f(n, a)


### FIXED CODE ###

import numpy as np
def f(n, a):
    if len(np.unique(a)) == n:
        print('YES')
    else:
        print('NO')

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

f(n, a)
from math import ceil
a,b=map(int,input().split())
print(ceil(a*b))

### FIXED CODE ###

A,B=input().split()
a=int(A)
b=B[0]+B[2]+B[3]
print(a*int(b)//100)
s = list(map(int,intput().split()))
s.sort

print(s[len(s)-1] - s[0])

### FIXED CODE ###

n = int(input())
s = list(map(int,input().split()))
s.sort()

print(s[len(s)-1] - s[0])
# coding: utf-8
# 整数の入力
#a = int(raw_input())
# スペース区切りの整数の入力
import numpy as np

N, MaxTotalWeight = map(int, raw_input().split())

def getWeightValuePair(W,Values,WeightValuePair):
    totalValue = 0
    WeightKeys = WeightValuePair.keys()
    WeightValuePairCopy = WeightValuePair.copy()
    for i in xrange(len(Values)):
        totalValue += Values[i]
        for totalWeight in WeightKeys:
            if (totalWeight + W * (i+1)) <= MaxTotalWeight:
                if (totalWeight + W * (i+1)) not in WeightValuePair:
                    WeightValuePair[totalWeight + W * (i+1)] = WeightValuePairCopy[totalWeight] +  totalValue
                elif WeightValuePairCopy[totalWeight] +  totalValue > WeightValuePairCopy[totalWeight + W * (i+1)]:
                    WeightValuePair[totalWeight + W * (i+1)] = WeightValuePairCopy[totalWeight] +  totalValue
    return WeightValuePair

Weights = []
WeightsValues = []

for i in xrange(N):
    tempData = map(int, raw_input().split())        
    if i == 0:
        Weights.append(tempData[0])
        Weights.append(tempData[0]+1)
        Weights.append(tempData[0]+2)
        Weights.append(tempData[0]+3)
        WeightsValues.append([tempData[1]])
        WeightsValues.append([])
        WeightsValues.append([])
        WeightsValues.append([])
    else:
        WeightsValues[tempData[0] - Weights[0]].append(tempData[1])

for data in WeightsValues:
    data.sort(reverse=True)

returnWeightValuePair = {0:0}
for i in range(4):
    returnWeightValuePair = getWeightValuePair(Weights[i],WeightsValues[i],returnWeightValuePair)

print max(returnWeightValuePair.values())

### FIXED CODE ###

N, W = map(int, raw_input().split())
X = [map(int, raw_input().split()) for _ in range(N)]
 
dp = {}
dp[0] = 0
 
for w, v in X:
    d = dp.copy()
    for k in d:
        if k + w > W:
            continue
        if k + w in dp:
            dp[k + w] = max(dp[k + w], d[k] + v)
        else:
            dp[k + w] = d[k] + v
 
print max(dp.values())
n,d=map(int,input().split())
def f(r):return r[0]**2+r[1]**2
print(sum(f(list(map(int,input().split())))<=d**2 for _ in range(n))

### FIXED CODE ###

n,d=map(int,input().split())
s=0
for _ in range(n):
  x,y=map(int,input().split())
  if x**2+y**2<=d**2:s+=1
print(s)
a=int(input().split())
if a[0]==c[2]:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a=input()
if a[0]==a[2]:
  print("Yes")
else:
  print("No")
def comb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


mod = 10**9+7  # 出力の制限
N = 10**4
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

for i in range(2, N + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod//i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)


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

appeared = set()
dup_right = 0
dup = 0
for i, x in enumerate(a):
    if x in appeared:
        dup_right = n - i
        dup = x
        break
    appeared.add(x)
dup_left = 0
for i, x in enumerate(a):
    if x == dup:
        dup_left = i
        break

print("dup_right", dup_right)
print("dup_left", dup_left)

print(n)
for i in range(2, n + 2):
    res = comb(n + 1, i, MOD)
    if dup_right + dup_left >= i - 1:
        res = res - comb(dup_right + dup_left, i - 1, MOD) % MOD
    print(res)


### FIXED CODE ###

def comb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


mod = 10**9+7  # 出力の制限
N = 10**6
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

for i in range(2, N + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod//i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)


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

appeared = set()
dup_right = 0
dup = 0
for i, x in enumerate(a):
    if x in appeared:
        dup_right = n - i
        dup = x
        break
    appeared.add(x)
dup_left = 0
for i, x in enumerate(a):
    if x == dup:
        dup_left = i
        break

for k in range(1, n + 2):
    print((comb(n + 1, k, MOD) - comb(dup_right + dup_left, k - 1, MOD) + MOD) % MOD)
cin = open(0).read().strip().split('\n')
n, m, q = map(int, cin[0].split(' '))
abcd = [tuple(map(int, a.split(' '))) for a in cin[1:]]

ret = 0
for case in itertools.combinations_with_replacement(list(range(1,m+1)), n):
    tmp = 0
    for c in abcd:
        if case[c[1]-1] - case[c[0]-1] == c[2]:
            tmp += c[3]
    ret = max(ret, tmp)
print(ret)

### FIXED CODE ###

cin = open(0).read().strip().split('\n')
n, m, q = map(int, cin[0].split(' '))
abcd = [tuple(map(int, a.split(' '))) for a in cin[1:]]

ret = 0
import itertools
for case in itertools.combinations_with_replacement(list(range(1,m+1)), n):
    tmp = 0
    for c in abcd:
        if case[c[1]-1] - case[c[0]-1] == c[2]:
            tmp += c[3]
    ret = max(ret, tmp)
print(ret)
a = list(map(int,input().split()))
N,K = a[0]-1,a[1]-1
 
if N/2 >= K:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

a = list(map(int,input().split()))
N,K = a[0]-1,a[1]-1
 
if N/2 >= K:
    print("YES")
else:
    print("NO")
import math
T1, T2 = map(int,input().split())
A1, A2 = map(int,input().split())
B1, B2 = map(int,input().split())

if A1*T1+A2*T2 == B1*T1+B2*T2:
    print('infinity')
elif (A1-B1)*T1/((A1-B1)*T1+(A2-B2)*T2) > 0:
    print(0)    
else:
    n = abs((A1-B1)*T1/((A1-B1)*T1+(A2-B2)*T2))
    meet = math.ceil(n) + int(n)
print(meet)   

### FIXED CODE ###

import math
T1, T2 = map(int,input().split())
A1, A2 = map(int,input().split())
B1, B2 = map(int,input().split())

if A1*T1+A2*T2 == B1*T1+B2*T2:
    print('infinity')
elif (A1-B1)*T1/((A1-B1)*T1+(A2-B2)*T2) > 0:
    print(0)    
else:
    n = abs((A1-B1)*T1/((A1-B1)*T1+(A2-B2)*T2))
    meet = math.ceil(n) + int(n)
    print(meet)
L = int(input())

print((L/3)**3

### FIXED CODE ###

L = int(input())

print((L/3)**3)
import sys
n=int(input())
s=[[int(i) for i in l.split()] for l in sys.stdin]
for cx in range(101):
  for cy in range(101):
    flag=True
    flag2=True
    for i in range(n):
      x,y,h=s[i]
      if x>=cx and y>=cy:
        H=h+x+y-cx-cy
      elif x>=cx:
        H=h+x-y-cx+cy
      elif y>=cy:
        H=h-x+y+cx-cy
      else:
        H=h-x-y+cx+cy
      if i==0:
        if h==0:
          flag2=False
        stack=H
        continue
      if h==0:
        if flag2==False:
          if H<stack:
            stack=H
          continue
        elif stack>H:
          flag=False
          break
      if flag2=False:
        if H>stack:
          flag=False
          break
        else:
          stack=H
          flag2=True
      if stack!=H:
        flag=False
        break
    if flag:
      print(cx,cy,H)
      exit()

### FIXED CODE ###

import sys
n=int(input())
s=[[int(i) for i in l.split()] for l in sys.stdin]
for cx in range(101):
  for cy in range(101):
    H=[]
    Z=[]
    for i in range(n):
      x,y,h=s[i]
      if h!=0:
        H.append(abs(x-cx)+abs(y-cy)+h)
      else:
        Z.append(abs(x-cx)+abs(y-cy))
    if len(Z)==0:
      Z.append(10**18)
    if H.count(H[0])==len(H) and min(Z)>=H[0]:
      print(cx,cy,H[0])
      exit()
A,B,C = (0,1,5,4),(1,2,4,3),(2,0,3,5)
D = (-1,3)

f = input().split()
input()
while True:
    t, s = map(f.index, input().split())
    if t in A and s in A:
        print(f[2]) if A.index(t) - A.index(s) in D else print(f[3])
    if t in B and s in B:
        print(f[0]) if B.index(t) - B.index(s) in D else print(f[5])
    if t in C and s in C:
        print(f[1]) if C.index(t) - C.index(s) in D else print(f[4])

### FIXED CODE ###

R = ((1,2,4,3),(2,0,3,5),(0,1,5,4))
f = input().split()

for i in range(int(input())):
    t, s = map(f.index, input().split())
    for j in R:
        if not (t in j)*(s in j):
            continue
        d = R.index(j)
        if (j.index(t) - j.index(s)) %4 == 1:
            d -= 5
    print(f[abs(d)])
n=[int(input()) for i in range(int(input()))]
print(sum(i for i in n)-int(max(l)/2))

### FIXED CODE ###

n=[int(input()) for i in range(int(input()))]
#print(n)
print(sum(i for i in n)-int(max(n)/2))
#!/usr/bin/env python3
import sys


def solve(X: int, K: int, D: int):
    X=abs(X)

    mostl = X - K * D
    if mostl > 0:
        print(mostl)
        exit()

    if K%2 == 1:
        X -= D
        ans = min(ans, abs(X), abs(X+2*D))
    else:
        ans = min(X, abs(X - K * D))

    Kh = K // 2

    N = X // (D*2)
    ans = min(ans, abs(X - D * 2 * (N - 1)))
    ans = min(ans, abs(X - D * 2 * N))
    if N < Kh:
        ans = min(ans, abs(X - D * 2 * (N + 1)))

    print(ans)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    solve(X, K, D)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(X: int, K: int, D: int):
    X=abs(X)

    mostl = X - K * D
    if mostl > 0:
        print(mostl)
        exit()

    if K%2 == 1:
        X -= D
        ans = min(abs(X), abs(X+2*D))
    else:
        ans = min(X, abs(X - K * D))

    Kh = K // 2

    N = X // (D*2)
    ans = min(ans, abs(X - D * 2 * (N - 1)))
    ans = min(ans, abs(X - D * 2 * N))
    if N < Kh:
        ans = min(ans, abs(X - D * 2 * (N + 1)))

    print(ans)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    solve(X, K, D)

if __name__ == '__main__':
    main()
from collections import Counter

class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
            

N, M = map(int, input().split())
UF = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    UF.par[a] = b
    
for i in range(N):
    _ = UF.find(i)
    
c = Counter(UF.par)
print(max(c.values()))

### FIXED CODE ###

from collections import Counter

class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
                
n, m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.union(a, b)

for i in range(n):
    uf.find(i)

c = Counter(uf.par)
print(max(c.values()))
s = input()
if s == "A" : s = "T"
else if s == "T" : s = "A"
else if s == "C" : s = "G"
else s = "C"
print(s)

### FIXED CODE ###

s = input()
if s == "A" : s = "T"
elif s == "T" : s = "A"
elif s == "C" : s = "G"
else : s = "C"
print(s)
#coding: utf-8
N = list(map(int, list(input())))
K = int(input())
if N[0] == 1:
    print(N[1])
else:
    print(N[0])

### FIXED CODE ###

#coding: utf-8
N = input()
K = int(input())
ans = 0
for i in range(min(K, len(N))):
    if int(N[i]) != 1:
        ans = N[i]
        #print(N[i])
        break
print(ans if ans != 0 else 1)
import itertools
import heapq
n,k = map(int,input().split())
a = list(map(int,input().split()))
if n>=2*k:
  a_plus = heapq.nlargest(k, a)
  a_minus = heapq.nsmallest(k, a)
  a_new = a_plus+a_minus
  comb = itertools.combinations(a_new,k)
else:
  comb = itertools.combinations(a,k)
  
l = []
for i in comb:
  l.append(list(i))
  
one = [1]*len(l)
for i in range(len(l)):
  for j in range(k):
    one[i]*=l[i][j]
    one=[one[i] for i]
    
l_max = max(one)
waru = 10**9 + 7
 
mod = l_max % waru
print(mod)

### FIXED CODE ###

import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero and k%2:
    ans = 0
  else:
    if k%2:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)
N = int(input())
A =  list(map(int, input().split()))
Q = int(input())
B = [0]*(Q+1)
C = [0]*(Q+1)
S = [0]*(Q+1)


for i in range(1,Q+1,1):
    B[i],C[i] = map(int,input().split())

a = [0]*(10**5)

for i in range(N):
    a[A[i]] += 1
    S[0] += A[i]

for i in range(1,Q+1,1):
    S[i] = S[i-1] + a[B[i]]*(C[i]-B[i])
    a[C[i]] = a[C[i]] + a[B[i]]
    a[B[i]] = 0
    print(S[i])

### FIXED CODE ###

N = int(input())
A =  list(map(int, input().split()))
Q = int(input())
B = [0]*(Q+1)
C = [0]*(Q+1)
S = [0]*(Q+1)


for i in range(1,Q+1,1):
    B[i],C[i] = map(int,input().split())

a = [0]*(10**5+3)

for i in range(N):
    a[A[i]] += 1
    S[0] += A[i]

for i in range(1,Q+1,1):
    S[i] = S[i-1] + a[B[i]]*(C[i]-B[i])
    a[C[i]] = a[C[i]] + a[B[i]]
    a[B[i]] = 0
    print(S[i])
N, K = map(int, input().split())
x = [int(i) for i in input().split()]
a = []
a2 = []
for i in x:
    if i < 0:
        a2.append(2 * abs(i))
    else:
        a.append(i)

if len(a2) == 0:
    print(a[K-1])
    exit()
a2 = sorted(a2)
c1 = float('inf')

for i, v in enumerate(a):
    i = i + 1
    c1 = min(c1, v + a2[K - i - 1])

b = []
b2 = []
for i in x:
    if i > 0:
        b2.append(2 * abs(i))
    else:
        b.append(-i)

if len(b2) == 0:
    print(b[K-1])
    exit()
b = sorted(b)
c2 = float('inf')
for i, v in enumerate(b):
    i = i + 1
    c2 = min(c2, v + b2[K - i - 1])

print(min(c1,c2))

### FIXED CODE ###

N, K = map(int, input().split())
x = [int(i) for i in input().split()]
ans = float('inf')
for i in range(N-K+1):
    l = x[i]
    r = x[i+K-1]
    a = abs(l) + abs(r - l)
    b = abs(r) + abs(r - l)
    ans = min(a,b,ans)
print(ans)
n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[10**10]*n
dp[0]=0
for i in range(1,n):
    for j in range(i-k,i):
        dp[i]=dp[j]+min(h[j]-h[i])
print(dp[n-1])


### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[10**5]*n
dp[0]=0
for i in range(1,n):
    dp[i]=min(dp[j]+abs(h[j]-h[i]) for j in range(max(0,i-k),i))
print(dp[n-1])
A,B,C=int(input().split())
if A=<C and B=>C:
  print('YES')
else:
  print('NO')


### FIXED CODE ###

A,B,C=map(int,input().split())
if A<=C and C<=B:
  print('Yes')
else:
  print('No')
import numpy as np 
import sys 

readline = sys.stdin.readline

N, K = map(int, readline().split())
A = list(map(int, readline().split()))

# 愚直にやると計算量O(K)でTLEになる
# 同じ街にいったら操作打ち切りで配列を完結させる

# Teleport順の配列を作る
teleport = {1: True}
next_town = 1
for i in range(K):
    next_town = A[next_town - 1] # next_townがintで与えられる
    try: # 辞書を使用してO[1]で判定する
        teleport[next_town]
        dupulicate_town = next_town
        # 辞書をリストに変換
        teleport = list(teleport.keys())
        dupulicate_index = teleport.index(dupulicate_town)
        dupulicate_list = teleport[dupulicate_index:]
        break
    except KeyError:
        teleport[next_town] = True


if len(teleport) - 1 == K:
    print(teleport[-1])
else: # ループに入る場合
    consumption = len(teleport) - 1
    roop_num = K - consumption
    roop_index = roop_num % len(dupulicate_list)
    if roop_index == 0:
        print(dupulicate_list[-1])
    else:
        print(dupulicate_list[roop_index - 1])



### FIXED CODE ###

import numpy as np 
import sys 

readline = sys.stdin.readline

N, K = map(int, readline().split())
A = list(map(int, readline().split()))

# 愚直にやると計算量O(K)でTLEになる
# 同じ街にいったら操作打ち切りで配列を完結させる

# Teleport順の配列を作る
teleport = {1: True}
next_town = 1
roop_exist = False
for i in range(K):
    next_town = A[next_town - 1] # next_townがintで与えられる
    try: # 辞書を使用してO[1]で判定する
        teleport[next_town]
        dupulicate_town = next_town
        # 辞書をリストに変換
        teleport = list(teleport.keys())
        dupulicate_index = teleport.index(dupulicate_town)
        dupulicate_list = teleport[dupulicate_index:]
        roop_exist = True
        break
    except KeyError:
        teleport[next_town] = True


# 最後の処理の前にリストに変換してしまう
if not roop_exist:
    teleport = list(teleport.keys())

if len(teleport) - 1 == K:
    print(teleport[-1])
else: # ループに入る場合
    consumption = len(teleport) - 1
    roop_num = K - consumption
    roop_index = roop_num % len(dupulicate_list)
    if roop_index == 0:
        print(dupulicate_list[-1])
    else:
        print(dupulicate_list[roop_index - 1])
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 6)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"
AL = al.upper()

a,b,x = I()

if a**2*b == 2*x:
  print(90-180/math.pi*math.atan(a/b))
elif a**2*b < 2*x:
  ama = x-a**2*b*0.5
  ran = 2*ama/(a**2)
  print(90-180/math.pi*math.atan(a/(b-ran)))
else:
  ran = 2*x/(a*b)
  print(90-180/math.pi*math.atan(ran/b))

### FIXED CODE ###

import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

a,b,x = I()

if (a**2*b)<=2*x:
    c = 2*(a**2*b-x)/a**3
else:
    c = (a*b**2)/(2*x)

print(math.degrees(math.atan(c)))
from collections import Counter
    ans = 0
    s = []
    N = int(input())
    for i in range(N):
    	tmp = []
    	string = input()
    	for st in string:
    		tmp.append(st)
    	s.append(tmp)
     
    for m in range(len(s)):
    	for n in range(len(s)):
    		if Counter(s[n])==Counter(s[m]) and s[m] != s[n]:
    			ans+=1
    print(int(ans/2))

### FIXED CODE ###

ans = 0
s = {}
N = int(input())
for i in range(N):
	tmp = []
	string = input()
	for st in string:
		tmp.append(st)
	tmp.sort()
	stmp = ''.join(tmp)
	if stmp in s and s[stmp] > 0:
		ans += s[stmp]
		s[stmp] = s[stmp]+1
	else:
		s[stmp] = 1
print(ans)