Problem Background

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

Problem Description

Bessie is planning an endless adventure across a continent with $N$ ($1 \le N \le 10^5$) cities. Each city $i$ has a portal with a cycle period $T_i$. All $T_i$ are powers of 2, and $T_1 + \cdots + T_N \le 10^5$. If you enter the portal of city $i$ on day $t$, you will immediately exit from the portal of city $c_{i, t \mod T_i}$.

Bessie has $Q$ ($1 \le Q \le 5 \cdot 10^4$) plans for her travels, each consisting of a tuple $(v, t, \Delta)$. In each plan, she starts from city $v$ on day $t$. Then, she will perform the following operation $\Delta$ times: she will enter the portal of the current city and then wait for one day. For each of her plans, she wants to know which city she will end up in.

Input Format

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

The second line contains $N$ space-separated integers: $T_1, T_2, \ldots, T_N$ ($1 \le T_i$, $T_i$ is a power of 2, and $T_1 + \cdots + T_N \le 10^5$).

For $i = 1, 2, \ldots, N$, the $(i+2)$-th line contains $T_i$ space-separated positive integers, which are $c_{i,0}, \ldots, c_{i,T_{i-1}}$ ($1 \le c_{i,t} \le N$).

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

Output Format

Output $Q$ lines. The $j$-th line contains the answer to the $j$-th query.

Sample Input and Output

Input Sample #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

Output Sample #1

2
2
5
4

Input Sample #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

Output Sample #2

2
3
5
4
2

Notes/Hints

Sample Explanation 1

Bessie's first three adventures will proceed as follows:

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

Test Case Properties

• Test case $3$: $\Delta_j \le 2 \cdot 10^2$.
• Test cases $4-5$: $N, \sum T_j \le 2 \cdot 10^3$.
• Test cases $6-8$: $N, \sum T_j \le 10^4$.
• Test cases $9-18$: No additional restrictions.

见题面 Input 部分

见题面 Output 部分