Bitaro купил на перекус длинную шпажку с клёцками. Эту шпажку можно описать $N$ положительными целыми числами $A_1,A_2,\ldots,A_N$ следующим образом. Для каждого целого $i$, такого что $0\le i\le N$, положим $s_i=A_1+A_2+\cdots+A_i$. В частности, определим $s_0=0$.

• На шпажке находится $s_N$ клёцок, расположенных в один столбец сверху вниз.

• Каждая клёцка либо сладкая, либо острая. Вкус каждой клёцки описывается следующим образом.

  • Если $i$ — нечётное целое число, удовлетворяющее $1\le i\le N$, то клёцки с $(s_{i-1}+1)$-й по $s_i$-ю сверху сладкие.
  • Если $i$ — чётное целое число, удовлетворяющее $1\le i\le N$, то клёцки с $(s_{i-1}+1)$-й по $s_i$-ю сверху острые.

Bitaro придумал $Q$ возможных планов поедания клёцок с этой шпажки. План $j$ ($1\le j\le Q$) задаётся целыми числами $L_j$ и $R_j$, удовлетворяющими $1\le L_j\le R_j\le N$. В этом плане он съедает клёцки с $(s_{L_j-1}+1)$-й сверху по $s_{R_j}$-ю сверху.

Кроме того, Bitaro решил разделить поедание клёцок на несколько укусов следующим образом. Здесь $K$ — положительное целое число, описывающее предпочтение Bitaro к сладкому.

• Он ест клёцки сверху вниз, причём каждая клёцка съедается ровно один раз.
• За один укус он может съесть любое положительное количество последовательных клёцок на шпажке. Если среди клёцок, съеденных за этот укус, количество сладких минус количество острых составляет не менее $K$, Bitaro доволен.

По информации о шпажке с клёцками и планах напишите программу, которая для каждого плана вычисляет максимально возможное количество раз, когда Bitaro может быть доволен.

Входные данные

Считайте следующие данные со стандартного ввода.

$$ \begin{array}{l} N\ Q\ K\\ A_1\ A_2\ \cdots\ A_N\\ L_1\ R_1\\ L_2\ R_2\\ \vdots\\ L_Q\ R_Q \end{array} $$

Выходные данные

Выведите $Q$ строк на стандартный вывод. В $j$-й строке ($1\le j\le Q$) выведите максимальное количество раз, когда Bitaro может быть доволен в плане $j$.

Ограничения

• $1\le N\le500\,000$.
• $1\le Q\le500\,000$.
• $1\le K\le10^{14}$.
• $1\le A_i\le10^9$ ($1\le i\le N$).
• $1\le L_j\le R_j\le N$ ($1\le j\le Q$).
• Все заданные значения — целые числа.

Подзадачи

1. (6 баллов) $Q\le10$.
2. (5 баллов) $K\le2$.
3. (18 баллов) $K\le10$.
4. (27 баллов) $A_1+A_2+\cdots+A_N\le500\,000$.
5. (17 баллов) $N\le200\,000$, $Q\le200\,000$.
6. (27 баллов) Дополнительных ограничений нет.

Примеры

Входные данные 1

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

Выходные данные 1

7
2

Примечание

В первом плане Bitaro ест клёцки с первой по двенадцатую сверху. Последовательно съедая сверху ровно одну клёцку за укус, он может быть доволен 7 раз. Поскольку невозможно сделать его довольным 8 или более раз, следует вывести 7.

Во втором плане Bitaro ест клёцки с третьей по девятую сверху. Последовательно съедая сверху ровно одну клёцку за укус, он может быть доволен 2 раза. Поскольку невозможно сделать его довольным 3 или более раз, следует вывести 2.

Этот пример входных данных удовлетворяет ограничениям всех подзадач.

Входные данные 2

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

Выходные данные 2

2
0

Примечание

Этот пример отличается от примера входных данных 1 только значением $K$.

В первом плане Bitaro может быть доволен 2 раза, съев клёцки за следующие четыре укуса.

• За первый укус он съедает клёцки с первой по пятую сверху. Поскольку сладких клёцок 4, а острых 1, Bitaro доволен.
• За второй укус он съедает только шестую клёцку сверху. Поскольку сладких клёцок 0, а острых 1, Bitaro недоволен.
• За третий укус он съедает клёцки с седьмой по девятую сверху. Поскольку сладких клёцок 0, а острых 3, Bitaro недоволен.
• За четвёртый укус он съедает клёцки с десятой по двенадцатую сверху. Поскольку сладких клёцок 3, а острых 0, Bitaro доволен.

Поскольку невозможно сделать его довольным 3 или более раз, следует вывести 2.

Во втором плане невозможно съесть клёцки так, чтобы Bitaro был доволен хотя бы один раз, поэтому следует вывести 0.

Этот пример входных данных удовлетворяет ограничениям подзадач $1,3,4,5,6$.

Входные данные 3

9 4 50
24 26 89 45 84 72 15 31 66
1 9
2 8
4 6
5 6

Выходные данные 3

3
2
1
1

Примечание

Этот пример входных данных удовлетворяет ограничениям подзадач $1,4,5,6$.