장애물 경기

평면 위에 있는 점의 위치는 좌표로 나타내면 다루기 쉽다. 그림 1에서 기준점(이를 원점이라 부른다)으로부터 오른쪽으로 거리가 4, 위로 거리가 3만큼 떨어진 빨간 점의 좌표는 $(4, 3)$이다. 같은 방식으로 원점에서 오른쪽으로 $x$, 위로 $y$만큼 떨어진 점의 좌표는 $(x, y)$이고, 원점의 좌표는 $(0, 0)$이다.

그림 1

장애물이 설치된 넓은 들판에서 달리기 시합이 열린다. 들판 곳곳에는 수직 방향(남북 방향)으로 세워진 담장 모양의 장애물이 있다. 선수는 출발지점에서 동쪽으로 달리기 시작하고, 장애물을 만나면 남쪽이나 북쪽으로 달려 장애물을 피해야 한다. 장애물 끝에 다다르면 선수는 다시 동쪽으로만 달릴 수 있다.

이 달리기의 목표는 결승선으로 정해진 무한히 긴 수직선까지 가장 짧은 거리를 달려 도달하는 것이다. 달리기를 시작하기 전에 모든 장애물의 정보가 선수에게 주어진다. 즉, 어떤 크기의 장애물이 어느 위치에 놓여 있는지를 선수가 알고 있고, 선수는 장애물을 피하면서 가장 짧은 거리를 달려 결승선에 도착해야 한다.

출발지점과 각 장애물 양 끝점의 위치는 $(x, y)$ 좌표로 나타낸다. 모든 좌표 값은 정수이고, 출발지점의 $x$ 좌표는 $0$이다. 장애물은 수직선분이어서 양 끝점의 $x$ 좌표가 같으므로, 장애물 하나의 정보는 세 값 $[x, y_l, y_h]$ ($y_l < y_h$)로 나타낼 수 있다. 이 세 값은 장애물이 설치된 $x$ 좌표와 양 끝점의 $y$ 좌표다.

$x$ 좌표가 같은 두 장애물이 겹치거나 한 점에서 만나는 경우는 없다.

동쪽으로 달리던 선수가 장애물의 끝점을 만나면 방향을 바꾸지 않고 계속 동쪽으로 달린다.

그림 2의 예를 보자. 출발지점이 $(0, 43)$, 결승선의 $x$ 좌표가 $70$이고, 네 장애물의 정보가 각각 $[20, 30, 50]$, $[30, 10, 38]$, $[45, 35, 55]$, $[55, 50, 70]$이다. 점선으로 표시한 최단 경로는 다음과 같다.

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

이때 총 이동거리는 $87$이고, 도착지점의 $y$ 좌표는 $50$이다.

그림 2

그림 3의 예에는 서로 다른 최단경로가 다음과 같이 네 개 있다.

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)$

그림 3

이 가운데 두 번째 경로와 세 번째 경로는 달리는 길이 다르지만 도착지점이 같다.

출발지점의 $y$ 좌표, 결승선의 $x$ 좌표, $N$개의 장애물 정보가 주어질 때 이동 규칙을 따르는 최단경로를 모두 찾은 후, 도착지점이 서로 다른 최단경로의 도착지점 $y$ 좌표를 오름차순으로 차례로 출력하는 프로그램을 작성하시오.

표준 입력으로 다음 정보가 주어진다. 첫째 줄에 장애물의 개수를 나타내는 정수 $N$이 주어진다 ($1 \le N \le 100{,}000$). 둘째 줄에 출발지점의 $y$ 좌표와 결승선의 $x$ 좌표를 나타내는 두 정수가 차례로 주어진다. 이어지는 $N$개의 줄에는 장애물 하나의 정보를 나타내는 세 정수 $x$, $y_l$, $y_h$ ($y_l < y_h$)가 차례로 주어진다. 문제에 나오는 모든 좌표 $(x, y)$는 $0 \le x \le 1{,}000{,}000$과 $0 \le y \le 2{,}000{,}000$을 만족한다. 모든 장애물의 $x$ 좌표는 $0$보다 크고 결승선의 $x$ 좌표보다 작다.

표준 출력으로 첫째 줄에 최단경로의 길이를 출력한다. 둘째 줄에는 최단경로들의 서로 다른 도착지점의 개수 $k$를 출력하고, 이어서 $k$개의 도착지점의 $y$ 좌표를 오름차순으로 차례로 출력한다.