JOI-kun 正在一个大鱼缸里养 $N$ 条鱼，每条鱼的编号从 $1$ 到 $N$。

JOI-kun 有两种鱼食，A 和 B，数量充足。当向鱼缸中投入一块食物时，恰好有一条鱼会吃掉它（任何一条鱼都可能吃掉），根据食物的种类以及吃掉食物的鱼，鱼的智力变化如下：

• 当编号为 $k$ ($1 \le k \le N$) 的鱼吃掉一块 A 类食物时，该鱼的智力恰好增加 $D$。
• 当编号为 $k$ ($1 \le k \le N$) 的鱼吃掉一块 B 类食物时，编号为 $k$ 及以上的所有鱼的智力各增加 $1$。

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

因此，他考虑了 $Q$ 个问题。第 $j$ 个问题 ($1 \le j \le Q$) 如下：

• 从所有鱼的智力均为 $0$ 的状态开始，通过重复零次或多次投入食物的操作，是否可能达到所有鱼 $L_j, L_j + 1, \dots, R_j$ 的智力恰好等于其理想智力值的状态？如果可能，投入鱼缸的 A 类食物的最少数量是多少？

请编写一个程序，在给定 JOI-kun 的鱼的信息和问题信息的情况下，回答他的问题。

输入格式

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

$N \ D$ $C_1 \ C_2 \dots C_N$ $Q$ $L_1 \ R_1$ $L_2 \ R_2$ $\vdots$ $L_Q \ R_Q$

输出格式

输出 $Q$ 行到标准输出。在第 $j$ 行 ($1 \le j \le Q$) 中，如果可以达到所有鱼 $L_j, L_j + 1, \dots, R_j$ 的智力恰好等于其理想智力值的状态，则输出需要投入的 A 类食物的最少数量。否则，输出 $-1$。

数据范围

• $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 分) 无附加限制。

样例

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