問題文
三上君正在使用一本可疑的英语词汇书。那本词汇书里 包含 N 单词的含义。 i 的描述为“word 它只是说:“它与 b_i 具有相同的含义。”在这里,i 字 我们称之为 i 。 三上君一个英文单词都不懂,所以 当我试图找出 i 的含义时,这个词 尝试找出 b_i 的含义。三上君很认真,所以他继续以同样的方式查找单词,即使他已经尝试过查找它们。 然而,不幸的是,英语单词的含义没有写在这本词典中,所以不可能知道它们的含义。 某个词 当我尝试查找 i 时,我查了词汇书并找到了这个词 第一步是尝试检查 b_i 。
三上君是一个词 当试图找出 i 时,k 每一步之后,三上将查找哪个单词?
入出力
输入是按以下格式从标准输入给出的。
N a k b_1 b_2 … b_N
- 1 行中的字数 N (2 ≦ N ≦ 10^5) 以及三上君想要找出的单词的编号。 a (1 ≦ a ≦ N) 用空格分隔。
- 2 Mikami-kun 搜索单词的步数 k(1 ≦ k ≦ 10^{100000}) 。
- 3 行显示每个单词的解释。 N 整数 b_1,...,b_N 用空格分隔。
- 1 ≦ b_i ≦ N かつ b_i ≠ i (1 ≦ i ≦ N) 有保证。 在尝试找出
部分点
针对此问题设置了部分分数。
- k ≦ 10^{18} 的数据集 50 点。 如果您对除上述数据集之外的所有满足
出力
三上君是一个词 当试图找出 a 之后 k 在每一步之后,输入您要查找的单词的编号。 在 1 行输出。还在输出末尾添加换行符。
入力例1
6 4 5 2 3 1 2 6 5
出力例1
3
Mikami-kun 按以下步骤查找单词。
1 在这一步,这个词 要了解 4 的含义,请使用该词 尝试检查 2 。
2 在这一步,这个词 要了解 2 的含义,请使用该词 尝试检查 3 。
3 在这一步,这个词 要了解 3 的含义,请使用该词 尝试检查 1 。
4 在这一步,这个词 要了解 1 的含义,请使用该词 尝试检查 2 。
5 在这一步,这个词 要了解 2 的含义,请使用该词 尝试检查 3 。
因此,5 通过台阶后,三上君会说出这句话 我正在尝试找出 3 。
入力例2
4 1 100000000000000000000 2 3 4 1
出力例2
1
k 可能非常大。 维度平面上的
入力例3
8 1 1 2 3 4 5 3 2 4 5
出力例3
2