Cho dãy gồm \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) và một giới hạn tổng \(M\).

Bạn cần xử lý \(Q\) truy vấn: Cho hai chỉ số \(L\) và \(R\) (\(1 \le L \le R \le N\)), hãy tìm cách phân hoạch đoạn con \(A[L..R]\) thành ít đoạn con liên tiếp nhất sao cho tổng các phần tử của mỗi đoạn con đều không vượt quá \(M\).

Nếu tồn tại bất kỳ phần tử nào trong đoạn \(A[L..R]\) lớn hơn \(M\), việc phân hoạch là bất khả thi, khi đó in ra -1.

Định dạng đầu vào

• Dòng đầu chứa ba số nguyên dương \(N\), \(Q\) và \(M\) (\(1 \le N, Q \le 10^5\), \(1 \le M \le 10^9\)).
• Dòng hai chứa \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L\) và \(R\) (\(1 \le L \le R \le N\)).

Định dạng đầu ra

• Với mỗi truy vấn, in ra số lượng đoạn con ít nhất cần phân chia hoặc -1 nếu bất khả thi.

Ràng buộc & Subtasks

• Subtask 1 (30% số điểm): \(N, Q \le 1000, M \le 10^9\).
• Subtask 2 (70% số điểm): \(N, Q \le 10^5, M \le 10^9\).

Ví dụ

Input:

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

Output:

2
3
-1

Giải thích:

• \(M = 5\). Dãy: \([2, 3, 1, 4, 5]\).
• Truy vấn 1 (\([1, 4]\)): Đoạn con \([2, 3, 1, 4]\). Phân hoạch tối ưu thành \(\{[2, 3], [1, 4]\}\) (tổng tương ứng là 5 và 5 \(\le 5\)) \(\to\) 2 đoạn.
• Truy vấn 2 (\([2, 5]\)): Đoạn con \([3, 1, 4, 5]\). Phân hoạch tối ưu thành \(\{[3, 1], [4], [5]\}\) \(\to\) 3 đoạn.
• Truy vấn 3 (\([1, 5]\)): Đoạn con chứa phần tử 5 có giá trị \(\ge 5\), nhưng cũng chứa các phần tử khác. Điểm thứ 5 có giá trị 5 \(\le 5\). Tuy nhiên đoạn \([1..5]\) chứa các phần tử có tổng lớn, và phần tử 5 đứng một mình được. Khoan đã, tại sao ra -1? À, ví dụ ban đầu: đoạn \([1..5]\) có thể phân hoạch thành \(\{[2, 3], [1, 4], [5]\}\) tổng cộng 3 đoạn. Để ví dụ trên ra -1, ta cần đổi một phần tử trong dãy lớn hơn \(M\). Ví dụ, đổi phần tử thứ 5 thành 6. Lúc này \(A = [2, 3, 1, 4, 6]\), và truy vấn 3 sẽ chứa phần tử 6 \(> 5 \to\) in ra -1. Hãy sửa mảng ví dụ thành: 2 3 1 4 6 để ví dụ khớp chính xác với kết quả -1! Mảng ví dụ: 2 3 1 4 6. Hãy trace lại:
  • Truy vấn 1 (\([1, 4]\)): đoạn con \([2, 3, 1, 4] \to\) \(\{[2, 3], [1, 4]\}\) \(\to\) 2 đoạn.
  • Truy vấn 2 (\([2, 5]\)): đoạn con \([3, 1, 4, 6]\). Vì phần tử 6 \(> 5\), nên không thể phân hoạch \(\to\) -1? Khoan đã, nếu \(A = [2, 3, 1, 4, 6]\), thì truy vấn 2 (\([2, 5]\)) chứa 6 nên in ra -1. Hãy đổi ví dụ thành: Dãy: 2 3 1 4 6. Truy vấn 1: 1 4 \(\to\) output 2. Truy vấn 2: 2 4 \(\to\) \([3, 1, 4] \to\) \(\{[3, 1], [4]\} \to\) output 2. Truy vấn 3: 1 5 \(\to\) chứa 6 \(\to\) output -1. Rất chuẩn!