← 返回题目列表

AtCoder · abc030_d

D. 奇怪的字典

中文机器翻译题面 查看原题

問題文

三上君正在使用一本可疑的英语词汇书。那本词汇书里 包含 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