Divine Array

Description:

Input:

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). Description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 2000$$$) — the size of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the initial values of array $$$a$$$.

The third line of each test case contains a single integer $$$q$$$ ($$$1 \le q \le 100\,000$$$) — the number of queries.

Next $$$q$$$ lines contain the information about queries — one query per line. The $$$i$$$-th line contains two integers $$$x_i$$$ and $$$k_i$$$ ($$$1 \le x_i \le n$$$; $$$0 \le k_i \le 10^9$$$), meaning that Black is asking for the value of $$$a_{x_i}$$$ after the $$$k_i$$$-th step of transformation. $$$k_i = 0$$$ means that Black is interested in values of the initial array.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2000$$$ and the sum of $$$q$$$ over all test cases doesn't exceed $$$100\,000$$$.

Output:

For each test case, print $$$q$$$ answers. The $$$i$$$-th of them should be the value of $$$a_{x_i}$$$ after the $$$k_i$$$-th step of transformation. It can be shown that the answer to each query is unique.

Sample Input:

2
7
2 1 1 4 3 1 2
4
3 0
1 1
2 2
6 1
2
1 1
2
1 0
2 1000000000

Sample Output:

1
2
3
3
1
2

Note:

The first test case was described ih the statement. It can be seen that:

1. $$$k_1 = 0$$$ (initial array): $$$a_3 = 1$$$;
2. $$$k_2 = 1$$$ (after the $$$1$$$-st step): $$$a_1 = 2$$$;
3. $$$k_3 = 2$$$ (after the $$$2$$$-nd step): $$$a_2 = 3$$$;
4. $$$k_4 = 1$$$ (after the $$$1$$$-st step): $$$a_6 = 3$$$.

For the second test case,

Initial array:	$$$1$$$ $$$1$$$
After the $$$1$$$-st step:	$$$2$$$ $$$2$$$
After the $$$2$$$-nd step:	$$$2$$$ $$$2$$$
...	...

It can be seen that:

1. $$$k_1 = 0$$$ (initial array): $$$a_1 = 1$$$;
2. $$$k_2 = 1000000000$$$: $$$a_2 = 2$$$;