、Consider an inifite array, $a$, of positive numbers, $a_1,a_2,\ldots$, where each $a_i=i$. You can apply a permutation, ${p}$, of size $n$ (i.e., $n$ different numbers $1\leq p_1,\ldots,p_n\leq n$) to the $n$-element subset of your array from $a_1$ through $a_n$ in the following way:  

$(a_1,...,a_n)\rightarrow(a_{p_1},...,a_{p_n}).$ 

To get infinite array ${b}$, you must apply permutation ${p}$ to the first $n$ elements ($a_1$ to $a_n$), then to elements $a_2$ through ${a_{n+1}}$, then to elements $a_3$ through $a_{n+2}$, and so on, infinitely many times. 

Given the values of $n$, $m$, and ${p}$, find and print the value of $b_m$. See the Explanation section below for more detail. 

Note: This challenge uses $1$-based array indexing.

Input Format

The first line contains $2$ space-separated integers, $n$ and $m$, respectively. 

The second line contains $n$ space-separated integers describing the respective values of $p_1,p_2,\ldots,p_n$.

Constraints

$1\leq n\leq10^5$
$1\leq m\leq10^{18}$  
$1\leq p_1,p_2,\ldots,p_n\leq n$, and each $p_i$ is unique.  

Output Format

Print a single integer denoting the value of $b_m$.

Sample Input 0

2 10
2 1

Sample Output 0

11

Sample Input 1

3 1
2 3 1

Sample Output 1

2

Sample Input 2

3 10
2 3 1

Sample Output 2

10 

Explanation

Sample Case 0 has the following sequence of array transformations: 

$\mathbf{1}\:\mathbf{2}\:3\:4\:5\:6\:7\:8\:9\:10\:11\:12\ldots$ 

${2}\:\mathbf{1}\:\mathbf{3}\:4\:5\:6\:7\:8\:9\:10\:11\:12\ldots$ 

${2\:3}\:\mathbf{1}\:\mathbf{4}\:{5}\:{6}\:{7}\:{8}\:{9}\:{10}\:{11}\:{12}\ldots$ 

${2\:3}\:4\:\mathbf{1}\:\mathbf5\:{6}\:7\:8\:9\:\:{10}\:11\:{12}...$ 

${2\:3}\:4\:5\:\mathbf1\:6\:7\:8\:9\:10\:11\:12\ldots$ 

${2\:3\:4\:5\:6}\:\mathbf{1}\:\mathbf7\:{8}\:{9}\:{10}\:{11}\:{12}\ldots$ 

${2\:3\:4\:5}\:{67}\:\mathbf{1\:8}\:{9}\:{10}\:{11}\:{12}\ldots$ 

${2\:3}\:4\:5\:6\:7\:8\:\mathbf{1\:9}\:10\:11\:12\ldots$ 

${2\:3\:4\:5}\:6\:7\:8\:9\:\mathbf{1}\:\mathbf10\:11\:12\ldots$ 

$2\:3\:4\:5\:6\:7\:89\:10\:\mathbf{1}\:\mathbf{11}\:12\ldots$ 

${2\:3}\:4\:5\:6\:7\:8\:9\:10\:11\:\mathbf{1}\:\mathbf{12}\:\ldots$   

As you can see, each $b_i=a_i+1=i+1$. Thus, we know that $b_m=m+1=10+1=11$.

Sample Case 1 and Sample Case 2 have the following sequence of array transformations: 

$\mathbf{1}\:\mathbf{2}\:\mathbf{3}\:{4}\:5\:{6}\:{7}\:{8}\:{9}\:{10}\:{11}\:{12}\:{13}\ldots$ 

${2}\:\mathbf{3}\:\mathbf{1\:4}\:5\:6\:7\:8\:9\:10\:11\:12\:13\ldots$ 

${2}\:{1}\:\mathbf4\:\mathbf{3}\:\mathbf5\:6\:{7}\:{8}\:{9}\:{10}\:{11}\:{12}\:{13}\ldots$ 

$2\:1\:3\:\mathbf{5}\:\mathbf{4}\:\mathbf{6}\:{7}\:{8}\:{9}\:{10}\:{11}\:{12}\:{13}\ldots$ 

${2}\:1\:3\:4\:\mathbf6\:\mathbf5\:\mathbf7\:8\:9\:10\:11\:12\:13\ldots$ 

$2\:1\:3\:4\:5\:\mathbf{7}\:\mathbf{6\:8}\:{9}\:{10}\:{11}\:{12}\:{13}\ldots$ 

${2}\:1\:3\:45\:6\:\mathbf8\:\mathbf{7\:9}\:10\:11\:12\:13\ldots$ 

${2}\:{1}\:{3}\:{4}\:{5}\:{6}\:{7}\:\mathbf{9}\:\mathbf{8}\:\mathbf{10}\:{11}\:{12}\:13}\ldots$ 

${2}\:{1}\:{3}\:4\:5\:{6}\:{7}\:{8}\:\mathbf{10}\:\mathbf{9}\:\mathbf{11}\:12\:13}\ldots$ 

${2}\:1\:3\:45\:6\:7\:89\:\mathbf{11}\:\mathbf{10}\:\mathbf{12}\:13\ldots$ 

${2\:1\:3}\:4\:5\:6\:7\:89\:10\:\mathbf{12}\:\mathbf{11}\:\mathbf{13}\:\ldots$        

As you can see, $b_1=2$ and $b_{10}=10$.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Number theory


Solutions:
(n, m) = map(int, input().split())
(*p,) = map(lambda x: int(x) - 1, input().split())
p = p[1:] + p[:1]
order = []
idx = n - 1
while p[idx] != -1:
	order.append(p[idx])
	tmp = p[idx]
	p[idx] = -1
	idx = tmp
if m > len(order):
	print(m + (n - len(order)))
else:
	print(order[m - 1] + 1)


(n, m) = [int(t) for t in input().strip().split()]
p = [int(t) for t in input().strip().split()]
beg = m - 1
end = m + n - 1
curr = m - 1
while curr < end and beg >= 0:
	if curr >= beg:
		curr = p[curr - beg] + beg - 1
		beg -= 1
		end -= 1
print(curr + 1)
exit(0)
test = [i for i in range(n * 2 + 2)]
for beg in range(n + 2):
	test_temp = test.copy()
	for i in range(len(p)):
		try:
			test_temp[beg + i] = test[beg + p[i] - 1]
		except:
			print(beg, i, p[i], beg + p[i] - 1, len(test))
	test = test_temp
if m < n:
	print(test[m - 1] + 1)
else:
	print(m + test[n] - n)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


from time import time
from random import randrange, sample

def solve(p, n, m):
	r = m
	k = -1
	while k != n - 1 and r >= 0:
		k = p[k + 1]
		r -= 1
	return r + k + 1

def prod(M, a):
	N = len(a)
	b = [0] * N
	for i in range(N):
		for j in range(N):
			b[i] += M[i][j] * a[j]
	return b

def prod_m(A, B):
	N = len(A)
	C = [[0] * N for _ in range(N)]
	for i in range(N):
		for j in range(N):
			for k in range(N):
				C[i][j] += A[i][k] * B[k][j]
	return C

def identity(r):
	I = [[0] * r for _ in range(r)]
	for i in range(r):
		I[i][i] = 1
	return I

def diag_block(B):
	N = sum((len(b) for b in B))
	M = [[0] * N for _ in range(N)]
	offset = 0
	for b in B:
		s = len(b)
		for i in range(s):
			for j in range(s):
				M[offset + i][offset + j] = b[i][j]
		offset += s
	return M

def perm_matrix(p):
	N = len(p)
	P = [[0] * N for _ in range(N)]
	for i in range(N):
		P[i][p[i]] = 1
	return P

def brute_force_1(q, n, m):
	p = [0] * n
	for i in range(n):
		p[q[i]] = i
	t = [0] * n
	t[0] = 1
	e = [0] * (m - 1) + t
	P = perm_matrix(p)
	for r in reversed(range(m)):
		Q = diag_block([identity(r), P, identity(m - r - 1)])
		e = prod(Q, e)
	for i in range(m + n - 1):
		if e[i] == 1:
			return i + 1

def brute_force_2(p, n, m):
	a = list(range(n + m - 1))
	for i in range(m):
		a[i:i + n] = [a[i + p[j]] for j in range(n)]
	return a[m - 1] + 1
(n, m) = map(int, input().strip().split())
p = list(map(lambda x: int(x) - 1, input().strip().split()))
print(solve(p, n, m - 1) + 1)


def rond(p1, p2):
	return [p1[e - 1] for e in p2]

def recp(p, n, step, m):
	if step >= m:
		return (p, step)
	p1 = p + [n + step + k for k in range(step)]
	p2 = [k for k in range(1, step + 1)] + [e + step for e in p]
	p3 = rond(p1, p2)
	return recp(p3, n, 2 * step, m)

def perm(p, n):
	p1 = p + [n + 1]
	p2 = [1] + [e + 1 for e in p]
	p3 = rond(p1, p2)
	p4 = p3 + [n + 2, n + 3]
	p5 = [1, 2] + [e + 2 for e in p3]
	p6 = rond(p4, p5)
	return p6
(n, m) = map(int, input().split(' '))
p = list(map(int, input().split(' ')))
(p3, step) = recp(p, n, 1, m)
c = [i for i in range(1, len(p3))]
k = [i for i in range(1, len(p3) + m)]
for j in range(0, m, step):
	c = [k[i] for i in range(j, j + len(p3))]
	for i in range(len(p3)):
		k[i + j] = c[p3[i] - 1]
print(k[m - 1])


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


import sys
X = input().split(' ')
(n, m) = (int(X[0]), int(X[1]))
plist = [int(x) for x in input().split(' ')]
dlist = [plist[i] - i - 1 for i in range(n)]
p = 0
varylist = []
for k in range(n):
	if p >= n:
		break
	varylist.append(dlist[p])
	p += 1 + dlist[p]
l = len(varylist)
for i in range(1, l):
	varylist[i] = varylist[i] + varylist[i - 1]
result = m + varylist[min(l, m) - 1]
print(result)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


(n, m) = list(map(int, input().split()))
ps = list(map(int, input().split()))
d = dict()
for (i, val) in enumerate(ps):
	d[i + 1] = val
curr_perm = m
while m - curr_perm + 1 <= n and curr_perm >= 1:
	num = m - curr_perm + 1
	m = curr_perm + d[num] - 1
	curr_perm = curr_perm - 1
print(m)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


[n, m] = list(map(int, input().split(' ')))
p = list(map(int, input().split(' ')))
pinv = [0] * n
for i in range(n):
	p[i] -= 1
	pinv[p[i]] = i
pos2num = dict()
num2pos = dict()
num = 0
pos = 0
currstart = m
printed = False
while currstart > 0:
	if pos == n:
		printed = True
		print(currstart + n)
		break
	pos = p[pos] + 1
	currstart -= 1
if not printed:
	print(pos)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


(n, m) = [int(t) for t in input().strip().split()]
p = [int(t) for t in input().strip().split()]
beg = m - 1
end = m + n - 1
curr = m - 1
while curr < end and beg >= 0:
	if curr >= beg:
		curr = p[curr - beg] + beg - 1
		beg -= 1
		end -= 1
print(curr + 1)
exit(0)
test = [i for i in range(n * 2 + 2)]
for beg in range(n + 2):
	test_temp = test.copy()
	for i in range(len(p)):
		try:
			test_temp[beg + i] = test[beg + p[i] - 1]
		except:
			print(beg, i, p[i], beg + p[i] - 1, len(test))
	test = test_temp
if m < n:
	print(test[m - 1] + 1)
else:
	print(m + test[n] - n)


(n, m) = map(int, input().split())
(*p,) = map(lambda x: int(x) - 1, input().split())
p = p[1:] + p[:1]
order = []
idx = n - 1
while p[idx] != -1:
	order.append(p[idx])
	tmp = p[idx]
	p[idx] = -1
	idx = tmp
if m > len(order):
	print(m + (n - len(order)))
else:
	print(order[m - 1] + 1)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


(n, m) = map(int, input().split())
(*p,) = map(lambda x: int(x) - 1, input().split())
p = p[1:] + p[:1]
order = []
idx = n - 1
while p[idx] != -1:
	order.append(p[idx])
	tmp = p[idx]
	p[idx] = -1
	idx = tmp
if m > len(order):
	print(m + (n - len(order)))
else:
	print(order[m - 1] + 1)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


(n, m) = map(int, input().split())
p = list(map(int, input().split()))
x = 0
while m >= 1:
	m -= 1
	x = p[x]
	if x >= n:
		x += m
		break
print(x)


(n, m) = map(int, input().split())
ps = list(map(int, input().split()))
x = 0
for i in range(m):
	x += 1
	if x > n:
		x += m - i - 1
		break
	x = ps[x - 1]
print(x)