Một tập đoàn thuê ~n~ bác lao công dọn dẹp tòa nhà trụ sở để đón tiếp một đối tác lớn. Các bác lao công được đánh số từ 1 tới ~n~. Tùy theo tính chất công việc, bác lao công thứ 𝑖 sẽ làm việc trong khoảng thời gian ~[a_i; b_i]~ và nhận khoản tiền là ~w_i~ ngay khi bắt đầu công việc.

Tập đoàn cho phép một bác lao công ~i~ khi nhận tiền có thể nhận hộ những người khác có thời gian lao động nằm hoàn toàn trong khoảng thời gian lao động bác ~i~. Cụ thể là bác lao công ~i~ có thể nhận hộ tiền cho bác lao công ~j~ nếu:

~[a_i; b_i] ⊇ [a_j; b_j]⟺ a_i \le a_j < b_j≤ \le b_i~

Ví dụ một bác lao công làm việc trong khoảng thời gian [0; 9] có thể nhận hộ tiền cho các bác lao công làm việc trong khoảng thời gian [0; 2];[4; 6] hoặc [7; 9].

Yêu cầu: Với mỗi ~i~ = 1,2, … , 𝑛, hãy tính ~c_i~ là tổng số tiền bác lao công ~i~ sẽ nhận nếu bác ấy tới nhận tiền của mình và nhận hộ tất cả những người khác có thời gian lao động nằm hoàn toàn trong khoảng thời gian lao động của bác ~i~.

Input

Dòng 1 chứa số nguyên dương ~n ≤ 2 ∗ 10^5~

~n~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~a_i, b_i, w_i~ (~0 ≤ a_i < b_i ≤ 10^9; 1 ≤ w_i ≤ 10^9~)

Output

Ghi ra ~n~ số nguyên trên một dòng, số thứ ~i~ là ~c_i~

Test mẫu

Input

8
0 9 1
1 8 2
2 6 3
0 2 4
5 9 5
2 3 6
4 6 7
7 9 8

Output

36 18 16 4 13 6 7 8

Subtasks

~30\%~ số điểm ứng với các test có ~n ≤ 5000~

~30\%~ số điểm ứng với các test có ~𝑛 ≤ 20000~

~40\%~ số điểm ứng với các test không có ràng buộc bổ sung ngoài các ràng buộc đã nêu trong đề