Description

Walking through the mortal world, charine is a traveler. Stepping into the noise of cities, he begins his journey from city to city.

There is a group of cities with $n$ cities, and any two cities are reachable from each other. With the rapid development of modern transportation, travel time has been greatly reduced, so distance no longer seems that important:

In this city group, roads no longer have different lengths. Because travel time keeps shrinking, every road can be regarded as having the same length, measured as one unit, which can be seen as $1$ zm.

However, because the city group is huge and charine still has things tying him down, he cannot travel forever in this vast city group. This makes him very upset, so he decides to spend as little time as possible to visit the entire city group.

Specifically, charine will not waste time staying in any city. Every city he visits will be remembered in a very short time.

charine does not walk fast, which means he can only walk $1$ zm in one unit of time.

This makes him even more eager to find a way to travel to more cities.

To remove the hesitation time at every intersection, charine wisely planned his trip in advance. For the exits leaving city $i$, charine defines a “passage” $a_i$ for this city. He trusts his plan and will definitely follow the passage forward. After visiting city $i$, he will set his next target city to be $a_i$.

After finishing these preparations, he can no longer find any way to further shorten the time, so he starts executing his travel plan.

charine has $m$ seasons when he has a chance to travel. For the $i$-th season, charine will start from $S_i$. He tells you that he will prepare $t$ units of time for traveling.

To see him in time, you need to know: after $t$ units of time, which city will charine appear in?

Note the difference between the definitions of “road” and “passage”.

Input Format

The first line contains a positive integer $n$, the number of cities.

The second line contains $n$ integers. The $i$-th integer is $a_i$.

Next is an integer $m$, indicating $m$ seasons.

Lines $4$ to $m+3$ each describe one trip. Each line contains three integers $S_i, t_1, t_2$ as described above, where $t=t_1^{t_2}$.

Output Format

For each season, output one line containing the answer.

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

5
3
1

Hint

Sample explanation:

Start from $1$ and walk $2^{2}$ steps to reach $5$ ($1-2-3-4-5$).

Start from $2$ and walk $7^{1}$ steps to reach $3$ ($2-3-4-5-6-1-2-3$).

Start from $6$ and walk $1^{1}$ step to reach $1$ ($6-1$).

For $10\%$ of the testdata, $n\leq 100$, $m\leq 300$, $t_1\leq 100$.

For $50\%$ of the testdata, $n\leq 3000$, $m\leq 3000$, $t_1\leq 3000$, $t_2=1$.

For $70\%$ of the testdata, $n\leq 3000$, $m\leq 3000$.

For $100\%$ of the testdata, $n\leq 400000$, $m\leq 300000$, $t_1\leq 10^{9}$, $t_2\leq 10^9$.

Translated by ChatGPT 5