Fish 3

JOI-kun is breeding $N$ fish in a large tank. Each fish is numbered from $1$ to $N$.

JOI-kun has two types of fish food, A and B, and both are available in sufficient quantities. Each time one piece of food is added to the tank, exactly one fish eats it, and any fish can eat it. The intelligence of each fish changes depending on the food type and the fish that ate it:

• When fish $k$ ($1 \le k \le N$) eats one piece of type A food, the intelligence of fish $k$ increases by exactly $D$.
• When fish $k$ ($1 \le k \le N$) eats one piece of type B food, the intelligence of every fish numbered $k$ and above increases by exactly $1$.

At the start, every fish has intelligence $0$. JOI-kun wants the intelligence of fish $i$ ($1 \le i \le N$) to equal its ideal intelligence $C_i$, but this is not always possible.

JOI-kun has $Q$ questions. The $j$-th question asks the following. Starting from intelligence $0$ for all fish, and repeating the action of adding food zero or more times, can fish $L_j, L_j+1, \dots, R_j$ all reach exactly their ideal intelligence values? If so, what is the minimum number of pieces of type A food that must be added to the tank?

Write a program that answers these questions, given the information about the fish and the questions.

The first line contains $N$ and $D$.

The second line contains $C_1, C_2, \cdots, C_N$.

The third line contains $Q$.

Each of the next $Q$ lines contains $L_j$ and $R_j$.

$N$ $D$

$C_1$ $C_2$ $\cdots$ $C_N$

$Q$

$L_1$ $R_1$

$L_2$ $R_2$

$\vdots$

$L_Q$ $R_Q$

Print $Q$ lines. On line $j$, print the minimum number of pieces of type A food needed to make fish $L_j, \dots, R_j$ have exactly their ideal intelligence values. If it is impossible, print -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$).
• All given values are integers.