Bitaro kupił na przekąskę długi szpikulec z kluskami. Można go opisać za pomocą $N$ dodatnich liczb całkowitych $A_1,A_2,\ldots,A_N$ w następujący sposób. Dla każdej liczby całkowitej $i$ takiej, że $0\le i\le N$, niech $s_i=A_1+A_2+\cdots+A_i$. W szczególności definiujemy $s_0=0$.

• Na szpikulcu znajduje się $s_N$ klusek ułożonych w jednej kolumnie od góry do dołu.

• Każda kluska jest słodka albo ostra. Smak każdej kluski można opisać następująco.

  • Jeśli $i$ jest nieparzystą liczbą całkowitą spełniającą $1\le i\le N$, to kluski od $(s_{i-1}+1)$-szej do $s_i$-tej od góry są słodkie.
  • Jeśli $i$ jest parzystą liczbą całkowitą spełniającą $1\le i\le N$, to kluski od $(s_{i-1}+1)$-szej do $s_i$-tej od góry są ostre.

Bitaro przygotował $Q$ możliwych planów zjedzenia klusek ze szpikulca. Plan $j$ ($1\le j\le Q$) jest opisany liczbami całkowitymi $L_j$ i $R_j$ spełniającymi $1\le L_j\le R_j\le N$. W tym planie zjada on kluski od $(s_{L_j-1}+1)$-szej od góry do $s_{R_j}$-tej od góry.

Ponadto Bitaro postanowił podzielić jedzenie klusek na kilka kęsów w opisany poniżej sposób. Tutaj $K$ jest dodatnią liczbą całkowitą określającą upodobanie Bitaro do słodyczy.

• Zjada kluski od góry do dołu, a każda kluska zostaje zjedzona dokładnie raz.
• W jednym kęsie może zjeść dowolną dodatnią liczbę kolejnych klusek na szpikulcu. Jeśli wśród klusek zjedzonych w tym kęsie liczba słodkich klusek pomniejszona o liczbę ostrych klusek wynosi co najmniej $K$, Bitaro jest zadowolony.

Napisz program, który na podstawie informacji o szpikulcu z kluskami i planach obliczy dla każdego planu największą możliwą liczbę razy, gdy Bitaro będzie zadowolony.

Wejście

Wczytaj następujące dane ze standardowego wejścia.

$$ \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} $$

Wyjście

Wypisz $Q$ wierszy na standardowe wyjście. W $j$-tym wierszu ($1\le j\le Q$) wypisz największą liczbę razy, gdy Bitaro może być zadowolony w planie $j$.

Ograniczenia

• $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$).
• Wszystkie podane wartości są liczbami całkowitymi.

Podzadania

1. (6 punktów) $Q\le10$.
2. (5 punktów) $K\le2$.
3. (18 punktów) $K\le10$.
4. (27 punktów) $A_1+A_2+\cdots+A_N\le500\,000$.
5. (17 punktów) $N\le200\,000$, $Q\le200\,000$.
6. (27 punktów) Brak dodatkowych ograniczeń.

Przykład

Wejście 1

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

Wyjście 1

7
2

Uwagi

W pierwszym planie Bitaro zjada kluski od pierwszej do dwunastej od góry. Jedząc od góry po jednej klusce w każdym kęsie, Bitaro może być zadowolony 7 razy. Ponieważ nie można sprawić, by był zadowolony 8 lub więcej razy, należy wypisać 7.

W drugim planie Bitaro zjada kluski od trzeciej do dziewiątej od góry. Jedząc od góry po jednej klusce w każdym kęsie, Bitaro może być zadowolony 2 razy. Ponieważ nie można sprawić, by był zadowolony 3 lub więcej razy, należy wypisać 2.

To przykładowe wejście spełnia ograniczenia wszystkich podzadań.

Wejście 2

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

Wyjście 2

2
0

Uwagi

To wejście różni się od przykładowego wejścia 1 jedynie wartością $K$.

W pierwszym planie Bitaro może być zadowolony 2 razy, zjadając kluski w następujących czterech kęsach.

• W pierwszym kęsie zjada kluski od pierwszej do piątej od góry. Ponieważ słodkich klusek jest 4, a ostrych 1, Bitaro jest zadowolony.
• W drugim kęsie zjada jedynie szóstą kluskę od góry. Ponieważ słodkich klusek jest 0, a ostrych 1, Bitaro nie jest zadowolony.
• W trzecim kęsie zjada kluski od siódmej do dziewiątej od góry. Ponieważ słodkich klusek jest 0, a ostrych 3, Bitaro nie jest zadowolony.
• W czwartym kęsie zjada kluski od dziesiątej do dwunastej od góry. Ponieważ słodkich klusek jest 3, a ostrych 0, Bitaro jest zadowolony.

Ponieważ nie można sprawić, by był zadowolony 3 lub więcej razy, należy wypisać 2.

W drugim planie nie da się zjeść klusek tak, aby Bitaro był zadowolony choć raz, więc należy wypisać 0.

To przykładowe wejście spełnia ograniczenia podzadań $1,3,4,5,6$.

Wejście 3

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

Wyjście 3

3
2
1
1

Uwagi

To przykładowe wejście spełnia ograniczenia podzadań $1,4,5,6$.