Trên một trục số, ta có ~n~ đoạn thẳng ~L_1, \dots, 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:

• ~A_p \ge A_q~;

• ~A_p + T_p \le A_q + T_q~.

Với mỗi dãy ~L_i~: hãy tìm dãy dài nhất ~L_i, L_{h_1}, \dots, L_{h_k}~ thỏa mãn ~L_i \subset L_{h_1} \subset \dots \subset L_{h_k}~; trong đó ~L_i, L_{h_1}, \dots, L_{h_k}~ là các đoạn thẳng trong ~n~ đoạn thẳng đã cho.

Input

• 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;

• ~1 \le n \le 2 \cdot 10^5~;

• ~1 \le A_i, T_i \le 10^9~.

Output

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}, \dots, L_{h_k}~ thỏa mãn ~L_i \subset L_{h_1} \subset \dots \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.

Scoring

Sample Input 1

5
2 5
3 3
2 2
4 2
4 1

Sample Output 1

0 1 1 2 3