Mức Phủ Trên Trục Số

Cho $n$ đoạn đóng có đầu mút nguyên. Với mỗi $k$ từ $1$ đến $n$, hãy đếm số tọa độ nguyên được đúng $k$ đoạn phủ.

Input

• Dòng đầu chứa số nguyên $n$.
• Mỗi trong $n$ dòng tiếp theo chứa hai số nguyên $l_i$ và $r_i$.

Output

• In $n$ số; số thứ $k$ là số tọa độ nguyên được đúng $k$ đoạn phủ.

Constraints

• $1\le n\le 2\cdot 10^5$.
• $0\le l_i\le r_i\le 10^{18}$.
• Các đoạn có thể trùng nhau, lồng nhau hoặc suy biến thành một điểm.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 10$ và $r_i\le 100$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

4
0 2
2 4
4 4
1 3

1 3 1 0