Vera and Canada Day

Time limit2sMemory limit512 MB

Summary

After each laser is added, choose one of four L-shaped firing orientations per laser so that the total awe from lasers hit by beams is maximized.

Level: Hard8 of 10
Topics: Dynamic programming, Graph, Sorting, Implementation
Solved: No attempts yet

Problem

Vera is preparing a laser show for Canada Day. She places $N$ lasers on the xy-plane one at a time, and laser $i$ goes to $(x_i, y_i)$ . No two lasers share a position.

Every laser fires two beams in perpendicular axis-aligned directions. The four possible orientations are up and left, left and down, down and right, right and up. When a beam hits laser $j$ , the show gains $v_j$ awe and the beam stops there, so one beam hits at most one laser, the closest one in the direction it was fired. Beams do not interfere with each other, so they may cross and two lasers may fire at each other. A laser can be hit by several beams, and every hit adds its awe value separately.

After Vera places laser $i$ , she wants the maximum total awe value over all orientations of the lasers placed so far. Each laser is oriented independently, and the orientations may be chosen again from scratch for every answer.

Input

The first line contains the integer $N$ ( $1 \le N \le 10^5$ ).

Each of the next $N$ lines contains the integers $x_i$ , $y_i$ , $v_i$ ( $-10^9 \le x_i, y_i \le 10^9$ , $1 \le v_i \le 10^4$ ). The lasers are placed in the order given in the input, and $(x_i, y_i) \ne (x_j, y_j)$ for $i \ne j$ .

Output

Print $N$ lines. Line $i$ contains one integer, the maximum total awe value after lasers $1$ through $i$ have been placed.

Examples6

Example 1

Input

Expected output

Example 2
Input
```
1
0 0 1
```
Expected output
```
0
```
Example 3
Input
```
2
0 0 7
5 0 3
```
Expected output
```
0
10
```
Example 4
Input
```
2
0 0 7
5 1 3
```
Expected output
```
0
0
```
Example 5
Input
```
3
0 0 100
10 0 100
5 0 1
```
Expected output
```
0
200
102
```

Example 6

Input

4
-1000000000 -1000000000 10000
1000000000 -1000000000 10000
-1000000000 1000000000 10000
1000000000 1000000000 10000

Expected output