Lần xuất hiện thứ k

Cho mảng \(A\) gồm \(n\) phần tử. Cho \(q\) truy vấn dạng \(x, k\), hãy tìm chỉ số của phần tử mang giá trị \(x\) xuất hiện lần thứ \(k\) (tính từ chỉ số \(1\) trở đi, đếm các lần xuất hiện của \(x\) theo thứ tự chỉ số tăng dần).

Input

• Dòng đầu tiên gồm hai số nguyên \(n, q\) (\(1 \le n, q \le 10^5\)).

• Dòng thứ hai gồm \(n\) số nguyên \(A_1, A_2, \ldots, A_n\) (\(1 \le A_i \le 10^9\)).

• \(q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(x, k\) (\(1 \le x, k \le 10^9\)) thể hiện một truy vấn.

Các truy vấn đảm bảo luôn tồn tại đáp án.

Output

Với mỗi truy vấn, in ra trên một dòng một số nguyên là chỉ số cần tìm.

Example

Input:

8 5
1 1 3 4 2 1 4 2
1 3
1 2
1 1
4 2
2 1

Output:

6
2
1
7
5

Note

Trong ví dụ trên, giá trị \(1\) xuất hiện tại các chỉ số \(1, 2, 6\); giá trị \(4\) xuất hiện tại các chỉ số \(4, 7\); giá trị \(2\) xuất hiện tại các chỉ số \(5, 8\). Truy vấn \((x, k) = (1, 3)\) ứng với lần xuất hiện thứ ba của giá trị \(1\), tức là chỉ số \(6\).