Bitaro 買了一長串糰子當點心。這串糰子可以用 $N$ 個正整數 $A_1,A_2,\ldots,A_N$ 描述如下。對每個滿足 $0\le i\le N$ 的整數 $i$，令 $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$）由滿足 $1\le L_j\le R_j\le N$ 的整數 $L_j,R_j$ 表示。在這個方案中，他會吃掉由上數第 $s_{L_j-1}+1$ 顆到第 $s_{R_j}$ 顆糰子。

此外，Bitaro 決定按照以下方式，分成幾口吃掉糰子。其中，$K$ 是表示 Bitaro 對甜味偏好的正整數。

• 他由上到下吃糰子，每顆糰子都恰好吃一次。
• 每一口可以吃任意正數量的連續糰子。如果這一口吃下的甜糰子數減去辣糰子數至少為 $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$）輸出第 $j$ 個方案中 Bitaro 最多可以感到滿足的次數。

資料範圍

• $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 吃掉由上數第 $1$ 顆到第 $12$ 顆糰子。從上到下每口恰好吃一顆，可以感到滿足 $7$ 次。由於不可能感到滿足 $8$ 次或更多，因此應輸出 $7$。

第二個方案中，Bitaro 吃掉由上數第 $3$ 顆到第 $9$ 顆糰子。從上到下每口恰好吃一顆，可以感到滿足 $2$ 次。由於不可能感到滿足 $3$ 次或更多，因此應輸出 $2$。

這個範例滿足所有子任務的限制。

輸入格式 2

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

輸出格式 2

2
0

說明

這個範例與範例輸入 $1$ 只有 $K$ 的值不同。

第一個方案中，Bitaro 可以分成以下四口吃糰子，感到滿足 $2$ 次。

• 第一口吃掉由上數第 $1$ 顆到第 $5$ 顆糰子。甜糰子有 $4$ 顆，辣糰子有 $1$ 顆，因此 Bitaro 感到滿足。
• 第二口只吃掉由上數第 $6$ 顆糰子。甜糰子有 $0$ 顆，辣糰子有 $1$ 顆，因此 Bitaro 沒有感到滿足。
• 第三口吃掉由上數第 $7$ 顆到第 $9$ 顆糰子。甜糰子有 $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$ 的限制。