У вас есть возможность создавать роботов с высотой из отрезка $[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