Hệ Thống Mai Mối Tình Yêu AI

Trường Đại học Công nghệ Tương lai vừa cho ra mắt một hệ thống AI đặc biệt mang tên "Mai Mối Chuẩn Gen", với nhiệm vụ giúp sinh viên cô đơn tìm được nửa kia phù hợp nhất dựa trên chỉ số "tương thích cảm xúc".

Có \(n\) sinh viên tham gia hệ thống, mỗi người được hệ thống đánh giá bằng một chỉ số \(a_1, a_2, ..., a_n\) thể hiện mức độ đồng điệu về cảm xúc.

Hệ thống hoạt động bằng cách chia dãy chỉ số cảm xúc thành các đoạn con liên tiếp, không giao nhau. Một đoạn được xem là tối ưu nếu trung bình cộng của các chỉ số trong đoạn đúng bằng một giá trị lý tưởng \(x\) mà hệ thống đưa ra.

Mỗi khi có sinh viên đăng ký tham gia, hệ thống sẽ yêu cầu trả lời một truy vấn dạng:

Trong khoảng từ người thứ \(l\) đến người thứ \(r\), có thể chia được tối đa bao nhiêu đoạn con liên tiếp, không giao nhau sao cho trung bình cộng của mỗi đoạn đúng bằng \(x\)?

Bạn được giao nhiệm vụ xử lý \(q\) truy vấn như vậy, để giúp hệ thống hoạt động hiệu quả hơn!

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(q\), \(x\) \((1 \le n, q \le 2 \cdot 10^5, 1 \le x \le 10^6)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\) là chỉ số cảm xúc của từng sinh viên \((1 \le a_i \le 10^6)\).
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l_i\), \(r_i\) \((1 \le l_i \le r_i \le n)\).

Output

• Gồm \(q\) dòng, dòng thứ \(i\) là đáp án cho truy vấn thứ \(i\) --- số đoạn con liên tiếp, không giao nhau trong đoạn \([l_i, r_i]\) sao cho trung bình cộng đúng bằng \(x\).

Example

10 1 5
6 7 2 5 6 1 8 7 4 6
1 10

4

Scoring

• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(n, q \leq 200\).
• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(n, q \leq 2000\).
• Có \(40\%\) số test tương ứng với \(40\%\) số điểm không có ràng buộc gì thêm.