JOI-kun đang nuôi \(N\) con cá trong một bể lớn. Các con cá được đánh số từ \(1\) đến \(N\).

JOI-kun có hai loại thức ăn \(A\) và \(B\), với số lượng đủ nhiều. Khi thả một viên thức ăn vào bể, đúng một con cá ăn viên đó (bất kỳ con cá nào cũng có thể ăn được). Tùy vào loại thức ăn và con cá đã ăn, độ thông minh của các con cá thay đổi như sau:

• Khi cá \(k\) (\(1 \le k \le N\)) ăn một viên thức ăn loại \(A\), độ thông minh của riêng cá \(k\) tăng đúng \(D\).
• Khi cá \(k\) (\(1 \le k \le N\)) ăn một viên thức ăn loại \(B\), độ thông minh của tất cả các con cá có số thứ tự từ \(k\) trở lên đều tăng đúng \(1\).

Hiện tại, độ thông minh của mọi con cá đều bằng \(0\). JOI-kun muốn độ thông minh của cá \(i\) (\(1 \le i \le N\)) bằng giá trị lý tưởng \(C_i\), nhưng điều này không phải lúc nào cũng thực hiện được.

Vì vậy, cậu đặt ra \(Q\) câu hỏi. Câu hỏi thứ \(j\) (\(1 \le j \le Q\)) như sau:

• Bắt đầu từ trạng thái mà độ thông minh của mọi con cá đều bằng \(0\), có khả năng nào để sau khi thực hiện thao tác thả một viên thức ăn vào bể không hoặc nhiều lần, độ thông minh của tất cả các con cá \(L_j,L_j+1,\ldots,R_j\) đồng thời bằng đúng giá trị lý tưởng tương ứng hay không? Nếu có, số viên thức ăn loại \(A\) ít nhất có thể đã thả vào bể là bao nhiêu?

Hãy viết chương trình trả lời các câu hỏi khi biết thông tin về đàn cá và các câu hỏi của JOI-kun.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

N D
C_1 C_2 ... C_N
Q
L_1 R_1
L_2 R_2
...
L_Q R_Q

Dữ liệu ra

In \(Q\) dòng ra đầu ra chuẩn. Trên dòng thứ \(j\) (\(1 \le j \le Q\)), nếu có thể làm cho tất cả các con cá \(L_j,L_j+1,\ldots,R_j\) đạt đúng độ thông minh lý tưởng tương ứng, in số viên thức ăn loại \(A\) ít nhất cần thả vào bể. Nếu không thể, in -1.

Ràng buộc

• \(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\)).
• Tất cả các giá trị đầu vào đều là số nguyên.

Phân nhóm

1. 9 điểm: \(N \le 3\,000\), \(Q \le 3\,000\).
2. 7 điểm: \(C_i \le 1\) với mọi \(1 \le i \le N\).
3. 28 điểm: \(D=1\).
4. 20 điểm: \(C_i \ge C_{i+1}\) với mọi \(1 \le i \le N-1\).
5. 36 điểm: Không có ràng buộc bổ sung.

Ví dụ

4 2
3 1 2 1
1
1 3

1

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

0
-1
0

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

5
3
3

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

9
8
0
-1

Nguồn

Bản dịch tiếng Việt từ đề tiếng Anh và tiếng Nhật của JOI 2023/2024, vòng tuyển chọn mùa xuân, ngày thi thứ nhất, do Ủy ban Olympic Tin học Nhật Bản (JCIOI) cung cấp. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.