Convoluted Intervals

Cho $N$ đoạn trên trục số, đoạn thứ $i$ có hai đầu mút $a_i$ và $b_i$ (với $0\le a_i\le b_i\le M$).

Bessie và Elsie mỗi người chọn một đoạn (có thể trùng nhau). Giả sử Bessie chọn đoạn $i$, Elsie chọn đoạn $j$. Họ thắng nếu tồn tại số nguyên $k$ thỏa mãn $a_i+a_j\le k\le b_i+b_j$.

Với mỗi $k$ từ $0$ đến $2M$, đếm số cặp có thứ tự $(i,j)$ thắng.

Dữ liệu vào

• Dòng $1$: Hai số nguyên $N$ và $M$.
• $N$ dòng tiếp: Mỗi dòng gồm hai số nguyên $a_i$ và $b_i$.

Dữ liệu ra

In $2M+1$ dòng, dòng thứ $k$ (bắt đầu từ $0$) là số cặp thắng ứng với giá trị $k$ đó.

Ràng buộc

• $1\le N\le 2\times {10}^5$.
• $1\le M\le 5000$.
• $0\le a_i\le b_i\le M$.

Ví dụ