Trò chơi

Trong buổi lễ khai mạc của kỳ thi Olympic truyền thống 30 tháng 4, bạn Lê được Ban tổ chức mời tham gia một trò chơi nhỏ. Quản trò viết lên bảng $N$ số nguyên $A_1,A_2,\dots ,A_N$ thành một vòng tròn và bí mật chọn ra một đoạn liên tiếp gồm không quá $N-1$ số trên vòng tròn đó. Sau đó, quản trò nói cho Lê biết rằng tổng các số trong đoạn được chọn là một số không nhỏ hơn $L$ và không lớn hơn $R$. Lê được phép chọn một vị trí bất kỳ trên bảng, và nếu vị trí đó nằm trong đoạn mà quản trò đã chọn thì Lê sẽ nhận được một phần quà. Lê muốn khả năng nhận quà của mình là lớn nhất có thể nên muốn tính toán xem với mỗi vị trí $i$ trên vòng tròn, có bao nhiêu đoạn đi qua vị trí này mà quản trò có thể chọn.

Yêu cầu: Hãy giúp Lê giải quyết bài toán trên.

Dữ liệu vào

• Dòng đầu tiên gồm ba số nguyên $N,L,R$ ($2\le N\le 2·{10}^5$; $-2·{10}^{14}\le L\le R\le 2·{10}^{14}$).
• Dòng tiếp theo gồm $N$ số nguyên $A_1,A_2,\dots ,A_N$ ($-{10}^9\le A_i\le {10}^9$).

Dữ liệu ra

Một dòng duy nhất gồm $N$ số nguyên không âm, số nguyên thứ $i$ là số lượng đoạn đi qua vị trí $i$ mà quản trò có thể chọn.

Ràng buộc

• $2\le N\le 2·{10}^5$.
• $-2·{10}^{14}\le L\le R\le 2·{10}^{14}$.
• $-{10}^9\le A_i\le {10}^9$.

Subtasks

• Subtask 1 ($30\%$ số điểm): $N\le 200$.
• Subtask 2 ($30\%$ số điểm): $N\le 5000$.
• Subtask 3 ($20\%$ số điểm): $A_i\ge 0$ với mọi $i=1,2,\dots ,N$.
• Subtask 4 ($20\%$ số điểm): không có ràng buộc nào thêm.

Ví dụ