Cho dãy \(n\) số nguyên, các phần tử trong dãy được đánh số thứ tự từ 1 đến \(n\). Dãy số được chia thành \(\frac{n}{k}\) đoạn, \(k\) là ước của \(n\), mỗi đoạn có \(k\) số theo quy luật:

- Đoạn thứ nhất có giá trị tăng dần từ 1 đến \(k\);

- Đoạn thứ hai có giá trị giảm dần từ \(2 \times k\) về \(k + 1\);

- Đoạn thứ ba có giá trị tăng dần từ \(2 \times k + 1\) đến \(3 \times k\);

- Đoạn thứ tư có giá trị giảm dần từ \(4 \times k\) về \(3 \times k + 1\);

…

- Đoạn thứ \(i\ (i \leq \frac{n}{k})\):

Nếu \(i\) lẻ: có giá trị tăng dần từ \((i - 1) \times k + 1\) đến \(i \times k\);

Nếu \(i\) chẵn: có giá trị giảm dần từ \(i \times k\) về \((i - 1) \times k + 1\);

Ví dụ với \(n = 24,\ k = 4\), dãy số nguyên có giá trị như sau:

1 2 3 4 8 7 6 5 9 10 11 12 16 15 14 13 17 18 19 20 24 23 22 21

Yêu cầu: Hãy tính tổng các số ở các vị trí từ \(l\) đến \(r\) trong dãy số đã cho.

Dữ liệu vào: Ghi 4 số nguyên \(n,\ k,\ l,\ r\) trên một dòng, trong đó \(k\) là ước của \(n\) \(\left( 1 \leq l \leq r \leq n \leq 10^{9} \right)\);

Kết quả: Ghi một số nguyên duy nhất cho biết kết quả bài toán.

Ví dụ:

Input	Output		Input	Output
24 1 1 24	300		24 4 7 21	209

Ràng buộc:

- Có 50% số test tương ứng 50% số điểm có \(k = 1\ \)hoặc \(k = n\);

- Có \(30\%\ \)số test khác tương ứng \(30\%\) số điểm có \(n \leq 10^{6}\);

- Có 20% số test còn lại tương ứng 20% số điểm không có ràng buộc gì thêm.