Yêu cầu: Cho \(N\) số nguyên \(A_1, A_2, \dots, A_N\) xếp thành một vòng tròn. Cần tính xem với mỗi vị trí \(i\) trên vòng tròn, có bao nhiêu đoạn liên tiếp (gồm không quá \(N - 1\) phần tử) đi qua vị trí này sao cho tổng các số trong đoạn đó nằm trong đoạn \([L, R]\).

Input

Đọc từ file văn bản CGAME.INP:

• Dòng đầu tiên gồm 3 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

Ghi ra file văn bản CGAME.OUT:

• Gồm một dòng duy nhất gồm \(N\) số nguyên không âm, số thứ \(i\) là số lượng đoạn đi qua vị trí \(i\) thỏa mãn điều kiện.

Scoring

• Subtask \(1\) (\(2.1\) điểm): \(N \le 200\)
• Subtask \(2\) (\(2.1\) điểm): \(N \le 5000\)
• Subtask \(3\) (\(1.4\) điểm): \(A_i \ge 0\) với mọi \(i = 1, 2, \dots, N\)
• Subtask \(4\) (\(1.4\) điểm): Không có ràng buộc nào thêm

Example

5 6 7
1 2 3 4 5

2 1 2 1 1

3 1 2
1 -1 2

1 1 2