You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-1750 题。

题目描述

你正在玩一个由 $n$ 个行星组成的游戏。每个行星都有一个传送门，可以传送到另一个行星（或者是它自己）。

你的任务是处理 $q$ 个查询，查询的形式是：当你从行星 $x$ 出发，经过 $k$ 次传送后，你将到达哪个行星？

输入格式

第一行包含两个整数 $n$ 和 $q$：分别表示行星的数量和查询的数量。行星编号为 $1,2,…,n$。

第二行包含 $n$ 个整数 $t_1,t_2,…,t_n$：表示每个行星的传送门目的地。如果 $t_i = i$，则表示该行星的传送门指向自己。

接下来的 $q$ 行，每行包含两个整数 $x$ 和 $k$：表示你从行星 $x$ 出发，经过 $k$ 次传送后，最终会到达哪个行星。

输出格式

对每个查询，输出经过 $k$ 次传送后你将到达的行星编号。

样例

4 3
2 1 1 4
1 2
3 4
4 1

1
2
4

说明/提示

$1 \leq n,q \leq 2 \cdot 10^5$；

$1 \leq t_i \leq n$；

$1 \leq x \leq n$；

$0 \le k \le 10^9$。