题目描述

Bitaro 买了一长串团子作为零食。这串团子可以用 $N$ 个正整数 $A_1, A_2, \cdots, A_N$ 表示如下。对于每个满足 $0 \leq i \leq N$ 的整数 $i$，令 $s_i = A_1 + A_2 + \cdots + A_i$。特别地，我们定义 $s_0 = 0$。

• 这串团子由 $s_N$ 个团子组成，从上到下排成一列。
• 每个团子要么是甜的，要么是辣的。每个团子的口味可以描述如下。
  • 如果 $i$ 是一个满足 $1 \leq i \leq N$ 的奇数，那么从上往下数第 $(s_{i-1} + 1)$ 个到第 $s_i$ 个团子是甜的。
  • 如果 $i$ 是一个满足 $1 \leq i \leq N$ 的偶数，那么从上往下数第 $(s_{i-1} + 1)$ 个到第 $s_i$ 个团子是辣的。

在吃这串团子时，Bitaro 制订了 $Q$ 种可能的计划。第 $j$ 个计划（$1 \leq j \leq Q$）由满足 $1 \leq L_j \leq R_j \leq 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 \leq j \leq Q$），输出在第 $j$ 个计划中 Bitaro 能够感到满足的最大次数。

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

7
2

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

2
0

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

3
2
1
1

提示

样例 1

对于第一个计划，Bitaro 吃掉从上往下数第 $1$ 到第 $12$ 个团子。通过反复从顶部每口恰好吃一个团子，Bitaro 可以感到满足 $7$ 次。因为不可能让他感到满足 $8$ 次或更多，所以你应该输出 $7$。

对于第二个计划，Bitaro 吃掉从上往下数第 $3$ 到第 $9$ 个团子。通过反复从顶部每口恰好吃一个团子，Bitaro 可以感到满足 $2$ 次。因为不可能让他感到满足 $3$ 次或更多，所以你应该输出 $2$。

这个样例输入满足所有子任务的约束条件。

样例 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$。

这个样例输入满足子任务 $1,3,4,5,6$ 的约束条件。

样例 3

这个样例输入满足子任务 $1,4,5,6$ 的约束条件。

约束条件

• $1 \leq N \leq 500000$。
• $1 \leq Q \leq 500000$。
• $1 \leq K \leq 10^{14}$。
• $1 \leq A_i \leq 10^9$ ($1 \leq i \leq N$)。
• $1 \leq L_j \leq R_j \leq N$ ($1 \leq j \leq Q$)。
• 给定的值都是整数。

子任务

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