베라와 캐나다 데이

캐나다 데이를 맞아 베라가 레이저 쇼를 준비한다. 레이저 $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$번까지 놓은 뒤 얻을 수 있는 감동 수치 합의 최댓값을 정수 하나로 출력한다.