Cao Thanh Hùng là một anh chàng nghiện game có tiếng, anh ta luôn ngồi trong phòng của mình và cày game đến sáng, chính vì vậy anh ta vẫn ế đến tận bây giờ.
Chính vì thiếu gái ngoài đời nên Hùng đang cố tìm một game để xây dựng một dàn harem cho riêng mình.

Hùng đã tìm được một game khá thú vị để thoả mãn sở thích của mình. Game cho Hùng một dàn harem gồm \(n\) cô gái lần lượt có chỉ số xinh đẹp là \(a_1, a_2, \dots, a_n\).

Game còn cho Hùng một số nguyên \(x\) gọi là độ đẹp cân đối.

Độ đẹp của một dãy các cô gái là số dãy con liên tiếp nhiều nhất có thể chọn trong dãy mà các dãy con không giao nhau và trung bình cộng chỉ số xinh đẹp của mỗi dãy con đều bằng \(x\).

Hùng phải trả lời \(q\) câu hỏi game đưa ra để rước cả dàn harem này về cho mình.

Câu hỏi thứ \(i\) gồm 2 số \(l_i\) và \(r_i\) yêu cầu Hùng tính độ đẹp của dãy harem \(a_{l_i} \dots a_{r_i}\).

Do bị bệnh ế đeo bám bao lâu nay nên đầu óc Hùng rất lú lẫn nên rất khó để trả lời các câu hỏi của game, bình thường những lúc này thì Hùng thường nhờ đến Vinh giúp đỡ (Vinh không ế nên rất tỉnh táo), mà đúng hôm nay Vinh lại bận đi chơi với bạn gái nên không giúp được.

Hùng đành nhờ đến các bạn giúp đỡ, hãy giúp Hùng nhé!

Input

• Dòng thứ nhất gồm 3 số nguyên dương \(n, q, x\) (\(n, q \le 2\cdot 10^5\), \(x \le 10^6\)).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(a_i \le 10^6\)).
• \(q\) dòng tiếp theo, mỗi dòng gồm 2 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 của câu hỏi thứ \(i\).

Scoring

• Subtask 1 (\(30\%\) số điểm): \(n, q \le 500\).
• Subtask 2 (\(40\%\) số điểm): \(500 < n, q \le 5000\).
• Subtask 3 (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

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

4