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

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

ans = 0
P = 10**9+7
bit = [0 for i in range(60)]

# 各bit独立に1が何個あるか数える
for i in range(N):
    S = bin(A[i])
    for j in range(1,len(S)-1):
        if S[-1*j] == '1':
            bit[j-1] += 1

# 各bitの1の個数と0の個数の積が、XOR和が1になる数字の個数と一致
for i,a in enumerate(bit):
    ans += a*(N-a)*(2**i)
    ans %= P

print(ans)



### FIXED CODE ###

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

ans = 0
P = 10**9+7
bit = [0 for i in range(70)]

# 各bit独立に1が何個あるか数える
for i in range(N):
    S = bin(A[i])
    for j in range(1,len(S)-1):
        if S[-1*j] == '1':
            bit[j-1] += 1

# 各bitの1の個数と0の個数の積が、XOR和が1になる数字の個数と一致
for i in range(70):
    ans += (2**i)*bit[i]*(N-bit[i])
    ans %= P

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

INF=10**30
N=int(input())
A=list(map(int,input().split()))
s=sum(A)
dp=[[-INF]*(s+1) for i in range(N+1)]
dp[0][0]=1000
for i in range(N):
    for j in range(s+1):
        if dp[i][j]==-INF:
            continue
        for x in range(j+1):
            dp[i+1][j-x]=max(dp[i+1][j-x],dp[i][j]+A[i]*x)
        for x in range(dp[i][j]//A[i]+1):
            dp[i+1][j+x]=max(dp[i+1][j+x],dp[i][j]-A[i]*x)
print(max(dp[N]))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
money=1000;kabu=0
i=0
while(i<N):
    j=i
    money,kabu=money-(money//A[i])*A[i],kabu+(money//A[i])
    while(j<N-1 and A[j]<=A[j+1]):
        j+=1
    money=money+kabu*A[j]
    kabu=0
    i=j+1
print(money)
### BUGGY CODE ###

n = int(input())
if n >= 2:
     prime_nums = [2]
     for i in range(3, n + 1):
         for p in prime_nums:
             if i % p == 0:
                 break
         else:
             prime_nums.append(i)
for x in prime_nums[::-1]:
    if n % x == 0:
        print(x + n//x - 2)
        break

### FIXED CODE ###

N = int(input())
val = []
for a in range(int(N**0.5)+1):
  b, mod = divmod(N, a+1)
  if mod == 0:
    val.append( (a+1) + b - 2 )
print(min(val))
### BUGGY CODE ###

# 問題文をよく読んで、制約をヒントに答えを導かないといけない問題

s = input()
K = int(input())

result = []

len_s = len(s)
for i in range(len_s):
  for j in range(min(len_s, 5)):
    if s[i:i+j+1]:
      result.append(s[i:i+j+1])

ans = []
for res in sorted(result):
  if not res in ans:
    ans.append(res)
    if len(ans) == K:
      print(ans[K-1])

### FIXED CODE ###

# 問題文をよく読んで、制約をヒントに答えを導かないといけない問題

s = input()
K = int(input())

result = []

len_s = len(s)
for i in range(len_s):
  for j in range(min(len_s, 5)):
    if s[i:i+j+1]:
      result.append(s[i:i+j+1])

ans = []
for res in sorted(result):
  if not res in ans:
    ans.append(res)
    if len(ans) == K:
      print(ans[K-1])
      exit()
### BUGGY CODE ###

import sys
a=int(input())
b=list(map(int,input().split()))

for i in range(a):
  for j in range(a):
    if i==j:
      pass
    else:
      
      if b[j]==b[i]:
        print('NO')
        sys.exit()
print('YES')

### FIXED CODE ###

a=int(input())
b=list(map(int,input().split()))
d=len(b)
c=len(set(b))
if c==d:
  print('YES')
else:
  print('NO')
### BUGGY CODE ###

N = int(input())
S = input()

# N = 39
# S = 'RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB'

# N = 4
# S = 'RRGB'

count = 0
for k in range(N-1, -1, -1):
    for j in range(k-1, -1, -1):
        for i in range(j-1, -1, -1):
            if j - i == k - j:
                continue
            if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                count += 1
print(count)


### FIXED CODE ###

N = int(input())
S = input()

# 方針
# S_i!=S_j!=S_kである全ての組み合わせ(i,j,k)からj-i=k-jの組み合わせを引く

r = S.count('R')
g = S.count('G')
b = S.count('B')

total_comb = r*g*b

count = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        # この時点でS_i=S_jであるのでスキップ
        if S[i] == S[j]:
            continue
        # kはiとjを定めれば一意に決まる
        k = 2 * j - i
        # kは単調増加なので、この時点でkがN-1より大きい場合、この(i,j)の組み合わせは計算しない
        if k > N - 1:
            break
        # 文字が同じであればスキップ
        if S[i] == S[k] or S[j] == S[k]:
            continue
        # ここでようやく、S_i != S_j != S_kかつj-i=k-jと判定できる
        count += 1

print(total_comb - count)
### BUGGY CODE ###

import itertools
import math
from functools import reduce

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

N = int(input())

l = list(range(1,N+1))
tap = list(itertools.product(l, repeat=3))
total = 0
for i in tap:
  total += gcd(i[0],i[1],i[2])
print(total)

### FIXED CODE ###

import math
ans = 0
n = int(input())

for i in range(1,n+1):
    for j in range(1,n+1):
        l = math.gcd(i,j)
        for k in range(1,n+1):
            ans += math.gcd(k,l)
print(ans)
### BUGGY CODE ###

from sys import stdin
n, q = [int(_) for _ in stdin.readline().rstrip().split()]
s = list(stdin.readline().rstrip())
data = [list(map(int, stdin.readline().rstrip().split())) for _ in range(q)]
for d in data:
    l = [0]
    sub_s = s[d[0]-1:d[1]]
    sub_n = len(sub_s)
    for i in range(sub_n):
        l.append(l[i]+1 if i+1 < sub_n and sub_s[i] == 'A' and sub_s[i+1] == 'C' else l[i])
    print(l[-1])

### FIXED CODE ###

from sys import stdin
n, q = [int(_) for _ in stdin.readline().rstrip().split()]
s = list(stdin.readline().rstrip())
data = [list(map(int, stdin.readline().rstrip().split())) for _ in range(q)]
l = [0]
for i in range(n):
    l.append(l[i]+1 if i+1 < n and s[i] == 'A' and s[i+1] == 'C' else l[i])
for d in data:
    print(l[d[1]-1]-l[d[0]-1])
### BUGGY CODE ###

N = int(input())

def f(n):
    total = 0
    for x in range(1,100):
        for y in range(1,100):
            for z in range(1,100):
                if x**2 + y**2 + z**2 + x*y + y*z + z*x == n:
                    total += 1
    return total

for i in range(1,N+1):
    print(f(i))

### FIXED CODE ###

N = int(input())


ans = [0]*(N+1)
i = 102
for x in range(1,i):
    for y in range(1,i):
        for z in range(1,i):
            total = (x + y + z)**2 - (x*y + y*z + x*z)
            if total <= N:
                ans[total] += 1

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

from collections import defaultdict,deque
import bisect
n,m,k=map(int,input().split())
F=defaultdict(set)
B=defaultdict(set)
for i in range(m):
   a,b=map(int,input().split())
   F[a].add(b)
   F[b].add(a)
for i in range(k):
   c,d=map(int,input().split())
   B[c].add(d)
   B[d].add(c)

ans=[0]*n
for i in F:
   V=set()
   for j in F[i]:
      que=deque([j])
      while que:
         s=que.pop()
         if s not in V:
            V.add(s)
            for k in F[s]:
               que.append(k)
   for j in B[i]:
      if j in V:
         V.remove(j)
   ans[i-1]=len(V)-len(F[i])-1
   
print(*ans)  

### FIXED CODE ###

import sys
from collections import defaultdict, deque
 
readline = sys.stdin.readline
n, m, k = map(int, readline().split())
# ab = [list(map(int, readline().split())) for i in range(m)]
# cd = [list(map(int, readline().split())) for i in range(k)]
 
friend = [set() for i in range(n)]
not_friend = [set() for i in range(n)]
 
suggest_friends = [-1] * n
for i in range(m):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    friend[a].add(b)
    friend[b].add(a)
    # friend[b].append(a)
for i in range(k):
    c, d = map(int, readline().split())
    c -= 1
    d -= 1
    not_friend[c].add(d)
    not_friend[d].add(c)
    # not_friend[d].append(c)
for i in range(n):
    if suggest_friends[i] != -1:
        continue
    q = deque(friend[i])
    friend_group = set(friend[i])
    while q:
        p = q.popleft()
        for f in friend[p]:
            if not(f in friend_group):
                q.append(f)
                friend_group.add(f)
    num = len(friend_group)
    for f in friend_group:
        suggest_friends[f] = num - 1 - len(friend[f] | not_friend[f] & friend_group)
 
for i in range(n):
    if suggest_friends[i] == -1:
        suggest_friends[i] = 0
print(*suggest_friends)
### BUGGY CODE ###

N = int(input())
XL = sorted(list(map(int, input().split())) for _ in range(N))

X = [xl[0] for xl in XL]
L = [xl[1] for xl in XL]

i = 0
count = N
while i < count - 1:
  if X[i] + L[i] > X[i+1] - L[i+1]:
    if X[i] + L[i] < X[i+1] + L[i+1]:
      del X[i+1]
      del L[i+1]
    else:
      del X[i]
      del L[i]
    count -= 1
  else:
    i += 1
print(count)

### FIXED CODE ###

N = int(input())
XL = sorted(list(map(int, input().split())) for _ in range(N))

i, j = 0, 1
count = N
while j < N:
  if XL[i][0] + XL[i][1] > XL[j][0] - XL[j][1]:
    if XL[i][0] + XL[i][1] < XL[j][0] + XL[j][1]:
      j += 1
    else:
      i, j = j, j + 1
    count -= 1
  else:
    i, j = j, j + 1
print(count)
### BUGGY CODE ###

N = int(input().split()[0])
aa = input().split()
bb = []

for i in range(1, N+1):
    for j in range(0, N):
        if int(aa[j]) == i:
            bb.append(j+1)
            break

print(*bb)

### FIXED CODE ###

N = int(input().split()[0])
aa = input().split()
bb = [0]*N

for i in range(0, N):
    bb[int(aa[i]) - 1] = i + 1

print(*bb)
### BUGGY CODE ###

H, W =  map(int, input().split())

S = []
for _ in range(H):
    tmp = list(input())
    S.append(tmp)
    
import numpy as np

Gs = np.asarray(S)
Gs_ = np.rot90(Gs, k=1)

def count_light(Gs, h, w):
    Gc = np.empty((h,w))
    for i, gs in enumerate(Gs):
        count = 0
        gc = []
        for j, s in enumerate(gs):
            if s == '#':
                count = 0
                Gc[i][j] = 0
            else:
                count += 1
                Gc[i][j] = count

    Gn = np.empty((h,w))
    for i, gc in enumerate(Gc):
        count = -1
        gn = []
        for j, c in enumerate(reversed(gc)):
            if c == 0:
                count = -1
                Gn[i][w-j-1] = 0
            else:
                if count == -1:
                    count = c
                Gn[i][w-j-1]  = count

    return Gn

Gn = count_light(Gs, H, W)
Gn_ = count_light(Gs_, W, H)
Gn_ = np.rot90(Gn_, k=-1)

Gsum = Gn+Gn_
ans = np.max(Gsum)-1

        
print(int(ans))

### FIXED CODE ###

H, W =  map(int, input().split())

S = []
for _ in range(H):
    tmp = list(input())
    S.append(tmp)
    
import numpy as np

def count_light(Gs, h, w):
    Gc = np.empty((h,w))
    for i in range(w):
        if i == 0:
            Gc[:, i] = Gs[:, i]
        else:
            Gc[:, i] = (Gc[:, i-1] + 1) * Gs[:, i]

    return Gc

Gs1 = np.asarray(S) == "."
Gn1 = count_light(Gs1, H, W)

Gs2 = np.rot90(Gs1, k=1)
Gn2 = count_light(Gs2, W, H)

Gs3 = np.rot90(Gs2, k=1)
Gn3 = count_light(Gs3, H, W)

Gs4 = np.rot90(Gs3, k=1)
Gn4 = count_light(Gs4, W, H)

Gn2 = np.rot90(Gn2, k=-1)
Gn3 = np.rot90(Gn3, k=-2)
Gn4 = np.rot90(Gn4, k=-3)

Gsum = Gn1+Gn2+Gn3+Gn4
ans = int(np.max(Gsum)-3)
print(ans)
### BUGGY CODE ###

import bisect
import numpy as np
N,M,Q = map(int,input().split())
lr = [0]*M
for i in range(M):
    l,r = map(int,input().split())
    lr[i] = [l,r]
lr = sorted(lr,key=lambda x:x[0])
lr_t = np.array(lr).transpose()
for i in range(Q):
    p,q = map(int,input().split())
    I = bisect.bisect_left(lr_t[0],p)
    r = sorted(lr_t[1][I:])
    I = bisect.bisect(r,q)
    print(len(r[:I]))

### FIXED CODE ###

import numpy as np
N,M,Q = map(int,input().split())
c = [[0]*(N+1) for i in range(N+1)]
for i in range(M):
    l,r = map(int,input().split())
    c[l][r] += 1
c = np.cumsum(np.cumsum(c,axis=0),axis=1)
for i in range(Q):
    p,q = map(int,input().split())
    print(c[q][q]-c[q][p-1]-c[p-1][q]+c[p-1][p-1])
### BUGGY CODE ###

import sys
 
# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())
 
def log(*args):
    print("DEBUG:", *args, file=sys.stderr)
 
def int_to_bits(x):
    return [ 1 if 2**i & x != 0 else 0 for i in range(60) ]
 
def inv(x, MOD):
    return pow(x, MOD-2, MOD)
 
MOD = 10**9+7
 
n,*A = get_all_int()
 
pow2 = [1] * 61
for i in range(1,61):
    pow2[i] = pow2[i-1] * 2
 
# ビットごとの出現回数 2**i
bits = [0] * 60
 
for a in A:
    for i in range(60):
        if pow2[i] & a != 0:
            bits[i] += 1
 
ans = 0
 
for a in A:
    for i in range(60):
        ans += pow(2,i,MOD) * abs(bits[i] - (1 if pow2[i] & a != 0 else 0) *n)
 
print(ans*inv(2,MOD) % MOD)

### FIXED CODE ###

import sys
import time

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def int_to_bits(x):
    return [ 1 if 2**i & x != 0 else 0 for i in range(60) ]

def inv(x, MOD):
    return pow(x, MOD-2, MOD)

start = time.time()

MOD = 10**9+7

debug = False

if debug:
    n = 30 * 10000
    A = list(range(n))
else:
    n,*A = get_all_int()

# ビットごとの出現回数 2**i
bits = [0] * 60

for a in A:
    for i in range(60):
        if 2**i & a != 0:
            bits[i] += 1

# log("bits:", bits)
# log("bits.", time.time() - start)

# ans = 0

ans = sum(( pow(2, i, MOD) * bits[i] * (n-bits[i]) for i in range(60))) % MOD

# for a in A:
#     # a_bits = [ 1 if 2**i & a != 0 else 0 for i in range(60) ]

#     for i in range(60):
#         ans += 2**i * abs(bits[i] - (1 if 2**i & a != 0 else 0) *n)

#     # a_dash = list(map(lambda a: a*(n-1), a_bits))

#     # log("a_dash", a_dash)

#     # bits_dash = [ bits[i] - a_bits[i] for i in range(60)]
#     # log("bits_dash", bits_dash)
#     # ans += sum( ( 2**i * abs(bits_dash[i]-2*a_dash[i])) for i in range(60) )

#     # ans += sum( ( 2**i * abs(bits[i]-2*a_dash[i])) for i in range(60) )

#     # for i in range(60):
#     #     ans = (ans + 2**i * abs(bits_dash[i] - a_dash[i])) % MOD
#     # log(a, ans)

# print(ans//2 % MOD)
print(ans)
# log("end.", time.time() - start)
### BUGGY CODE ###

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

pass_num_set = {}

for i in range(M):
    L, R = list(map(int, input().split()))
    if i == 0:
        pass_num_set = set(range(L, R + 1))
    else:
        pass_num_set = pass_num_set & set(range(L, R + 1))

ans = len(pass_num_set)

print(ans)

### FIXED CODE ###

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

L_list = []
R_list = []

for i in range(M):
    L, R = list(map(int, input().split()))
    L_list.append(L)
    R_list.append(R)
    
ans = max(min(R_list) - max(L_list) + 1, 0)

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

s = input()

for i in range(len(s)):
  for j in range(i,len(s)):
    if i !=j:
      li = {}
      for k in range(i,j+1):
        if s[k] not in li:
          li[s[k]] = 1
        else:
          li[s[k]] += 1
      if j-i+1 - max(li.values()) < max(li.values()):
        print(i+1,j+1)
        exit()
print(-1,-1)

### FIXED CODE ###

s = input()

if len(s) == 2:
  if s[0]==s[1]:
    print(1,2)
    exit()
  else:
    print(-1,-1)
    exit()

for i in range(len(s)-2):
  if s[i]==s[i+1]:
    print(i+1,i+2)
    exit()
  if s[i]==s[i+2]:
    print(i+1,i+3)
    exit()
print(-1,-1)
### BUGGY CODE ###

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

A = list(map(int, [K]*N))
s = [input() for i in range(Q)]

for i in s:
    A[int(i)-1] += 1
    num = 0
    for _ in A:
        A[num] -= 1
        num += 1

for i in A:
    if i <= 0:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

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

A = list(map(int, [K]*N))
s = [input() for i in range(Q)]

for i in s:
    A[int(i)-1] += 1

num = 0
for i in A:
    A[num] -= int(len(s))
    num += 1

for i in A:
    if i <= 0:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

from itertools import accumulate

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    N = 2* 10 ** 5
    K = N
    A = [0]*N
    arr = [0]*(N+1)

    for _ in range(K):
        arr = [0]*(N+1)
        for i, a in enumerate(A):
            left = max(0, i-a)
            right = min(N, i+a+1)
            arr[left] += 1
            arr[right] -= 1
        
        A = list(accumulate(arr[:-1]))
        if all(a == N for a in A):
           break

    print(*A[:-1], sep=" ")



if __name__ == "__main__":
    main()

### FIXED CODE ###

from itertools import accumulate

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    for _ in range(K):
        arr = [0]*(N+1)
        for i, a in enumerate(A):
            left = max(0, i-a)
            right = min(N, i+a+1)
            arr[left] += 1
            arr[right] -= 1
        
        A = list(accumulate(arr[:-1]))
        if all(a == N for a in A):
           break

    print(*A, sep=" ")



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

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

point = []
for i in range(K - 1, N):
    p = 1
    for j in range(i - (K - 1), i + 1):
        p = p * A[j]
    point.append(p)


for i in range(1, len(point)):
    if (point[i - 1] < point[i]):
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

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


for i in range(K, N):
    if (A[i - K] < A[i]):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

for i in range(N):
    rem = A[i]
    A.remove(rem)
    print(max(A))
    A.insert(i, rem)


### FIXED CODE ###

import copy

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

result = max(A)
ind = A.index(result)

for i in range(N):
    if i == ind:
        a = copy.deepcopy(A)
        a.remove(result)
        print(max(a))
    else:
        print(result)
### BUGGY CODE ###

I0 = lambda :map(int,input().split())
I1 = lambda :int(input())
I2 = lambda :list(map(int,input().split()))
#####################################################
n ,q = I0()
counter = [0]*n
tree = [[] for i in range(n)]
for i in range(n-1):
    a,b=I0()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

for i in range(q):
    p,x = I0()
    counter[p-1]+=x
    
stack = [0]
seen = dict()
seen[0] = 1
while stack:
    yy = stack.pop()
    for i in tree[yy]:
        if seen.get(i,-1) == -1:
            seen[i] = 1
            counter[i]+=counter[yy]
            stack.append(i)
            
print(*counter)



### FIXED CODE ###

I0 = lambda :map(int,input().split())
I1 = lambda :int(input())
I2 = lambda :list(map(int,input().split()))
#####################################################


from sys import stdin,setrecursionlimit
#from copy import deepcopy
 
setrecursionlimit(10**6)
input=stdin.readline

def dfs(p,father=-1):
    for i in tree[p]:
        if i == father:
            continue
        counter[i]+=counter[p]
        dfs(i,p)

n ,q = I0()
counter = [0]*n
tree = [[] for i in range(n)]
for i in range(n-1):
    a,b=I0()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

for i in range(q):
    p,x = I0()
    counter[p-1]+=x
    

dfs(0)

print(*counter)

'''stack = [1]
while stack:
    yy = stack.pop()
    for i in tree[yy]:
        counter[i-1]+=counter[yy-1]
        stack.append(i)'''
### BUGGY CODE ###

S = input()
Q = int(input())
QUERY = []
for i in range(Q):
    # q = list(map(int, input().split()))
    q = input().split()
    if q[0] == '1':
        QUERY.append([int(q[0])])
    else:
        QUERY.append([int(q[0]), int(q[1]), q[2]])

for q in QUERY:
    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()
Q = int(input())
QUERY = []
for i in range(Q):
    # q = list(map(int, input().split()))
    q = input().split()
    if q[0] == '1':
        QUERY.append([int(q[0])])
    else:
        QUERY.append([int(q[0]), int(q[1]), q[2]])

st = []
en = []
rev = False
rev_c = 0
for q in QUERY:
    if q[0] == 1:
        if rev:
            rev = False
        else:
            rev = True
        rev_c += 1
    else:
        if q[1] == 1:
            if not rev:
                st.append(q[2])
            else:
                en.append(q[2])
        else:
            if not rev:
                en.append(q[2])
            else:
                st.append(q[2])

# print(st)
# print(en)

st_s = "".join(st)
st_s = st_s[::-1]
en_s = "".join(en)

ans = st_s + S + en_s
if rev_c % 2 == 0:
    pass
else:
    ans = ans[::-1]

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

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

a=input().split()

l=len(a)

for i in range(0,l):
    a[i]=int(a[i])

p=1
h=[]
go=0
i=0
while(go==0):
    i+=1
    
    

    h.append(p)
    p=a[p-1]
    if i==k:
        break
    if p in h:
        j=h.index(p)
        amari=(k-i-1)%(i-j)
        p=h[j+amari]
        go=1
        break

if go==1:
    p=a[p-1]

print(p)


### FIXED CODE ###

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


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

ar=[-1 for i in range(n+1)]
p=1

go=0


for i in range(1,k+1):
    
    
    
    

    ar[p]=i-1
    p=a[p-1]
    
    if ar[p]>0:
        j=ar[p]
        amari=(k-i)%(i-j)
        
        go=1
        break

if go==1:
    p=ar.index(j+amari)
    
    


print(p)
### BUGGY CODE ###

n, k = map(int,input().split())
h = list(map(int, input().split()))

dp = [0] + [float("inf")]*(n-1)

for i in range(1, n):
    for j in range(max(0, i-k), i):
        dp[i] = min(dp[i], dp[j]+abs(h[i]-h[j]))

print(dp[-1])

### FIXED CODE ###

n, k = map(int,input().split())
h = list(map(int, input().split()))

dp = [0] + [float("inf")]*(n-1)

for i in range(1, n):
    for j in range(max(0, i-k), i):
        dp[i] = min(dp[i], dp[j]+abs(h[i]-h[j]))

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

n,q=map(int,input().split())
a=[]
b=[]
s=[0]


for i in range(0,n-1):
    A,B=map(int,input().split())
    a.append(A)
    b.append(B)
    s.append(0)
for i in range(0,q):
    P,X=map(int,input().split())
    s[P-1]=s[P-1]+X


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

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










### FIXED CODE ###

from operator import itemgetter
n,q=map(int,input().split())
a=[]
s=[0]


for i in range(n-1):
    a.append([int(j) for j in input().split()])
    s.append(0)

a.sort(key=itemgetter(0))

for i in range(0,q):
    P,X=map(int,input().split())
    s[P-1]=s[P-1]+X


for j in range(0,n-1):
    s[a[j][1]-1]=s[a[j][1]-1]+s[a[j][0]-1]


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

n = int(input())
l = sorted(list(map(int, input().split())))
ans=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]:
                ans += 1
            else:
                break
print(ans)

### FIXED CODE ###

import bisect
n = int(input())
l = sorted(list(map(int, input().split())))
ans=0
for i in range(n-2):
    for j in range(i+1,n-1):
        ans+=bisect.bisect_left(l, l[i] + l[j]) - j - 1
print(ans)
### BUGGY CODE ###

from bisect import bisect_left

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

p = [0] * (n + 1)
q = [] + p

L = [] + a[:n]
R = [] + a[n * 2:]
C = [] + a[n:n * 2]

p[0] = sum(L)
q[n] = sum(R)

L.sort()
R.sort()

for i in range(n):
    if C[i] > L[0]:
        p[i + 1] = p[i] + C[i] - L[0]
        del L[0]
        L.insert(bisect_left(L, C[i]), C[i])
    else:
        p[i + 1] = p[i]
    if C[n - 1 - i] < R[n -1]:
        q[n - 1 - i] = q[n - i] + C[n - 1 - i] - R[n - 1]
        del R[n - 1]
        R.insert(bisect_left(R, C[n - 1 - i]), C[n - 1 - i])
    else:
        q[n - 1 - i] = q[n - i]

ans = p[0] - q[0]
for i in range(1, n + 1):
    ans = max(ans, p[i] - q[i])

print(ans)



### FIXED CODE ###

import heapq

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

p = [0] * (n + 1)
q = [] + p

L = []
R = []
C = [] + a[n:n * 2]

for i in range(n):
    heapq.heappush(L, a[i])
    heapq.heappush(R, - a[n * 2 + i])

p[0] = sum(L)
q[n] = sum(R)
for i in range(n):
    if C[i] > L[0]:
        p[i + 1] = p[i] + C[i] - L[0]
        heapq.heappop(L)
        heapq.heappush(L, C[i])
    else:
        p[i + 1] = p[i]

    temp = C[n - 1 - i] * -1
    if temp > R[0]:
        q[n - 1 - i] = q[n - i] + temp - R[0]
        heapq.heappop(R)
        heapq.heappush(R, temp)
    else:
        q[n - 1 - i] = q[n - i]

ans = p[n] + q[n]
for i in range(n):
    ans = max(ans, p[i] + q[i])

print(ans)