Bitaro 买了一串长长的团子作为零食。这串团子可以用 $N$ 个正整数 $A_1, A_2, \dots, A_N$ 来表示。对于每个 $0 \le i \le N$ 的整数，令 $s_i = A_1 + A_2 + \dots + 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 感到满足的最大次数。

输入格式

从标准输入读取以下数据：

$N \ Q \ K$ $A_1 \ A_2 \ \dots \ 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 \le 500\,000$
• $1 \le Q \le 500\,000$
• $1 \le K \le 10^{14}$
• $1 \le A_i \le 10^9$ ($1 \le i \le N$)
• $1 \le L_j \le R_j \le N$ ($1 \le j \le Q$)
• 给定值均为整数。

子任务

1. (6 分) $Q \le 10$
2. (5 分) $K \le 2$
3. (18 分) $K \le 10$
4. (27 分) $A_1 + A_2 + \dots + A_N \le 500\,000$
5. (17 分) $N \le 200\,000, Q \le 200\,000$
6. (27 分) 无附加限制。

样例

样例输入 1

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

样例输出 1

7
2

说明 1

对于第一个计划，Bitaro 吃掉从上往下数第 1 到第 12 个团子。通过每次只吃一个团子，Bitaro 可以感到满足 7 次。由于不可能让他感到满足 8 次或更多，你应该输出 7。

对于第二个计划，Bitaro 吃掉从上往下数第 3 到第 9 个团子。通过每次只吃一个团子，Bitaro 可以感到满足 2 次。由于不可能让他感到满足 3 次或更多，你应该输出 2。

样例输入 2

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

样例输出 2

2
0

说明 2

这与样例 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。

样例输入 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