Parklife

그림 1. 구름 낀 날의 갑천과 엑스포 다리

갑천은 대전의 연구단지인 대덕이노폴리스를 관통하며 흐르는 하천이다. 대덕이노폴리스에는 KAIST, 엑스포 과학공원, 국립중앙과학관 등이 있다. 갑천 물가는 레저와 휴식을 위한 공원으로 쓰인다.

이 문제에서는 갑천을 약간 굽은 호(arc)로 모델링한다. 호 위에는 1cm 간격으로 정확히 $10^6$개의 점이 표시되어 있다. 갑천에는 $N$개의 다리가 있다. 각 다리는 호 위의 서로 다른 두 점을 잇는 직선 선분이다. 선분은 다른 선분과 끝점에서만 닿을 수 있고, 그 밖의 경우에는 교차하지 않는다. 두 점의 쌍마다 두 점을 직접 잇는 다리는 최대 하나다.

그림 2. $x, y, z$는 교차하지 않고 끝점에서만 서로 닿는 다리다. 가능한 입력의 예이다. 번호 $8 \ldots 10^6$의 점은 생략했다.

그림 3. $x, y$는 서로 교차하는 다리다. 가능한 입력이 아니다. 번호 $8 \ldots 10^6$의 점은 생략했다.

시의회는 밤에 갑천을 더 즐거운 곳으로 만들려고 일부 다리에 조명을 설치할 계획이다. 시의회는 다리마다 조명을 달았을 때의 미적 가치를 계산했다. 이 값은 양의 정수로 나타낼 수 있다.

그러나 조명이 너무 많으면 한밤중에 주민들이 불편을 겪는다. 이를 막기 위해 시의회는 규칙을 정했다. 인접한 두 점 사이의 모든 호에서, 그 호에서 보이는 조명 달린 다리는 최대 $k$개여야 한다. 인접한 두 점 $i$, $i+1$을 잇는 호에서 선분이 보인다는 것은, 선분의 한 끝점 번호가 $i$ 이하이고 다른 끝점 번호가 $i+1$ 이상인 경우를 뜻한다.

시의회는 빛 공해와 야경 사이의 균형을 맞추고자 한다. 모든 정수 $1 \le k \le N$에 대해 미적 가치 합의 최댓값을 구하라.

첫 줄에 정수 $N$이 주어진다. ($1 \le N \le 250\,000$)

다음 $N$개의 줄에는 세 정수 $S_i, E_i, V_i$가 주어진다. 이는 점 $S_i$와 $E_i$를 잇는 직선 다리가 있고, 그 미적 가치가 $V_i$라는 뜻이다. ($1 \le S_i < E_i \le 10^6, 1 \le V_i \le 10^9$)

같은 두 점을 잇는 다리는 없고, 서로 다른 두 선분은 교차하지 않는다고 보장된다.

$N$개의 정수를 공백으로 구분하여 출력한다. $i$번째 정수는 $k = i$일 때의 답이다.

그림 4. 첫 번째 입력의 도해.

그림 1 저작권 표기: 사진제공(한국관광공사 김지호)-한국관광공사