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

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 \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 $）
• 给定值均为整数。

子任务

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