Giải bài trực tuyến

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 <= v) đoạn liên tiếp sao cho mỗi đoạn có tổng <= M.

Input

Dòng đầu chứa N, Q, M (M <= 10^9 )

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

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

Output

Gồm Q dòng

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

Example

Input:
5 2 8

1 2 3 4 5

4 2

5 2

Output:
1

3

Subtask 1: (21 tests)

  N, Q <= 2000

Subtask 2: (10 tests)

  N, Q <= 100000.