Cho dãy ~A~ gồm ~N~ phần tử. Cho ~Q~ truy vấn dạng ~(u~, ~v)~ tìm ~e~ nhỏ nhất sao cho từ ~e~ tới ~u~ có thể chia thành ~x~ ~(x \le v)~ đoạn liên tiếp sao cho mỗi đoạn có tổng ~\le M~.

Input

Dòng đầu chứa ~N~, ~Q~, ~M~ ~(M \le 10^{9})~

Dòng thứ ~2~ chứa ~N~ số biểu diễn dãy ~A~. ~(0 \le~ Ai ~\le M)~

~Q~ dòng sau, dòng thứ ~i~ chứa ~2~ số ~u~, ~v~ mô tả truy vấn thứ ~i~. ~(0 < u \le N~, ~0 < v \le 10^{9})~

Output

Gồm ~Q~ dòng

Dòng thứ ~i~ chứa kết quả của truy vấn thứ ~i~

Giới hạn

Subtask ~1~: ~(21~ tests) ~N~, ~Q \le 2000~

Subtask ~2~: ~(10~ tests) ~N~, ~Q \le 100000~.

Sample Input

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

Sample Output

1
3