Đề được tóm tắt bởi bạn Phan Thành Hưng.

Cho ~n~ khách hàng thuê máy chủ. Khách hàng thứ ~i~ bắt đầu thuê máy từ ngày ~x_i~, sử dụng trong ~d_i~ ngày và dung lượng cần dùng là ~k_i~.

Công ty đó tính tổng dung lượng của từng ngày một. Nếu ngày đó không có khách hàng thuê thì dung lượng là ~0~.

Công ty cần theo dõi sự biến động của lượng dung lượng trong từng ngày, kể từ ngày cho thuê đầu tiên (ngày có ~x_i~ nhỏ nhất), tới ngày cuối cùng mà máy chủ được sử dụng.

Viết chương trình thông báo biến động sử dụng. Nói cách khác, hãy in ra những lần mà dung lượng của công ty có sự thay đổi so với ngày hôm trước.

INPUT

Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 8 \times 10^5~) là số khách hàng.

~n~ dòng tiếp theo, mỗi dòng gồm ba số nguyên dương ~x_i~, ~d_i~ và ~k_i~ thể hiện một khách hàng (~1 \le x_i + d_i \le 10^5~, ~1 \le k_i \le 10^9~).

OUTPUT

Bảng biến động sử dụng của công ty đó.

SAMPLE INPUT 1

3
6 2 15
3 6 9
4 5 7

SAMPLE OUTPUT 1

9 16 31 16

Các ngày có thay đổi được bôi vàng.

SAMPLE INPUT 2

3
1 2 5
5 3 7
1 3 9

SAMPLE OUTPUT 2

14 9 0 7

Các ngày có thay đổi được bôi vàng.

SUBTASKS