Công ty có ~N~ khách hàng thuê máy chủ. Khách hàng thứ ~i~ bắt đầu thuê từ ngày ~x_i~, thuê trong ~d_i~ ngày và dùng ~k_i~ đơn vị dung lượng.

Với mỗi ngày từ ngày thuê sớm nhất đến ngày kết thúc muộn nhất, xét tổng dung lượng đang được dùng. Hãy in ra dãy các giá trị mỗi khi tổng dung lượng thay đổi so với ngày trước đó.

Input

Dòng đầu chứa ~N~ ~(1 \le N \le 8 \cdot 10^5)~.

~N~ dòng tiếp theo, mỗi dòng chứa ~x_i, d_i, k_i~ ~(1 \le x_i, d_i \le 10^5, 1 \le k_i \le 10^9)~.

Output

In ra các giá trị dung lượng tại những thời điểm có biến động, cách nhau bởi dấu cách.

Subtask

• 40% s? ?i?m: ~N \le 100~ v? ~x_i+d_i \le 100~.
• 30% s? ?i?m: ~N \le 2 \cdot 10^4~.
• 30% s? ?i?m: ~N \le 8 \cdot 10^5~, ~1 \le x_i,d_i \le 10^5~, ~1 \le k_i \le 10^9~.