6 de Pentagrame

„6 de Pentagrame semnifică ajutorul și generozitatea” așa cum și comisia lotului de informatică vă oferă cu generozitate oportunitatea de a câștiga 100 de puncte pe următoarea problemă.

Se dau $N$ puncte de coordonate întregi în plan, fiecare având o greutate. O partiționare a planului prin punctul de coordonate $(x, y)$ se definește ca fiind împărțirea planului în $4$ cadrane prin trasarea dreptei verticale de coordonată $x +0.5$ și a dreptei orizontale de coordonată $y + 0.5$. Greutatea unui cadran este suma greutăților punctelor aflate în acel cadran. Dezechilibrul unei anumite partiționări se definește ca fiind diferența maximă dintre greutatea a două cadrane.

Cerință

Pentru fiecare număr întreg $x$ intre $1$ și $N − 1$ să se afle dezechilibrul minim pentru oricare partiționare printr-un punct aflat pe linia verticală de coordonată $x$.

Date de intrare

Pe prima linie a intrării se găsește numărul $N$.

Fiecare din următoarele $N$ linii conține $3$ numere întregi $x_i, y_i$ și $w_i$, reprezentând coordonatele celui de al $i$-lea punct din plan, respectiv greutatea lui.

Date de ieșire

Ieșirea trebuie să conțină pe prima linie $N − 1$ numere, reprezentând dezechilibrele minime căutate.

Restricții și precizări

• $1 \leq N \leq 200 \ 000$
• $1 ≤ x_i, y_i ≤ N$ pentru $1 ≤ i ≤ N$
• $1 ≤ w_i ≤ 10^9$ pentru $1 ≤ i ≤ N$
• Punctele nu sunt neapărat distincte.

Exemple

stdin

4
3 2 5
4 4 2
1 4 4
2 2 1

stdout

6
4
6

Explicație

Prima verticală aflată la coordonata $x = 1.5$ desparte cele $4$ puncte în $2$ semiplane. În stânga verticalei se află punctul $(1, 4)$ iar în dreapta celelalte $3$. Dacă alegem orizontala la coordonata $y = 3.5$, obținem $4$ cadrane: cadranul stânga-sus care conține punctul $(1, 4)$ cu greutatea $4$, cadranul dreapta-sus care conține punctul $(4, 4)$ cu greutatea $2$, cadranul dreapta-jos cu punctele $(2, 2)$ și $(3, 2)$ cu greutatea totală $6$ și cadranul stânga-jos care nu conține niciun punct și are greutatea $0$. Dezechilibrul devine $6 − 0 = 0$.

Pentru $x = 2.5$, selectăm $y = 2.5$, astfel împărțind planul în $4$ cadrane, fiecare cadran conținând exact unul din cele $4$ puncte. Dezechilibrul este astfel $5 − 1 = 4$.