Infinite Adventure

문제

Bessie is planning an infinite adventure in a land with $NN$ ($1\le N\le {10}^{5}1\backslash leq\; N\; \backslash leq\; 10^5$) cities. In each city $ii$, there is a portal, as well as a cycling time $T_{i}T\_i$. All $T_{i}T\_i$'s are powers of $22$, and $T_1+\cdots +T_N\le {10}^{5}T\_1\; +\; \backslash cdots\; +\; T\_N\; \backslash leq\; 10^5$. If you enter city $ii$'s portal on day $tt$, then you instantly exit the portal in city $c_{i,t{T}_i}c\_\{i,\; t\backslash bmod\{T\_i\}\}$.

Bessie has $QQ$ ($1\le Q\le 5\cdot {10}^{4}1\backslash leq\; Q\; \backslash leq\; 5\backslash cdot\; 10^4$) plans for her trip, each of which consists of a tuple $(v,t,\mathrm{\Delta })(v,\; t,\; \backslash Delta)$. In each plan, she will start in city $vv$ on day $tt$. She will then do the following $\mathrm{\Delta }\backslash Delta$ times: She will follow the portal in her current city, then wait one day. For each of her plans, she wants to know what city she will end up in.

입력

The first line contains two space-separated integers: $NN$, the number of nodes, and $QQ$, the number of queries.

The second line contains $NN$ space-separated integers: $T_1,T_2,\dots ,T_{N}T\_1,\; T\_2,\; \backslash ldots,\; T\_N$ ($1\le T_{i}1\backslash leq\; T\_i$, $T_{i}T\_i$ is a power of $22$, and $T_1+\cdots +T_N\le {10}^{5}T\_1\; +\; \backslash cdots\; +\; T\_N\; \backslash leq\; 10^5$).

For $i=1,2,\dots ,Ni\; =\; 1,\; 2,\; \backslash ldots,\; N$, line $i+2i+2$ contains $T_{i}T\_i$ space-separated positive integers, namely $c_{i,0},\dots ,c_{i,T_i-1}c\_\{i,\; 0\},\; \backslash ldots,\; c\_\{i,\; T\_i-1\}$ ($1\le c_{i,t}\le N1\backslash leq\; c\_\{i,\; t\}\; \backslash leq\; N$).

For $j=1,2,\dots ,Qj\; =\; 1,\; 2,\; \backslash ldots,\; Q$, line $j+N+2j+N+2$ contains three space-separated positive integers, $v_j,t_j,{\mathrm{\Delta }}_{j}v\_j,\; t\_j,\; \backslash Delta\_j$ ($1\le v_j\le N1\backslash leq\; v\_j\; \backslash leq\; N$, $1\le t_j\le {10}^{18}1\backslash leq\; t\_j\; \backslash leq\; 10^\{18\}$, and $1\le {\mathrm{\Delta }}_j\le {10}^{18}1\backslash leq\; \backslash Delta\_j\; \backslash leq\; 10^\{18\}$) representing the $jj$th query.

출력

Print $QQ$ lines. The $jj$th line must contain the answer to the $jj$th query.

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

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