## USACO 2024 February Contest, Platinum

Contest has ended.

**Note: The memory limit for this problem is 512MB, twice the default.**

Bessie is planning an infinite adventure in a land with $N$ ($1\leq N \leq 10^5$) cities. In each city $i$, there is a portal, as well as a cycling time $T_i$. All $T_i$'s are powers of $2$, and $T_1 + \cdots + T_N \leq 10^5$. If you enter city $i$'s portal on day $t$, then you instantly exit the portal in city $c_{i, t\bmod{T_i}}$.

Bessie has $Q$ ($1\leq Q \leq 5\cdot 10^4$) plans for her trip, each of which consists of a tuple $(v, t, \Delta)$. In each plan, she will start in city $v$ on day $t$. She will then do the following $\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.

#### INPUT FORMAT (input arrives from the terminal / stdin):

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

The second line contains $N$ space-separated integers: $T_1, T_2, \ldots, T_N$ ($1\leq T_i$, $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 $T_i$ space-separated positive integers, namely $c_{i, 0}, \ldots, c_{i, T_i-1}$ ($1\leq c_{i, t} \leq N$).

For $j = 1, 2, \ldots, Q$, line $j+N+2$ contains three space-separated positive integers, $v_j, t_j, \Delta_j$ ($1\leq v_j \leq N$, $1\leq t_j \leq 10^{18}$, and $1\leq \Delta_j \leq 10^{18}$) representing the $j$th query.

#### OUTPUT FORMAT (print output to the terminal / stdout):

Print $Q$ lines. The $j$th line must contain the answer to the $j$th query.

#### SAMPLE INPUT:

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


#### SAMPLE OUTPUT:

2
2
5
4


Bessie's first three adventures proceed as follows:

• In the first adventure, she goes from city $2$ at time $4$ to city $3$ at time $5$, to city $4$ at time $6$, to city $2$ at time $7$.
• In the second adventure, she goes from city $3$ at time $3$ to city $4$ at time $4$, to city $2$ at time $5$, to city $4$ at time $6$, to city $2$ at time $7$, to city $4$ at time $8$, to city $2$ at time $9$.
• In the third adventure, she goes from city $5$ at time $3$ to city $5$ at time $4$, to city $5$ at time $5$.

#### SAMPLE INPUT:

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


#### SAMPLE OUTPUT:

2
3
5
4
2


#### SCORING:

• 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.

Problem credits: Brandon Wang

Contest has ended. No further submissions allowed.