Bạn có khả năng tạo ra các robot có chiều cao nằm trong đoạn $[0, d]$. Để thử nghiệm chúng, bạn đã xây dựng một đường thẳng có độ dài $n$ chứa một số chướng ngại vật. Mô tả về các chướng ngại vật được cho dưới dạng một mảng $a$. Nếu $a_i = 0$ thì không có chướng ngại vật nào tại vị trí thứ $i$, ngược lại có một chướng ngại vật có chiều cao $a_i > 0$.

Để thử nghiệm robot của mình, bạn chọn một đoạn $[l, r]$ và cho nó đi qua tất cả các chướng ngại vật nằm trong đoạn đó. Khi robot gặp một chướng ngại vật có giá trị $a_i > 0$, một trong hai khả năng sau sẽ xảy ra:

• Nếu chiều cao hiện tại của robot $h$ nhỏ hơn $a_i$, thì không có gì xảy ra vì robot quá thấp để chạm tới chướng ngại vật.
• Nếu chiều cao hiện tại của robot $h$ lớn hơn hoặc bằng $a_i$, thì chiều cao mới sẽ thay đổi thành $h' = h - a_i$.

Bây giờ bạn cần trả lời $q$ truy vấn. Với mỗi đoạn trong $q$ đoạn $[l_i, r_i]$, bạn cần cho biết chiều cao lớn nhất có thể mà robot đạt được sau khi đi qua các chướng ngại vật trong đoạn nếu chiều cao ban đầu được chọn từ khoảng $[0, d]$.

Dữ liệu vào

Dòng đầu tiên chứa bộ số nguyên $n, q, d$ ($1 \le n, q \le 3 \cdot 10^5, 1 \le d \le 10^9$) — độ dài của mảng và số lượng truy vấn.

Dòng thứ hai chứa $n$ số nguyên $a_i$ ($0 \le a_i \le 10^9$) — mô tả của mảng.

$q$ dòng tiếp theo chứa cặp số nguyên $[l_i, r_i]$ ($1 \le l_i \le r_i \le n$) — mô tả các truy vấn.

Dữ liệu ra

In ra $q$ số nguyên — câu trả lời cho các truy vấn.

Ví dụ

Dữ liệu vào 1

5 3 5
0 2 6 1 3
5 5
1 5
1 3

Dữ liệu ra 1

2
2
3

Dữ liệu vào 2

7 5 10
7 6 2 5 0 1 4
1 3
1 7
4 7
2 5
4 6

Dữ liệu ra 2

3
2
3
3
4