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