Các con bò đang miệt mài sáng tạo ra những trò chơi thú vị mới. Một trong những ý tưởng hiện tại của chúng liên quan đến một tập gồm \(N\) đoạn (\(1\le N\le 2\cdot 10^5\)), trong đó đoạn thứ \(i\) bắt đầu tại vị trí \(a_i\) trên trục số và kết thúc tại vị trí \(b_i \geq a_i\). Cả \(a_i\) và \(b_i\) đều là các số nguyên trong khoảng \(0 \ldots M\), với \(1 \leq M \leq 5000\).

Để chơi trò chơi, Bessie chọn một đoạn nào đó (giả sử là đoạn thứ \(i\)) và cô em họ Elsie chọn một đoạn nào đó (giả sử là đoạn thứ \(j\), có thể trùng với đoạn của Bessie). Với một giá trị \(k\), chúng thắng nếu \(a_i + a_j \leq k \leq b_i + b_j\).

Với mỗi giá trị \(k\) trong khoảng \(0 \ldots 2M\), hãy đếm số cặp có thứ tự \((i,j)\) mà Bessie và Elsie có thể thắng trò chơi.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(M\). Mỗi dòng trong \(N\) dòng tiếp theo mô tả một đoạn bằng hai số nguyên \(a_i\) và \(b_i\).

Dữ liệu ra

In ra \(2M+1\) dòng, mỗi dòng ứng với một giá trị \(k\) trong khoảng \(0 \ldots 2M\).

Phân nhóm

• Dữ liệu 1–2: \(N\le 100, M\le 100\).
• Dữ liệu 3–5: \(N\le 5000\).
• Dữ liệu 6–20: Không có ràng buộc bổ sung.

Lưu ý rằng các giá trị đầu ra có thể quá lớn để lưu trong số nguyên 32 bit, vì vậy bạn có thể cần sử dụng số nguyên 64 bit (chẳng hạn long long trong C hoặc C++).

Ví dụ

2 5
1 3
2 5

0
0
1
3
4
4
4
3
3
1
1

Nguồn

USACO 2021 December Contest, Silver — Convoluted Intervals. Tác giả: Benjamin Qi.

https://usaco.org/index.php?page=viewproblem2&cpid=1160