У вас є можливість створювати роботів із висотою в межах $[0, d]$. Щоб протестувати їх, ви побудували смугу довжини $n$, яка містить деякі перешкоди. Опис перешкод задано масивом $a$. Якщо $a_i = 0$, то на $i$-й позиції перешкоди немає, а інакше там розташована перешкода висоти $a_i > 0$.

Щоб протестувати робота, ви обираєте відрізок $[l, r]$ і проводите його через усі перешкоди, що містяться на цьому відрізку. Коли робот зустрічає перешкоду зі значенням $a_i > 0$, відбувається одна з двох можливостей:

• Якщо поточна висота робота $h$ менша за $a_i$, то нічого не відбувається, оскільки робот занадто низький, щоб зачепити перешкоду.
• Якщо поточна висота робота $h$ не менша за $a_i$, то нова висота змінюється на $h' = h - a_i$.

Тепер вам потрібно відповісти на $q$ запитів. Для кожного з $q$ відрізків $[l_i, r_i]$ потрібно визначити максимально можливу кінцеву висоту, з якою робот може завершити рух після проходження перешкод на відрізку, якщо початкову висоту було обрано з інтервалу $[0, d]$.

Вхідні дані

Перший рядок містить цілі числа $n, q, d$ ($1 \le n, q \le 3 \cdot 10^5, 1 \le d \le 10^9$) — довжину масиву та кількість запитів.

Другий рядок містить $n$ цілих чисел $a_i$ ($0 \le a_i \le 10^9$) — опис масиву.

Наступні $q$ рядків містять пари цілих чисел $[l_i, r_i]$ ($1 \le l_i \le r_i \le n$) — опис запитів.

Вихідні дані

Виведіть $q$ цілих чисел — відповіді на запити.

Приклади

Вхідні дані 1

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

Вихідні дані 1

2
2
3

Вхідні дані 2

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

Вихідні дані 2

3
2
3
3
4