Công ty VinasatX cho thuê máy chủ, hiện đang có ~N~ khách hàng. Khách hàng thứ ~i~ có nhu cầu sẽ đăng ký các thông tin gồm: ngày bắt đầu thuê ~(x_i)~, số ngày sử dụng ~(d_i)~ và dung lượng cần dùng ~(k_i)~.

Nhằm chuẩn bị cho việc đầu tư cơ sở hạ tầng, công ty cần đánh giá quá trình biến động về dung lượng cho thuê trong suốt quá trình hoạt động. Ngày công ty bắt đầu chạy máy chủ được xem là ngày ~1~, các ngày tiếp theo được ghi nhận lần lượt là ngày ~2~, ngày ~3~, ...

Để đánh giá biến động về dung lượng máy chủ cần cung cấp, công ty sẽ tính tổng dung lượng của tất cả khách thuê theo từng ngày. Những ngày không có khách thuê thì dung lượng cần dùng được xem là ~0~.

Công ty cần lập bảng theo dõi quá trình biến động này từ ngày bắt đầu cho thuê (~x_i~ nhỏ nhất) cho đến ngày cuối cùng máy chủ được khách hàng sử dụng.

Yêu cầu

Viết chương trình thông báo biến động dung lượng trong quá trình hoạt động.

Dữ liệu đầu vào

Gồm ~N + 1~ dòng:

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \le N \le 8 \times 10^5)~.
• ~N~ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương ~x_i, d_i, k_i~ ~(x_i + d_i \le 10^5, 1 \le k_i \le 10^9)~, mỗi số cách nhau một khoảng trắng.

Dữ liệu đầu ra

Gồm một dòng duy nhất là dãy số cho biết quá trình biến động về dung lượng theo yêu cầu trên, mỗi số cách nhau một khoảng trắng.

Ràng buộc dữ liệu

• 40% số điểm: ~1 \le N \le 10^2, 1 \le x_i + d_i \le 10^2~.
• 30% số điểm: ~1 \le N \le 2 \times 10^4~.
• 30% số điểm: ~1 \le N \le 8 \times 10^5~.

Ví dụ

Ví dụ 1

INPUT

3
6 2 15
3 6 9
4 5 7

OUTPUT

9 16 31 16

Giải thích:

Ví dụ 2

INPUT

3
1 2 5
5 3 7
1 3 9

OUTPUT

14 9 0 7