Reorganizing Bus Routes

Seogang operates $N$ bus routes along a straight road. Because routes were added whenever the need arose, many of them overlap or duplicate each other. To help citizens tired of the complicated bus network, the government decided to reorganize the routes.

Each bus route is described by three integers $S$, $E$, and $C$, meaning that it covers the interval $[S,E]$ with fare $C$. If the intervals of two bus routes share at least one point, the two intervals are replaced by a single new route covering their union. The fare of the new route is the lower of the two fares. The reorganization continues until no two routes have overlapping intervals.

Figure D.1: Bus routes before and after reorganization

Given the information about the bus routes, write a program that outputs the routes after the reorganization finishes.

The first line contains the number of bus routes $N$. ($1 \le N \le 200\,000$)

The next $N$ lines each contain three integers $S$, $E$, and $C$ describing one bus route. ($0 \le S < E \le 10^9$, $1 \le C \le 10^9$)

Print $K$, the number of bus routes after the reorganization, on the first line.

On the next $K$ lines, print $S$, $E$, and $C$ for each route after the reorganization, in increasing order of $S$.