5256 : A57 - 더블링
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$ 개의 구멍이 있는 모래 사장에 개미 한 마리가 살고 있습니다. 이 개미는 규칙적으로 움직이는 것으로 알려져 있으며, 구멍 $i \ (1 \leq i \leq N) $ 에 들어간 다음 날에는 구멍 $A_i$ 로 이동합니다.
다음 $Q$ 개의 쿼리를 처리하세요.
[제약 조건]
• 입력되는 모든 값은 정수입니다.입니다.
• $1 \le N \le 100000$
• $1 \le Q \le 100000$
• $1 \le A_i \le N$
• $1 \le X_j \le N$
• $1 \le Y_j \le 10^9$
다음 $Q$ 개의 쿼리를 처리하세요.
- $j$ 번째 쿼리: 현재 구멍 $X_j$ 에 있을 때, $Y_j$ 일 후에는 어느 구멍에 있겠는가?
[제약 조건]
• 입력되는 모든 값은 정수입니다.입니다.
• $1 \le N \le 100000$
• $1 \le Q \le 100000$
• $1 \le A_i \le N$
• $1 \le X_j \le N$
• $1 \le Y_j \le 10^9$
입력 설명
첫째 줄에 $N, Q$ 가 주어집니다.
둘째 줄에 $A_1, A_2, \ldots, A_N$ 이 주어집니다.
셋째 줄부터 $Q$ 개의 줄에 걸쳐 $X_j, Y_j$ 가 주어집니다.
둘째 줄에 $A_1, A_2, \ldots, A_N$ 이 주어집니다.
셋째 줄부터 $Q$ 개의 줄에 걸쳐 $X_j, Y_j$ 가 주어집니다.
출력 설명
각 쿼리에 대한 결과를 출력하세요.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
7 4
2 4 1 7 6 5 3
1 1
1 5
2 13
5 999999999
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2
1
3
6