题目背景

光阴似箭。如烟火，只许刹那芳华；似九月，夜幕昙花一闪而散。 辉煌已逝。步征夫，辗转行路之洼；立孤叶，夙夜漂泊四海之旅。 ——《旅行》

题目描述

行走与尘世之间，charine 是一位旅行家。踏入城市的喧嚣，他开始了辗转于城市的旅行……

这是一个具有 $n$ 个城市的城市群，每两个点可以互相到达。现代交通技术飞速发展，大大缩短了航程，距离已显得不在那么重要：

城市群里，道路已经没有长长短短之说，每一条道路由于时间的不断缩短都可视为等长，把它们以一个单位计量，可以容易的视其为 $1$ zm。

正是由于城市群的庞大，未脱离于城市的 charine 亦有牵绊，这使他不可能无限遨游于这宽广的城市群里。这使 charine 极为郁闷，他决定选择尽可能短的时间走遍整个城市群。

具体而言，charine 不会因为在某个城市里而耽误他遨游天下的决心，他走访的每一个城市，都会在极短的时间里将其印在脑海里。

charine 的行走速度不会很快，这意味着他只能在一个单位时间内行走 $1$ zm。

这却使他更着急着找到足够旅行更多城市的方法……

为了去除他在每一个岔路口的犹豫时间，charine 亦是聪明的提前了他的旅行计划。对于走出城市 $i$ 的那几个路口，charine 给这个城市定义了一个通路 $a_i$，他相信自己的计划，就一定会踩着通路向前走。走访完城市 $i$ 的他会给自己的下一个城市目标定为 $a_i$。

处理完这些以后，他便是再也找不出继续缩短时间的办法了，于是他开始执行了自己的旅行计划。

charine 有 $m$ 个季度都有出行的机会，对于第 $i$ 个季度，charine 将会从 $S_i$ 出发，他告诉你，他会准备 $t$ 单位时间去旅行。

为了能及时的看到他的身影，你要知道，$t$ 单位时间后 charine 会出现在哪个城市……

注意“道路”与“通路”的定义问题。

输入格式

输入数据的第一行为一个正整数 $n$，表示城市数。

第二行 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

接下来一个整数 $m$，表示 $m$ 个季度。

第 $4$ 到 $m+3$ 行，描述一次旅行，每行 $3$ 个整数，$S_i,t_1,t_2$，描述见题面，其中，$t=t_1^{t_2}$。

输出格式

对于每个季度输出一行，表示答案。

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

5
3
1

提示

样例解析：

从 $1$ 开始走 $2^{2}$ 步到达 $5$（$1-2-3-4-5$）

从 $2$ 开始走 $7^{1}$ 步到达 $3$（$2-3-4-5-6-1-2-3$）

从 $6$ 开始走 $1^{1}$ 步到达 $1$（$6-1$）

对于 $10\%$ 的数据，$n\leq 100$，$m\leq 300$，$t_1\leq 100$。

对于 $50\%$ 的数据，$n\leq 3000$，$m\leq 3000$，$t_1\leq 3000$，$t_2=1$。

对于 $70\%$ 的数据，$n\leq 3000$，$m\leq 3000$。

对于 $100\%$ 的数据，$n\leq 400000$，$m\leq 300000$，$t_1\leq 10^{9}$，$t_2\leq 10^9$。