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

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 tổng các phần tử từ vị trí \(i\) đến trước vị trí \(j\) (tức là \(A_i + A_{i+1} + \dots + A_{j-1}\)) có giá trị ít nhất là \(S\). Nếu không có vị trí \(j\) nào thỏa mãn, 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 đứng ở 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à \(S\) (\(1 \le N, Q \le 10^5\), \(1 \le S \le 10^9\)).
• Dòng hai chứa \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) (\(1 \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 (30% số điểm): \(S \le 100\).
• Subtask 3 (40% số điểm): \(N, Q \le 10^5, K \le 10^9\), các ràng buộc gốc.

Ví dụ

Input:

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

Output:

4
-1
-1

Giải thích:

• \(S = 6\). Mảng: \([2, 3, 1, 4, 5]\).
• Các bước nhảy từ từng vị trí:
  • Từ 1 (giá trị 2): Cần tổng \(\ge 6\). Ta có \(2 + 3 + 1 = 6 \to\) nhảy tới 4 (giá trị 4).
  • Từ 2 (giá trị 3): Cần tổng \(\ge 6\). Ta có \(3 + 1 + 4 = 8 \ge 6 \to\) nhảy tới 5 (giá trị 5).
  • Từ 3 (giá trị 1): Cần tổng \(\ge 6\). Ta có \(1 + 4 + 5 = 10 \ge 6 \to\) nhảy ra ngoài mảng (dừng ở 6).
• Truy vấn 1: Xuất phát từ 1, sau 1 bước nhảy \(\to\) tới 4.
• Truy vấn 2: Xuất phát từ 1, sau 2 bước nhảy: \(1 \to 4 \to 6\) (ra ngoài mảng) \(\to\) -1.
• Truy vấn 3: Xuất phát từ 3, sau 2 bước nhảy: \(3 \to 6\) (bước thứ nhất đã ra ngoài mảng) \(\to\) -1.