Cho dãy gồm \(N\) số nguyên \(A_1, A_2, \dots, A_N\) và một số nguyên dương \(D\).

Từ một vị trí \(i\) (1-indexed), khi thực hiện một "nhảy", bạn sẽ nhảy tới vị trí \(j > i\) nhỏ nhất sao cho đoạn con \(A[i..j-1]\) chứa đúng \(D\) phần tử phân biệt (distinct elements). Nếu không tồn tại vị trí \(j\) nào thỏa mãn (tức là từ vị trí \(i\) đến hết mảng có ít hơn \(D\) phần tử phân biệt), bước nhảy được coi là không hợp lệ và bạn sẽ dừng lại bên ngoài mảng.

Bạn cần xử lý \(Q\) truy vấn: Xuất phát từ vị trí \(U\), sau khi thực hiện đúng \(K\) bước nhảy liên tiếp, bạn đang ở vị trí nào? (Nếu nhảy ra ngoài mảng, in ra -1).

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

• Dòng đầu chứa ba số nguyên dương \(N\), \(Q\) và \(D\) (\(1 \le N, Q \le 10^5\), \(1 \le D \le N\)).
• Dòng hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(-10^9 \le A_i \le 10^9\)).
• \(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\)).

Định dạng đầu ra

• Với mỗi truy vấn, in ra vị trí đích (1-indexed) hoặc -1 nếu nhảy ra ngoài mảng.

Ràng buộc & Subtasks

• Subtask 1 (30% số điểm): \(N, Q \le 1000, K \le 1000\).
• Subtask 2 (70% số điểm): \(N, Q \le 10^5, K \le 10^9\).

Ví dụ

Input:

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

Output:

3
5
-1

Giải thích:

• \(D = 2\). Dãy: \([1, 2, 1, 3, 2, 4]\).
• Các bước nhảy từ các vị trí:
  • Từ 1 (giá trị 1): Cần 2 số phân biệt. Đoạn \([1, 2]\) có 2 số phân biệt \(\to\) nhảy tới 3.
  • Từ 2 (giá trị 2): Đoạn \([2, 1]\) có 2 số phân biệt \(\to\) nhảy tới 4.
  • Từ 3 (giá trị 1): Đoạn \([1, 3]\) có 2 số phân biệt \(\to\) nhảy tới 5.
  • Từ 4 (giá trị 3): Đoạn \([3, 2]\) có 2 số phân biệt \(\to\) nhảy tới 6.
  • Từ 5 (giá trị 2): Đoạn \([2, 4]\) có 2 số phân biệt \(\to\) nhảy tới 7 (ra ngoài mảng).
• Truy vấn 1 (\(U=1, K=1\)): \(1 \to 3\). Output: 3.
• Truy vấn 2 (\(U=1, K=2\)): \(1 \to 3 \to 5\). Output: 5.
• Truy vấn 3 (\(U=3, K=2\)): \(3 \to 5 \to 7\) (ra ngoài mảng). Output: -1.