题目描述

JOI 君在一个大水缸中饲养着 $N$ 条鱼，每条鱼的编号从 $1$ 到 $N$。

JOI 君有两种类型的鱼食，$A$ 和 $B$，两种都有足够的数量。当往水族箱中添加一块食物时，恰好有一条鱼吃掉它（任何鱼都可以吃掉它），并且根据食物的类型以及吃掉它的鱼的情况，鱼的智力变化如下：

• 当第 $k$ 条鱼（$1 \leq k \leq N$）吃掉一块 $A$ 型食物时，第 $k$ 条鱼的智力恰好增加 $D$。
• 当第 $k$ 条鱼（$1 \leq k \leq N$）吃掉一块 $B$ 型食物时，编号大于等于 $k$ 的所有鱼的智力都恰好增加 $1$。

目前，所有鱼的智力都为 $0$。JOI 君希望使第 $i$ 条鱼（$1 \leq i \leq N$）的智力等于其理想智力 $C_i$，但这并不总是可能的。

因此，他考虑了 $Q$ 个问题。第 $j$ 个问题（$1 \leq j \leq Q$）如下：

• 从所有鱼的智力都为 0 的状态开始，通过重复将食物放入水族箱零次或多次的动作，是否可能达到所有鱼 $L_j , L_j + 1 ,..., R_j$ 都拥有其精确的理想智力值的状态？此外，如果可能，需要放入水族箱的 A 型食物的最小数量是多少？

编写一个程序，给定有关 JOI 君的鱼的信息以及有关问题的信息，回答他的问题。

输入格式

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

• $N,D$
• $C_1,C_2,...,C_N$
• $Q$
• $L_1,R_1$
• $L_2,R_2$
• ...
• $L_Q,R_Q$

输出格式

输出共 $Q$ 行。在第 $j$ 行（$1 \leq j \leq Q$）中，如果可以达到所有鱼 $L_j$，$L_j + 1$，...，$R_j$ 拥有其精确的理想智力值的状态，则输出需要放入水族箱的 $A$ 型食物的最小数量。否则，输出 $-1$。

输入输出样例 #1

输入 #1

4 2
3 1 2 1
1
1 3

输出 #1

1

输入输出样例 #2

输入 #2

4 2
0 1 0 1
3
1 2
2 3
1 1

输出 #2

0
-1
0

输入输出样例 #3

输入 #3

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

输出 #3

5
3
3

输入输出样例 #4

输入 #4

6 3
16 14 13 8 6 5
4
1 4
2 5
3 3
1 6

输出 #4

9
8
0
-1

说明/提示

样例解释 1

例如，在以下情况下，所有鱼 $1,2,3$ 最终都达到了其精确的理想智力值，且放入水族箱的 $A$ 型食物的数量为 $1$。

• 起初，鱼 $1,2,3,4$ 的智力分别为 $0,0,0,0$。
• 接下来，JOI 君将一块 $B$ 型食物放入水族箱，被鱼 $3$ 吃掉。结果，鱼 $1,2,3,4$ 的智力分别变为 $0,0,1,1$。
• 然后，JOI 君将一块 $A$ 型食物放入水族箱，被鱼 $1$ 吃掉。结果，鱼 $1,2,3,4$ 的智力分别变为 $2,0,1,1$。
• 最后，JOI 君将一块 $B$ 型食物放入水族箱，被鱼 $1$ 吃掉。结果，鱼 $1,2,3,4$ 的智力分别变为 $3,1,2,2$。
• 由于不放入任何 $A$ 型食物就无法达到所有鱼 $1,2,3$ 的精确理想智力值的状态，输出 $1$。

这个样例满足子任务 $1$ 和 $5$ 的约束条件。

约束条件

• $1 \leq N \leq 300,000$。
• $1 \leq Q \leq 300,000$。
• $1 \leq D \leq 10^{12}$。
• $0 \leq C_i \leq 10^{12}$（$1 \leq i \leq N$）。
• $1 \leq L_j \leq R_j \leq N$（$1 \leq j \leq Q$）。
• 给定值均为整数。

子任务

• （9 分）$N \leq 3,000$，$Q \leq 3,000$。
• （7 分）$C_i \leq 1$（$1 \leq i \leq N$）。
• （28 分）$D = 1$。
• （20 分）$C_i \geq C_{i+1}$（$1 \leq i \leq N - 1$）。
• （36 分）无额外约束。