물고기 3

JOI-kun은 큰 수조에서 물고기 $N$마리를 기르고 있다. 각 물고기에는 $1$부터 $N$까지 번호가 붙어 있다.

JOI-kun에게는 A와 B 두 종류의 먹이가 있으며, 두 먹이 모두 충분히 있다. 수조에 먹이를 한 개 넣으면 물고기 한 마리가 정확히 그 먹이를 먹는다. 어떤 물고기든 먹을 수 있다. 먹이 종류와 먹은 물고기에 따라 물고기의 지능은 다음과 같이 변한다.

• 물고기 $k$ ($1 \le k \le N$)가 A 먹이를 한 개 먹으면, 물고기 $k$의 지능이 정확히 $D$만큼 증가한다.
• 물고기 $k$ ($1 \le k \le N$)가 B 먹이를 한 개 먹으면, 번호가 $k$ 이상인 모든 물고기의 지능이 각각 정확히 $1$씩 증가한다.

처음에는 모든 물고기의 지능이 $0$이다. JOI-kun은 물고기 $i$ ($1 \le i \le N$)의 지능을 이상적인 지능 $C_i$와 같게 만들고 싶어 하지만, 항상 가능한 것은 아니다.

JOI-kun에게는 $Q$개의 질문이 있다. $j$번째 질문은 다음과 같다. 모든 지능이 $0$인 상태에서 먹이를 넣는 행동을 0번 이상 반복하여, 물고기 $L_j, L_j+1, \dots, R_j$의 지능을 모두 이상적인 값과 정확히 같게 만들 수 있는가? 가능하다면, 수조에 넣어야 하는 A 먹이의 최소 개수는 얼마인가?

물고기 정보와 질문 정보가 주어졌을 때, 이 질문들에 답하는 프로그램을 작성하라.

첫째 줄에 $N$과 $D$가 주어진다.

둘째 줄에 $C_1, C_2, \cdots, C_N$이 주어진다.

셋째 줄에 $Q$가 주어진다.

이후 $Q$개의 줄에 각각 $L_j$와 $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$

$Q$개의 줄을 출력한다. $j$번째 줄에는 물고기 $L_j, \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$).
• 주어지는 모든 값은 정수이다.