Obstacle Course Run

Coordinates are a convenient way to name a point in the plane. In Figure 1 the red point lies at distance 4 to the right of the reference point (called the origin) and distance 3 above it, so its coordinates are $(4, 3)$. In the same way, the point at distance $x$ to the right of the origin and distance $y$ above it has coordinates $(x, y)$, and the origin itself is $(0, 0)$.

Figure 1

A running race is held on a wide field with obstacles on it. Fence shaped obstacles stand here and there across the field, each one running in the vertical direction (north to south). The runner starts at the starting point and runs east. On meeting an obstacle the runner must run south or north to get around it. Once the runner reaches an end of the obstacle, the runner can only run east again.

The goal of the race is to reach the finish line, an infinitely long vertical line, over the shortest distance. Every obstacle is described to the runner before the race starts. The runner knows the size and the position of each obstacle and has to reach the finish line by the shortest run that avoids them.

The starting point and the two ends of each obstacle are written as $(x, y)$ coordinates. Every coordinate value is an integer, and the $x$ coordinate of the starting point is $0$. An obstacle is a vertical segment, so its two ends share one $x$ coordinate and a single obstacle is described by three values $[x, y_l, y_h]$ ($y_l < y_h$). These three values are the $x$ coordinate where the obstacle stands and the $y$ coordinates of its two ends.

No two obstacles with the same $x$ coordinate overlap or meet at a point.

A runner heading east who meets an end point of an obstacle keeps running east.

Look at the example in Figure 2. The starting point is $(0, 43)$, the $x$ coordinate of the finish line is $70$, and the four obstacles are $[20, 30, 50]$, $[30, 10, 38]$, $[45, 35, 55]$ and $[55, 50, 70]$. The shortest route, drawn as a dotted line, is

$(0, 43) \to (20, 43) \to (20, 50) \to (45, 50) \to (45, 55) \to (55, 55) \to (55, 50) \to (70, 50)$

Its total length is $87$, and the $y$ coordinate of the arrival point is $50$.

Figure 2

The example in Figure 3 has four different shortest routes.

1. $(0, 40) \to (20, 40) \to (20, 50) \to (35, 50) \to (35, 60) \to (70, 60)$
2. $(0, 40) \to (20, 40) \to (20, 50) \to (35, 50) \to (35, 40) \to (70, 40)$
3. $(0, 40) \to (20, 40) \to (20, 30) \to (50, 30) \to (50, 40) \to (70, 40)$
4. $(0, 40) \to (20, 40) \to (20, 30) \to (50, 30) \to (50, 20) \to (70, 20)$

Figure 3

The second route and the third route run along different paths, yet they arrive at the same point.

Given the $y$ coordinate of the starting point, the $x$ coordinate of the finish line and the description of $N$ obstacles, find every shortest route that follows the movement rules, then print the $y$ coordinates of the distinct arrival points in ascending order.

Standard input carries the following. The first line has one integer $N$, the number of obstacles ($1 \le N \le 100{,}000$). The second line has two integers, the $y$ coordinate of the starting point and the $x$ coordinate of the finish line, in that order. Each of the next $N$ lines has three integers $x$, $y_l$ and $y_h$ ($y_l < y_h$) describing one obstacle, in that order. Every coordinate $(x, y)$ used in the problem satisfies $0 \le x \le 1{,}000{,}000$ and $0 \le y \le 2{,}000{,}000$. The $x$ coordinate of every obstacle is greater than $0$ and smaller than the $x$ coordinate of the finish line.

On the first line of standard output print the length of a shortest route. On the second line print $k$, the number of distinct arrival points of the shortest routes, followed by the $y$ coordinates of those $k$ arrival points in ascending order.