## USACO 2024 February Contest, Platinum

## Problem 3. Infinite Adventure

Contest has ended.

**Log in to allow submissions in analysis mode**

****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