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.
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).
Print N lines. The i-th line should contain one integer, the maximum sum of awe value after placing lasers 1 to i.
6
0 0 5
0 2 10
3 0 4
0 1 8
-1 0 5
4 4 100
0
15
24
35
41
41
