페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8149
서브태스크

Infinite Adventure 1s 1024MB

문제

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.


입력

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 jth query.


출력

Print Q lines. The jth line must contain the answer to the jth query.


부분문제

번호 점수 조건
#125점

Δ_j≤2⋅10^2

#225점

N,∑T_j≤2⋅10^3

#325점

N,∑T_j≤10^4

#425점

추가 제약 조건 없음


예제 #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
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.


예제 #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
2
3
5
4
2

출처

USACO 2024 February Platinum 3번

로그인해야 코드를 작성할 수 있어요.