단일 절단점

침입 범죄 예방 회사(Intrusion and Crime Prevention Company)는 가정과 사업장에 침입 탐지 시스템을 설치한다. 머리글자가 같은 국제 대학생 프로그래밍 대회(International Collegiate Programming Contest)는 내년 세계 대회 문제지를 보관할 방의 경비를 이 회사에 맡길지 검토하고 있다.

대회 운영진은 지난 몇 년 동안 있었던 침입 시도를 막으려 한다. 건물 외벽을 타고 내려와 창문으로 들어오기, 환기 덕트로 기어들어 오기, 대회 관계자를 사칭하기, 공격 잠수함을 창의적으로 활용하기 같은 시도였다. 그래서 문제지는 문이 하나뿐이고 다른 출구가 없는 방에 둔다.

회사는 문의 네 변에 센서를 달고 센서를 두 개씩 전선으로 잇는 방안을 제안한다. 전선은 문을 가로질러 직선으로 지나간다. 누군가 문을 열면 전선으로 이어진 센서 쌍이 이를 감지해 경보를 울린다.

이 설계에는 허점이 하나 있다. 침입자는 문을 열기 전에 전선을 자를 수 있다. 절단은 양 끝이 문의 경계 위에 있는 선분이고, 두 끝은 문의 서로 다른 변에 있어야 한다. 절단은 자신과 교차하는 전선을 모두 끊는다. 이 시스템이 얼마나 안전한지 재기 위해, 모든 전선을 끊는 절단의 최소 개수를 구하라.

문은 네 꼭짓점이 $(0, 0)$, $(w, 0)$, $(w, h)$, $(0, h)$인 직사각형이다.

그림 1은 두 예제의 전선 배치와 각 예제의 최소 크기 절단 집합을 그린 것이다. 그림 속 절단은 올바른 답 하나일 뿐, 이 문제가 요구하는 특정한 답은 아니다.

첫 줄에 정수 $n$, $w$, $h$가 주어진다. $n$은 전선의 개수이고($1 \le n \le 10^6$), $w$와 $h$는 문의 가로 길이와 세로 길이다($1 \le w, h \le 10^8$).

다음 $n$개의 줄에 각각 정수 $x_1$, $y_1$, $x_2$, $y_2$가 주어진다($0 \le x_1, x_2 \le w$, $0 \le y_1, y_2 \le h$). 이는 $(x_1, y_1)$에서 $(x_2, y_2)$까지 이어지는 전선을 뜻한다. 전선의 두 끝점은 문의 경계 위에 있으며 서로 다른 변에 있다. 끝점 가운데 문의 꼭짓점인 것은 없고, $2n$개의 끝점 위치는 모두 다르다.

첫 줄에 절단의 최소 개수를 출력한다. 이어서 절단을 한 줄에 하나씩, $(x_1, y_1)$에서 $(x_2, y_2)$까지의 절단을 뜻하는 네 수 $x_1$ $y_1$ $x_2$ $y_2$로 출력한다. 절단은 언제나 한 번이나 두 번이면 충분하므로 첫 줄은 1 또는 2다.

최소 크기의 절단 집합이 여럿일 수 있으므로 아래에 정한 하나를 출력한다. 경계 위의 점은 꼭짓점 $(0, 0)$에서 출발해 $(w, 0)$, $(w, h)$, $(0, h)$를 차례로 지나 다시 $(0, 0)$으로 돌아오는 방향으로 경계를 따라 걸은 거리로 나타낸다. 경계 전체의 길이는 $2(w + h)$이고, 모든 전선 끝점은 정수 거리에 놓인다. 출력하는 절단의 두 끝은 소수 부분이 정확히 $0.5$인 거리, 즉 반정수 거리에 놓아야 한다. 그런 점은 꼭짓점도 아니고 전선 끝점도 아니다.

절단 하나로 모든 전선을 끊을 수 있으면 1을 출력하고 그 절단을 출력한다. 두 끝의 거리 가운데 작은 값을 $p$, 큰 값을 $q$라고 하자. 두 끝이 반정수 거리에 있고 서로 다른 변에 있으며 모든 전선과 교차하는 절단 가운데 $p$가 가장 작은 것을 고르고, 그런 절단이 여럿이면 $q$가 가장 작은 것을 고른다. 거리가 $p$인 끝을 먼저 출력한다.

절단 하나로 모든 전선을 끊을 수 없으면 2를 출력하고 다음 두 절단을 이 순서로 출력한다. 먼저 $(0.5, 0)$에서 $(w - 0.5, h)$까지의 절단, 그다음 $(w, 0.5)$에서 $(0, h - 0.5)$까지의 절단이다.

좌표가 정수이면 정수로 출력하고, 그렇지 않으면 소수점 아래 한 자리까지 출력한다.