Để kiểm thử tính ổn định của trang web NBKOJ, ban quản trị đã mời \(N\) người dùng đăng nhập vào tài khoản của bản thân trong một khoảng thời gian nhất định. Cụ thể, người dùng thứ \(i\) sẽ đăng nhập vào giây thứ \(L_i\) và đăng xuất sau thời điểm đó \(D_i\) giây. Tất cả \(N\) người dùng đều làm theo kế hoạch này với thái độ hợp tác và thiện chí.

Với mỗi giá trị nguyên dương \(k\) từ \(1\) đến \(N\), bạn hãy giúp ban quản trị NBKOJ thống kê xem có bao nhiêu giây trong đợt kiểm thử mà tồn tại đúng \(k\) người đang đăng nhập vào hệ thống nhé!

Input

• Dòng đầu chứa số nguyên \(N\) \(\left(1\leq N\leq 2\times 10^5\right)\).
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa hai số nguyên dương \(L_i\) và \(D_i\). Các giá trị đều không vượt quá \(10^9\).

Output

• In ra một dòng gồm \(N\) số nguyên, số thứ \(k\) thể hiện số lượng giây có đúng \(k\) người đang đăng nhập vào hệ thống.

Ví dụ

Sample input 01

3
1 2
2 3
3 1

Sample output 01

2 2 0

Sample input 02

3
1 2905
1 2905
1 2905

Sample output 02

0 0 2905