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

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

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

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

因此，他考虑了 $Q$ 个问题。第 $j$ 个问题（$1\le j\le 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\le j\le Q$）中，如果可以达到所有鱼 $L_j$，$L_j+1$，...，$R_j$ 拥有其精确的理想智力值的状态，则输出需要放入水族箱的 $A$ 型食物的最小数量。否则，输出 $-1$。

样例输入 1

4 2
3 1 2 1
1
1 3

样例输出 1

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$ 的约束条件。

样例输入 2

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

样例输出 2

0
-1
0

样例解释 2

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

样例输入 3

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

样例输出 3

5
3
3

样例解释 3

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

样例输入 4

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

样例输出 4

9
8
0
-1

样例解释 4

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

约束条件

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

子任务

1. （9 分）$N\le 3,000$，$Q\le 3,000$
2. （7 分）$C_i\le 1$（$1\le i\le N$）
3. （28 分）$D=1$
4. （20 分）$C_i\ge C_{i+1}$（$1\le i\le N-1$）
5. （36 分）无额外约束。