Các cô bò đang cố gắng sáng tạo những trò chơi mới thú vị. Một dự án hiện tại sử dụng tập hợp $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 $b_i \geq a_i$. Cả $a_i$ và $b_i$ là số nguyên trong khoảng $0 \ldots M$, với $1 \leq M \leq 5000$.

Để chơi, Bessie chọn một đoạn (chẳng hạn đoạn thứ $i$) và chị/em họ Elsie chọn một đoạn (chẳng hạn đoạn thứ $j$, có thể giống đoạn của Bessie). Với giá trị $k$ cho trước, họ 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.

Dữ liệu vào

Dòng đầu 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 $2M+1$ dòng, một dòng cho mỗi giá trị $k$ trong khoảng $0 \ldots 2M$.

Ví dụ

Dữ liệu vào 1

2 5
1 3
2 5

Dữ liệu ra 1

0
0
1
3
4
4
4
3
3
1
1

Ghi chú

Trong ví dụ này, riêng với $k=3$, có ba cặp có thứ tự giúp Bessie và Elie thắng: $(1, 1)$, $(1, 2)$ và $(2, 1)$.

Nhiệm vụ con

• Các bộ kiểm thử 1-2 thỏa mãn $N\le 100, M\le 100$.

• Các bộ kiểm thử 3-5 thỏa mãn $N\le 5000$.

• Các bộ kiểm thử 6-20 không có giới hạn bổ sung.

Giá trị đầu ra có thể quá lớn để chứa trong số nguyên 32 bit, nên bạn có thể muốn dùng số nguyên 64 bit (ví dụ số nguyên "long long" trong C hoặc C++).

Tác giả bài toán: Benjamin Qi