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.

Input

• Dòng đầu tiên gồm ba số nguyên ~N, L, R~ ~(2 \le N \le 2 \cdot 10^5; -2 \cdot 10^{14} \le L \le R \le 2 \cdot 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)~.

Output

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.

Scoring

Sample Input 1

5 6 7
1 2 3 4 5

Sample Output 1

2 1 2 1 1

Sample Input 2

3 1 2
1 -1 2

Sample Output 2

1 1 2

Notes

Trong ví dụ thứ nhất, ác đoạn thỏa mãn là ~(1, 2, 3)~, ~(3, 4)~, ~(5, 1)~. Trong các đoạn này, vị trí ~1~, ~3~ và ~5~ có ~2~ lần xuất hiện, các vị trí khác có ~1~ lần xuất hiện.

Trong ví dụ thứ hai, đoạn thỏa mãn là ~(1)~, ~(-1, 2)~, ~(2)~. Trong các đoạn này, vị trí ~1~ và ~2~ xuất hiện ~1~ lần, vị trí ~3~ xuất hiện ~2~ lần.