Infinite Adventure | Code Joint

**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 1 0^{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} + \dots + T_{N} \leq 1 0^{5}$ . If you enter city $i$ 's portal on day $t$ , then you instantly exit the portal in city $c_{i, t mod T_{i}}$ .

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

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

SCORING:

Input 3: $Δ_{j} \leq 2 \cdot 1 0^{2}$ .
Inputs 4-5: $N, \sum T_{j} \leq 2 \cdot 1 0^{3}$ .
Inputs 6-8: $N, \sum T_{j} \leq 1 0^{4}$ .
Inputs 9-18: No additional constraints.

Problem credits: Brandon Wang

Source: USA Computing Olympiad.

Input Format

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}, \dots, T_{N}$ ( $1 \leq T_{i}$ , $T_{i}$ is a power of $2$ , and $T_{1} + \dots + T_{N} \leq 1 0^{5}$ ).

For $i = 1, 2, \dots, N$ , line $i + 2$ contains $T_{i}$ space-separated positive integers, namely $c_{i, 0}, \dots, c_{i, T_{i} - 1}$ ( $1 \leq c_{i, t} \leq N$ ).

For $j = 1, 2, \dots, Q$ , line $j + N + 2$ contains three space-separated positive integers, $v_{j}, t_{j}, Δ_{j}$ ( $1 \leq v_{j} \leq N$ , $1 \leq t_{j} \leq 1 0^{18}$ , and $1 \leq Δ_{j} \leq 1 0^{18}$ ) representing the $j$ th query.

Output Format

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

Sample Input 1

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 1

2 2 5 4

Sample Input 2

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

2 3 5 4 2

Submit

Language