Cho một đồ thị hàm số (functional graph) gồm \(N\) đỉnh được đánh số từ \(0\) đến \(N-1\). Mỗi đỉnh \(i\) có đúng một cung đi ra hướng tới đỉnh \(next[i]\) (cho phép tự nối hoặc tạo chu kỳ).

Bạn cần xử lý \(Q\) truy vấn: Xuất phát từ đỉnh \(U\), nếu đi theo các cung liên tiếp đúng \(K\) bước, ta sẽ dừng lại ở đỉnh nào?

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên đại diện cho mảng \(next\) (\(0 \le next[i] < N\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(U\) và \(K\) (\(0 \le U < N\), \(0 \le K \le 10^{18}\)).

Định dạng đầu ra

• Với mỗi truy vấn, in ra đỉnh dừng lại trên một dòng riêng biệt.

Ràng buộc & Subtasks

• Subtask 1 (30% số điểm): \(N, Q \le 1000, K \le 1000\).
• Subtask 2 (30% số điểm): \(K \le 10^9\).
• Subtask 3 (40% số điểm): \(N, Q \le 10^5, K \le 10^{18}\), các ràng buộc gốc.

Ví dụ

Input:

5 3
2 0 1 3 4
0 3
1 4
3 10

Output:

0
1
3

Giải thích:

• Truy vấn 1: \(0 \to 2 \to 1 \to 0\) (sau 3 bước dừng tại 0).
• Truy vấn 2: \(1 \to 0 \to 2 \to 1 \to 0 \to 2 \dots\) (sau 4 bước dừng tại 0? Để xem: \(1 \to 0 \to 2 \to 1 \to 0\) (4 bước \(\to\) dừng tại 0? À, 1 bước là 0, 2 bước là 2, 3 bước là 1, 4 bước là 0? Chờ chút: \(next[1]=0, next[0]=2, next[2]=1 \to\) hành trình là \(1 \to 0 \to 2 \to 1 \to 0 \to 2 \to \dots\)). Wait, let's count:
• 0 bước: 1
• 1 bước: 0
• 2 bước: 2
• 3 bước: 1
• 4 bước: 0. Đúng vậy! Dừng tại 0.
• Truy vấn 3: \(3 \to 3 \to \dots \to 3\) (sau 10 bước dừng tại 3).