3871: 星际旅行(travel)

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:26 解决:3

题目描述

travel.in/travel.out
小 D 进入 CFS 学习一个月了,在这一个月中,小 D 表现非常优异,大家都认为他 是一个爱做作业,爱打游戏的,爱背单词,爱写作文,爱、爱、爱……的好孩子,为 了犒劳自己这么优秀,国庆期间,小 D 决定进行星际旅游。他被中国长征五号火箭送 到了 1 号星球,他在 1 号星球尽情玩乐,当他在 1 号星球玩腻了后他就会到其他星球 继续玩耍,星球间穿梭的唯一方式就是通过星际传输门,每个星球都有一个传送门, 但是这个门只能把他传送到对应的另外一个星球。 小 D 会在每个星球玩一天,第二天他会通过传输门到达另外一个星球旅游,传输 门传输可以视为瞬间移动,不需要时间。 经过若干天后小 D 终于累了,他想回地球做几道数学题来解解乏。于是我们需要 派宇宙飞船去对应的星球接小 D 回家做几道奥数题。 小 D 会在第 k 天告诉我们他累了,我们需要计算出把宇宙飞船去第几号星球去接小 D。所有星球都以 1 到 n 为编号。 


【样例解释】 在样例 1 中,第 1-8 天,小 D 每天所在星球旅游的编号是 1, 5, 3, 6, 4, 3, 6, 4 在样例 2 中,第 1-4 天小 D 每天所在星球旅游的编号是 1, 2, 2, 2 


【数据范围】 对于 20%的数据:n<=2; 对于 50%的数据:k<=10^5; 对于 100%的数据:n<=10^5,k<=2*10^9,1<=a[i]<=n;

输入

第一行输入两个正整数 n, k。表示星球数量和小 D 累了的天数。 第二行输入 n 个由空格隔开的正整数 ,在第 i 个星球的传送门可以把小 D 送到第 a[i] 个星球 【样例输入1】 5 4 2 2 3 4 5

输出

输出一个整数 x,表示第 k 天我们要去第 x 号星球接小 D。 【样例输入2】 2

样例输入 复制

6 8
5 2 6 3 3 4

样例输出 复制

4

来源/分类