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.

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).

Ràng buộc & Subtasks

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