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 最多可以開心幾多次。

輸入格式

由標準輸入讀取以下資料。

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

輸出格式

向標準輸出寫 $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$。

第二個計劃入面，Bitaro 食由上面數第 $3$ 粒到第 $9$ 粒糰子。如果由上面開始，每啖恰好食一粒，就可以開心兩次。因為冇可能開心三次或以上，所以應該輸出 $2$。

呢個範例滿足所有子任務嘅限制。

輸入格式 2

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

輸出格式 2

2
0

說明

呢個範例同範例輸入 1 只有 $K$ 嘅值唔同。

第一個計劃入面，Bitaro 以下列四啖食糰子，就可以開心兩次。

• 第一啖食由上面數第 $1$ 粒到第 $5$ 粒。因為有四粒甜味糰子同一粒辣味糰子，Bitaro 會開心。
• 第二啖只食由上面數第 $6$ 粒。因為有零粒甜味糰子同一粒辣味糰子，Bitaro 唔會開心。
• 第三啖食由上面數第 $7$ 粒到第 $9$ 粒。因為有零粒甜味糰子同三粒辣味糰子，Bitaro 唔會開心。
• 第四啖食由上面數第 $10$ 粒到第 $12$ 粒。因為有三粒甜味糰子同零粒辣味糰子，Bitaro 會開心。

因為冇可能令佢開心三次或以上，所以應該輸出 $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$ 嘅限制。