Trên một trục số, ta có \(n\) đoạn thẳng \(L_{1},\ldots,L_{n}\); đoạn thẳng \(L_{i}\) bắt đầu tại vị trí \(A_{i}\) và có độ dài \(T_{i}\) (tức là đoạn \(L_{i}\) kết thúc tại vị trí \(A_{i} + T_{i}\)).

Ta gọi đoạn thẳng \(L_{p}\) là con của đoạn thẳng \(L_{q}\) (ký hiệu là \(L_{p} \subset L_{q}\)) nếu \(\left\{ \begin{matrix} A_{p} \geq A_{q} \\ A_{p} + T_{p} \leq A_{q} + \ T_{q} \end{matrix} \right.\ \)

Với mỗi dãy \(L_{i}\): hãy tìm dãy dài nhất \(L_{i},L_{h_{1}},\ldots,L_{h_{k}}\) thỏa mãn \(L_{i} \subset L_{h_{1}} \subset \ldots \subset L_{h_{k}}\); trong đó \(L_{i},L_{h_{1}},\ldots,L_{h_{k}}\) là các đoạn thẳng trong \(n\) đoạn thẳng đã cho.

Dữ liệu vào:

+ Dòng đầu tiên chứa số nguyên dương \(n\).

+ Dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa 2 số nguyên \(A_{i}\) và \(T_{i}\), mô tả đoạn \(L_{i}\) có độ dài \(T_{i}\) bắt đầu từ vị trí \(A_{i}\).

+ Không tồn tại 2 đoạn thẳng giống nhau.

Kết quả:

+ Gồm \(n\) số, số thứ \(i\) là số lượng đoạn thẳng trong dãy dài nhất \(L_{i},L_{h_{1}},\ldots,L_{h_{k}}\) thỏa mãn \(L_{i} \subset L_{h_{1}} \subset \ldots \subset L_{h_{k}}\), không bao gồm đoạn \(L_{i}\). Hai số kề nhau được phân tách bởi một khoảng trắng.

Ràng buộc:

• \(1 \leq n \leq 2 \times 10^{5}\).

• \(1 \leq A_{i},T_{i} \leq 10^{9}\).

Ví dụ:

Ràng buộc:

• Có 30% điểm tương ứng với \(n \leq 100\).

• Có 20% điểm tương ứng với \(100 \leq n \leq 10^{4}\).

• Có 50% điểm tương ứng với \(10^{4} \leq n \leq 2 \times 10^{5}\).