베라와 캐나다 데이

시간 제한2초메모리 제한512 MB

요약

레이저를 하나씩 추가할 때마다 각 레이저의 네 가지 직각 발사 방향 중 하나를 골라, 피격된 레이저의 awe 값 합이 최대가 되도록 한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 그래프, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

캐나다 데이를 맞아 베라가 레이저 쇼를 준비한다. 레이저 $N$ 개를 xy 평면 위에 하나씩 놓을 예정이고, $i$ 번째 레이저는 $(x_i, y_i)$ 에 놓는다. 두 레이저를 같은 위치에 놓는 일은 없다.

레이저는 축에 평행하고 서로 수직인 두 방향으로 빛을 쏜다. 가능한 방향 조합은 위와 왼쪽, 왼쪽과 아래, 아래와 오른쪽, 오른쪽과 위, 이렇게 네 가지다. 빛이 $j$ 번 레이저에 닿으면 쇼의 감동 수치가 $v_j$ 만큼 늘어나고 빛은 거기서 멈춘다. 따라서 빛 하나가 맞히는 레이저는 그 방향에서 가장 가까운 하나뿐이다. 빛끼리는 간섭하지 않아서 서로 교차해도 되고, 두 레이저가 서로를 향해 쏘아도 된다. 한 레이저가 여러 빛에 맞을 수 있고, 맞을 때마다 감동 수치가 따로 더해진다.

베라는 $i$ 번째 레이저를 놓을 때마다, 지금까지 놓은 레이저 $i$ 개의 방향을 자유롭게 정했을 때 얻는 감동 수치 합의 최댓값을 알고 싶다. 방향은 레이저마다 따로 정하고, 답을 구할 때마다 처음부터 다시 정해도 된다.

입력

첫째 줄에 정수 $N$ 이 주어진다. ( $1 \le N \le 10^5$ )

다음 $N$ 개 줄 중 $i$ 번째 줄에는 정수 $x_i$ , $y_i$ , $v_i$ 가 주어진다. ( $-10^9 \le x_i, y_i \le 10^9$ , $1 \le v_i \le 10^4$ ) 레이저는 입력에 주어진 순서대로 놓이고, $i \ne j$ 이면 $(x_i, y_i) \ne (x_j, y_j)$ 이다.

출력

$N$ 개 줄을 출력한다. $i$ 번째 줄에는 레이저 $1$ 번부터 $i$ 번까지 놓은 뒤 얻을 수 있는 감동 수치 합의 최댓값을 정수 하나로 출력한다.

예제6

예제 1

입력

예상 출력

예제 2
입력
```
1
0 0 1
```
예상 출력
```
0
```
예제 3
입력
```
2
0 0 7
5 0 3
```
예상 출력
```
0
10
```
예제 4
입력
```
2
0 0 7
5 1 3
```
예상 출력
```
0
0
```
예제 5
입력
```
3
0 0 100
10 0 100
5 0 1
```
예상 출력
```
0
200
102
```

예제 6

입력

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

예상 출력