搬运行李（luggage）

题目描述

Y 同学是一名搬运员，他要依次经过一排仓库收取货物。

共有 $N$ 个仓库，从西向东依次编号为 $1,2,\dots,N$。第 $i$ 个仓库中有一件重量为 $A_i$ 的货物。

Y 同学会选择某个仓库 $s$ 作为出发点，开始时手中没有任何货物。随后他会从仓库 $s$ 开始，一直向东依次访问仓库 $s,s+1,s+2,\dots$。每到一个仓库，他都会立刻拿起该仓库中的货物，并将其加入当前负重中，而且之后不会放下已经拿到的货物。

在到达某个仓库后，Y 同学总是按如下过程行动：

先取走当前仓库中的货物，将其加入负重中。 然后检查当前负重总和。 如果当前负重严格大于 $K$，那么他无法继续前进，并停在当前仓库。 如果当前负重不超过 $K$，且当前仓库不是第 $N$ 个仓库，那么他会前往东边相邻的下一个仓库。 如果当前负重不超过 $K$，且当前仓库已经是第 $N$ 个仓库，那么由于已经没有更东边的仓库，他也会停在当前仓库。

换句话说，从仓库 $s$ 出发时，Y 同学会依次访问若干个连续仓库，并最终停在某个仓库 $t$。如果在访问到仓库 $t$ 后，区间 $[s,t]$ 的货物总重量第一次严格超过 $K$，那么他就停在 $t$；如果直到仓库 $N$ 都没有超过 $K$，那么他就停在仓库 $N$。

定义 $f(s)$ 表示从仓库 $s$ 出发时，Y 同学最终停下来的仓库编号。

现在有 $Q$ 次询问。每次询问给出两个整数 $L_j,R_j$，你需要计算：

输入格式

第一行输入三个整数 $N,K,Q$，分别表示仓库数量、负重上限以及询问次数。

第二行输入 $N$ 个整数 $A_1,A_2,\dots,A_N$，表示每个仓库中货物的重量。

接下来 $Q$ 行，每行输入两个整数 $L_j,R_j$，表示一次询问的起点编号范围。对于这一询问，需要求出所有起点属于区间 $[L_j,R_j]$ 时对应的停止位置编号之和。

输出格式

输出共 $Q$ 行。

第 $j$ 行输出一个整数，表示第 $j$ 次询问的答案，即

样例

样例输入 #1

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

样例输出 #1

23
13
15

数据范围与约定

对于 $100$ 的数据，保证：

• $1 \le N \le 2 \times 10^5$；
• $1 \le K \le 10^{15}$；
• $1 \le Q \le 2 \times 10^5$；
• $1 \le A_i \le 10^9$；
• $1 \le L_j \le R_j \le N$。

• 特殊性质 A：保证对于任意 $i$，都有 $A_i > K$。
• 特殊性质 B：保证序列 $A$ 单调不降。
• 特殊性质 C：保证所有询问都满足 $L_j = R_j$。