Island Journey

Bạn đang thực hiện một chuyến hành trình khám phá các khu vực liên tiếp trên một hòn đảo. Hòn đảo có \(n\) khu vực, được đánh số từ \(1\) đến \(n\). Mỗi khu vực \(i\) chứa lượng tài nguyên là \(A_i\).

Bạn nhận được \(q\) yêu cầu, mỗi yêu cầu cho biết:

• Một khu vực đích \(u\) bạn cần đến.
• Một số nguyên \(v\) --- số lượng chặng dừng tối đa bạn được phép chia.

Bạn cần xác định khu vực khởi hành \(e\) nhỏ nhất sao cho:

• Hành trình từ \(e\) đến \(u\) (liên tiếp, \(e \leq u\)) có thể được chia thành không quá \(v\) chặng.
• Tổng tài nguyên trong mỗi chặng không vượt quá \(M\).
• Dữ liệu đảm bảo luôn có giá trị \(e\) thỏa mãn.

Input

• Dòng đầu tiên gồm ba số nguyên \(n\), \(q\), và \(M\) \((1 \leq n, q \leq 10^5, 1 \leq M \leq 10^9)\).
• Dòng thứ hai chứa \(n\) số nguyên \(A_1, A_2, \ldots, A_n\) \((0 \leq A_i \leq M)\).
• Tiếp theo là \(q\) dòng, mỗi dòng gồm hai số nguyên \(u_i\) và \(v_i\) \((1 \leq u_i \leq n, 1 \leq v_i \leq 10^9)\).

Output

• Với mỗi truy vấn, in ra một số nguyên duy nhất trên một dòng --- khu vực bắt đầu \(e\) nhỏ nhất thỏa mãn điều kiện.

Example

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

1
3

Scoring

• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(1 \leq n, q \leq 100\).
• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(1 \leq n, q \leq 1000\).
• \(40\%\) số test tương ứng với \(40\%\) số điểm còn lại không có ràng buộc gì thêm.