Một trò chơi có \(N\) người chơi. Người thứ \(i\) đăng nhập trong \(B_i\) ngày liên tiếp, bắt đầu từ ngày \(A_i\), tức là các ngày \(A_i,A_i+1,\ldots,A_i+B_i-1\). Ngoài những ngày đó, người này không đăng nhập.

Trò chơi đã hoạt động tới ngày \(10^{100}\). Với mỗi \(k=1,2,\ldots,N\), hãy đếm số ngày có đúng \(k\) người đăng nhập.

Dữ liệu vào

• Dòng đầu chứa \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(A_i,B_i\).

Dữ liệu ra

In \(N\) số nguyên \(D_1,D_2,\ldots,D_N\), trong đó \(D_k\) là số ngày có đúng \(k\) người đăng nhập.

Ràng buộc

• \(1\le N\le2\cdot10^5\).
• \(1\le A_i,B_i\le10^9\).
• Mọi giá trị đầu vào đều là số nguyên.

Ví dụ

3
1 2
2 3
3 1

2 2 0

2
1000000000 1000000000
1000000000 1000000000

0 1000000000

Nguồn

AtCoder Beginner Contest 221 — 😩 Online games.