Có \(N\) hành tinh, mỗi hành tinh i chỉ có duy nhất một tuyến bay một chiều nối đến hành tinh t_i. Cho Q truy vấn, với mỗi truy vấn hãy tìm hành tinh dừng chân sau khi đi đúng K chuyến bay liên tiếp xuất phát từ hành tinh \(u\).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và Q (\(2 \le N, Q \le 200000\)).
• Dòng thứ hai chứa \(N\) số nguyên \(t_1, t_2 \dots t_N\) (\(1 \le t_i \le N\)) thể hiện hành tinh đích một chiều từ hành tinh \(i\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên u và K (\(1 \le u \le N, 1 \le K \le 10^9\)) mô tả truy vấn.

Kết quả ra

• Với mỗi truy vấn, in ra chỉ số của hành tinh kết quả trên một dòng mới.

Ví dụ

Input

4 3
2 3 4 1
1 1
1 2
1 4

Output

2
3
1

Ràng buộc & Subtasks