Infinite Adventure

Bessie is planning an infinite adventure in a land with $N$ ($1\leq N\leq 10^5$) cities. Each city $i$ has a portal and a cycling time $T_i$. Every $T_i$ is a power of $2$, and $T_1+\cdots+T_N\leq 10^5$. If you enter city $i$'s portal on day $t$, you instantly exit in city $c_{i,\, t \bmod T_i}$. Bessie has $Q$ ($1\leq Q\leq 5\cdot 10^4$) plans, each a tuple $(v, t, \Delta)$. In each plan she starts in city $v$ on day $t$, then repeats the following $\Delta$ times: she follows the portal in her current city, then waits one day. For each plan, find the city where she ends up.

The first line contains two integers $N$ and $Q$, separated by a space. The second line contains $T_1, T_2, \ldots, T_N$, separated by spaces ($1\leq T_i$, each $T_i$ is a power of $2$, and $T_1+\cdots+T_N\leq 10^5$). For $i=1,2,\ldots,N$, line $i+2$ contains $c_{i,0}, \ldots, c_{i,T_i-1}$, separated by spaces ($1\leq c_{i,t}\leq N$). For $j=1,2,\ldots,Q$, line $j+N+2$ contains three positive integers $v_j, t_j, \Delta_j$ separated by spaces ($1\leq v_j\leq N$, $1\leq t_j\leq 10^{18}$, $1\leq \Delta_j\leq 10^{18}$).

Print $Q$ lines. The $j$th line is the answer to the $j$th plan, the city where Bessie ends up.