무한 모험

시간 제한2초메모리 제한1024 MB

요약

도시마다 주기가 2의 거듭제곱인 포털이 있을 때, 도시 v에서 t일에 출발해 포털을 Δ번 이용한 뒤 도착하는 도시를 구합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 수학
정답자: 아직 제출이 없습니다

문제

베시는 도시가 $N$ 개( $1\leq N\leq 10^5$ )인 땅에서 무한 모험을 계획하고 있다. 각 도시 $i$ 에는 포털과 순환 주기 $T_i$ 가 있다. 모든 $T_i$ 는 2의 거듭제곱이며, $T_1+\cdots+T_N\leq 10^5$ 이다. 날짜 $t$ 에 도시 $i$ 의 포털에 들어가면 도시 $c_{i,\, t \bmod T_i}$ 에서 즉시 나온다. 베시에게는 $Q$ 개( $1\leq Q\leq 5\cdot 10^4$ )의 여행 계획이 있고, 각 계획은 $(v, t, \Delta)$ 튜플로 이루어진다. 각 계획에서 베시는 $t$ 일에 도시 $v$ 에서 출발한 뒤, 현재 도시의 포털을 타고 하루를 기다리는 과정을 $\Delta$ 번 반복한다. 각 계획마다 베시가 최종적으로 도착하는 도시를 구하라.

입력

첫 줄에 노드 수 $N$ 과 질의 수 $Q$ 가 공백으로 구분되어 주어진다. 둘째 줄에는 $T_1, T_2, \ldots, T_N$ 이 공백으로 구분되어 주어진다( $1\leq T_i$ , $T_i$ 는 2의 거듭제곱, $T_1+\cdots+T_N\leq 10^5$ ). $i=1,2,\ldots,N$ 에 대해 $i+2$ 번째 줄에는 $c_{i,0}, \ldots, c_{i,T_i-1}$ 이 공백으로 구분되어 주어진다( $1\leq c_{i,t}\leq N$ ). $j=1,2,\ldots,Q$ 에 대해 $j+N+2$ 번째 줄에는 $j$ 번째 질의를 나타내는 양의 정수 $v_j, t_j, \Delta_j$ 가 공백으로 구분되어 주어진다( $1\leq v_j\leq N$ , $1\leq t_j\leq 10^{18}$ , $1\leq \Delta_j\leq 10^{18}$ ).

출력

$Q$ 줄을 출력한다. $j$ 번째 줄에는 $j$ 번째 질의의 답, 즉 베시가 최종적으로 도착하는 도시 번호를 출력한다.

예제2

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

입력

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

예상 출력