Description

贝西计划在一个拥有 $N\left(1 \leq N \leq 10^5\right)$ 个城市的土地上展开一场无限冒险。

在每个城市 $i$ ，都有一个传送门和一个循环时间 $T_i$ 。所有的 $T_i$ 都是 2 的幕，且 $T_1+\cdots+T_N \leq 10^5$ 。如果你在第 $t$ 天进入城市 $i$ 的传送门，那么你会立刻在第 $c_{i, t} \bmod T_i$ 个城市的传送门中出来。

贝西有 $Q\left(1 \leq Q \leq 5 \cdot 10^4\right)$ 个旅行计划，每个计划都由一个元组 $(v, t, \Delta)$ 组成。在每个计划中，她会在第 $t$ 天从城市 $v$ 开始。然后她会进行 $\Delta$ 次以下操作：她会跟随当前城市的传送门，然后等待一天。对于她的每个计划，她想知道她最终会到达哪个城市。

Format

Input

第一行包含两个用空格分隔的整数： $N$ ，节点数，和 $Q$ ，查询数。

第二行包含 $N$ 个用空格分隔的整数: $T_1, T_2, \ldots, T_N\left(1 \leq T_i, T_i\right.$ 是 2 的幕，且 $\left.T_1+\cdots+T_N \leq 10^5\right)$ 。对于 $i=1,2, \ldots, N$ ，第 $i+2$ 行包含 $T_i$ 个用空格分隔的正整数，即 $c_{i, 0}, \ldots, c_{i, T_i-1}\left(1 \leq c_{i, t} \leq N\right)$ 。对于 $j=1,2, \ldots, Q$ ，第 $j+N+2$ 行包含三个用空格分隔的正整数， $v_j, t_j, \Delta_j\left(1 \leq v_j \leq N, 1 \leq t_j \leq 10^{18}\right.$ ，和 $\left.1 \leq \Delta_j \leq 10^{18}\right)$ 代表第 $j$ 个查询。

Output

打印 $Q$ 行。第 $j$ 行必须包含第 $j$ 个查询的答案。

Samples

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

2
2
5
4

贝西的前三次冒险经历如下：

在第一次冒险中，她在时间 4 从城市 2 出发，到时间 5 到达城市 3，到时间 6 到达城市 4，到时间 7 回到城市 2。

在第二次冒险中，她在时间 3 从城市 3 出发，到时间 4 到达城市 4，到时间 5 到达城市 2，到时间 6 到达城市 4，到时间 7 回到城市 2，到时间 8 再次到达城市 4，到时间 9 回到城市 2。

在第三次冒险中，她在时间 3 从城市 5 出发，到时间 4 仍然在城市 5，到时间 5 仍然在城市 5。

5 5
1 2 1 2 8
2
3 4
4
2 3
5 5 5 5 5 1 5 5
2 4 3
3 2 6
5 3 2
5 3 7
5 3 1000000000000000000

2
3
5
4
2

Limitation

• Input 3: $\Delta_j \leq 2 \cdot 10^2$.
• Inputs 4-5: $N, \sum T_j \leq 2 \cdot 10^3$.
• Inputs 6-8: $N, \sum T_j \leq 10^4$.
• Inputs 9-18: No additional constraints.