스키 활강

클레오파시는 IOI 대표 선발에서 떨어진 뒤 회전 스키 선수가 되기로 했다. 내일은 클레오파시가 처음으로 스키 대회에 나가는 날이다.

대회에서 클레오파시는 출발점에서 도착점까지 내려가면서 기문 $n$개를 모두 통과해야 한다. 최대한 빨리 내려가려면 이동 경로가 가장 짧아야 한다.

활강 코스는 출발점 $S$, 도착점 $F$, 기문 $n$개로 이루어진다. 기문은 모두 $x$축과 평행한 선분, 즉 수평 선분이다. $y$좌표(고도)가 같은 기문은 없다. 출발점은 모든 기문보다 위에 있어서 그 $y$좌표는 어떤 기문의 $y$좌표보다도 크다. 도착점은 모든 기문보다 아래에 있고, 출발점보다도 아래에 있다.

$S$에서 시작해 $F$에서 끝나고 모든 기문을 위에서 아래 순서대로 만나는 가장 짧은 꺾은선을 구하여라. 꺾은선과 선분이 공통점을 하나라도 가지면 둘이 만난다고 하고, 이 공통점이 선분의 끝점이어도 된다.

첫째 줄에 기문의 개수 $n$ ($0 \le n \le 10^6$)이 주어진다. 둘째 줄에 네 정수 $x_S, y_S, x_F, y_F$가 주어진다. 이는 각각 $S = (x_S, y_S)$와 $F = (x_F, y_F)$의 좌표이다.

다음 $n$개 줄에는 세 정수 $x_{1i}, x_{2i}, y_i$가 주어진다. $i$번째 기문은 $(x_{1i}, y_i)$에서 $(x_{2i}, y_i)$까지의 선분이며, 모든 $i$에 대해 $x_{1i} < x_{2i}$이다.

모든 좌표는 $-10^9$ 이상 $10^9$ 이하이다. 기문은 위에서 아래 순서로 주어지므로 $y_S > y_1 > y_2 > \dots > y_n > y_F$이다.

가장 짧은 꺾은선은 항상 유일하고, 그 꼭짓점의 좌표는 모두 정수임이 증명되어 있다. 이 꺾은선을 불필요한 꼭짓점 없이 출력한다. 즉 꺾은선의 방향이 바뀌는 꼭짓점만 출력한다.

첫째 줄에 최적 꺾은선의 꼭짓점 개수 $k$를 출력한다. 이어서 $k$개 줄에 $i$번째 꼭짓점의 좌표 $x_i$와 $y_i$를 공백으로 구분해 출력한다. 꼭짓점은 꺾은선의 시작부터 끝까지 차례로 출력해야 하므로 $x_1 = x_S$, $y_1 = y_S$, $x_k = x_F$, $y_k = y_F$이고 $y_1 > y_2 > \dots > y_k$를 만족해야 한다.

아래 그림은 첫 번째 예제의 코스와 그 최적 꺾은선이다.