Skiing

Kleofáš failed to qualify for the IOI, so he decided to become a slalom skier instead. Tomorrow is the day of his first skiing contest.

In the contest Kleofáš has to get from a start point to a finish point while passing through $n$ gates. To be as fast as possible, he wants the shortest possible trajectory.

A skiing course consists of a start point $S$, a finish point $F$ and $n$ gates. Every gate is a line segment parallel to the $x$ axis, so every gate is horizontal. No two gates share the same $y$ coordinate (altitude). The start point is above every gate, so its $y$ coordinate is larger than the $y$ coordinate of any gate. The finish point is below every gate and below the start point.

Find the shortest polygonal chain that starts at $S$, finishes at $F$ and intersects all gates in order from top to bottom. A polygonal chain intersects a line segment when the two have at least one common point, and that point may be an endpoint of the segment.

The first line contains one integer $n$ ($0 \le n \le 10^6$), the number of gates. The second line contains four integers $x_S, y_S, x_F, y_F$, the coordinates of $S = (x_S, y_S)$ and $F = (x_F, y_F)$.

Each of the next $n$ lines contains three integers $x_{1i}, x_{2i}, y_i$, meaning that the $i$-th gate is the segment from $(x_{1i}, y_i)$ to $(x_{2i}, y_i)$. For every $i$, $x_{1i} < x_{2i}$ holds.

All coordinates are between $-10^9$ and $10^9$, inclusive. The gates are given from top to bottom, so $y_S > y_1 > y_2 > \dots > y_n > y_F$.

The shortest polygonal chain always exists, it is unique, and all of its vertices have integer coordinates. Print this chain without any redundant vertices, that is, print only the vertices where the chain changes its direction.

On the first line print one integer $k$, the number of vertices of the optimal chain. Then print $k$ more lines, the $i$-th of them containing two space separated integers $x_i, y_i$, the coordinates of the $i$-th vertex of the chain. Print the vertices from the start of the chain to its end, so $x_1 = x_S$, $y_1 = y_S$, $x_k = x_F$, $y_k = y_F$ and $y_1 > y_2 > \dots > y_k$ must hold.

The picture below shows the course of the first example together with its optimal chain.