404144: GYM101431 C Vera and Canada Day

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Vera and Canada Daytime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

For Canada Day, Vera is going to create a spectacular laser show. She will place N lasers one at a time onto an xy-plane. The i-th laser will be placed at (xi, yi) and Vera will not place two lasers at the same location. Each laser will shoot two beams of light in axis-aligned perpendicular directions (up-left, left-down, down-right or right-up). If a beam hits another laser j, the show will gain awe value vj, and the beam will stop. Thus a beam can hit at most one laser, the closest one in the direction the beam is shot. Beams do not interfere with each other, so they can cross or two lasers can shoot at each other. A laser can be hit by multiple beams and each hit will gain awe value.

After Vera places the i-th laser (1 ≤ i ≤ N), she wants to know the maximum sum of awe value over all possible rotations of already placed lasers.

Input

Line 1 contains integer N (1 ≤ N ≤ 105).

N lines follow, the i-th one contains integers xi, yi, and vi ( - 109 ≤ xi, yi ≤ 109, (xi, yi) ≠ (xj, yj) if i ≠ j, 1 ≤ vi ≤ 104).

Output

Print N lines. The i-th line should contain one integer, the maximum sum of awe value after placing lasers 1 to i.

ExampleInput
6
0 0 5
0 2 10
3 0 4
0 1 8
-1 0 5
4 4 100
Output
0
15
24
35
41
41

加入题单

上一题 下一题 算法标签: