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$ — додатне ціле число, що описує його вподобання щодо солодкого.

• Він їсть кульки згори донизу, причому кожну кульку з'їдає рівно один раз.
• За один укус він може з'їсти довільну додатну кількість послідовних кульок на шампурі. Якщо кількість солодких кульок у цьому укусі мінус кількість гострих становить щонайменше $K$, Bitaro буде задоволений.

За інформацією про кульки на шампурі та плани напишіть програму, яка для кожного плану обчислює максимальну кількість разів, коли Bitaro може бути задоволений.

Вхідні дані

Зчитайте зі стандартного вводу такі дані.

$N\ Q\ K$

$A_1\ A_2\ \cdots\ A_N$

$L_1\ R_1$

$L_2\ R_2$

$\vdots$

$L_Q\ R_Q$

Вихідні дані

Виведіть $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 з'їдає кульки від першої до $12$-ї згори. Послідовно з'їдаючи згори рівно одну кульку за укус, він може бути задоволений $7$ разів. Оскільки бути задоволеним $8$ або більше разів неможливо, слід вивести $7$.

За другим планом Bitaro з'їдає кульки від третьої до $9$-ї згори. Послідовно з'їдаючи згори рівно одну кульку за укус, він може бути задоволений $2$ рази. Оскільки бути задоволеним $3$ або більше разів неможливо, слід вивести $2$.

Цей приклад задовольняє обмеження всіх підзадач.

Вхідні дані 2

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

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

2
0

Пояснення

Цей приклад відрізняється від першого лише значенням $K$.

За першим планом Bitaro може бути задоволений $2$ рази, з'ївши кульки за такі чотири укуси.

• За перший укус він з'їдає кульки від першої до п'ятої згори. Солодких кульок $4$, а гострих $1$, тому Bitaro задоволений.
• За другий укус він з'їдає лише шосту кульку згори. Солодких кульок $0$, а гострих $1$, тому Bitaro не задоволений.
• За третій укус він з'їдає кульки від сьомої до дев'ятої згори. Солодких кульок $0$, а гострих $3$, тому Bitaro не задоволений.
• За четвертий укус він з'їдає кульки від $10$-ї до $12$-ї згори. Солодких кульок $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$.