题目描述

给你一个长度为 $n$ 的排列 $p_1, p_2, \ldots, p_n$。

在本题中，对于一个整数 $a$ 来说，它经过一次变化后将会变为 $p_a$。

接下来有 $q$ 次询问。

每次询问给你两个整数 $x(1 \le x \le n)$ 和 $k(1 \le k \le 10^9)$，你需要回答出 $x$ 经过恰好 $k$ 次变化后将会变成的数字。

输入格式

第一行，一个整数 $n(1 \le n \le 2 \times 10^5)$。

第二行，$n$ 个整数 $p_1, p_2, \ldots, p_n$，两两之间以一个空格分隔。数据保证这是一个由整数 $1 \sim n$ 构成的排列。

第三行，一个整数 $q(1 \le q \le 2 \times 10^5)$，表示询问次数。

接下来 $q$ 行，每行包含两个整数 $x$ 和 $k$，以一个空格分隔，表示一次询问（$1 \le x \le n, 1 \le k \le 10^9$）。

输出格式

对于每次询问的 $x$ 和 $k$，输出一行，包含一个整数，表示整数 $x$ 经过恰好 $k$ 次变化后变成的数字。

样例

6
2 4 3 1 6 5
5
1 1
2 2
4 3
3 1000000000
5 7

2
1
4
3
6

说明/提示

样例解释

1. $1 \rightarrow 2$
2. $2 \rightarrow 4 \rightarrow 1$
3. $4 \rightarrow 1 \rightarrow 2 \rightarrow 4$
4. 因为 $p_3 = 3$，所以 $3$ 经过多少次变化都是 $3$
5. $5 \rightarrow 6 \rightarrow 5 \rightarrow 6 \rightarrow 5 \rightarrow 6 \rightarrow 5 \rightarrow 6$

数据规模与约定

• 对于 $20\%$ 的数据，$n, q \le 20; k \le 1000$
• 对于 $50\%$ 的数据，$n, q \le 2000; k \le 10^6$
• 对于 $100\%$ 的数据，$1 \le n, q \le 2 \times 10^5; 1 \le k \le 10^9$