题目描述

ICPC 公司为家庭和公司提供入侵检测系统，而国际大学生程序设计竞赛正在考虑租用该公司的服务来加固下一年 World Final 的存放题面的房间。

比赛的工作人员希望阻止历年发生的入侵尝试，比如用绳索从建筑物外部的窗户进入、沿通气管爬入、冒充 Bill Poucher（注：现 ICPC 执行主席），以及创造性地利用攻击性潜艇（smg）。因此，该房间将会只有一个门，且没有其它出口。

ICPC 公司准备在门的四条边上安装感应器，每对感应器之间用电线连接。如果有人打开了门，则相连的感应器会发现问题并发出警报声。

但这个系统有一个设计缺陷。攻击者可以在开门前切断电线。为了评估该系统的安全性，你需要计算切割所有电线所需要的最少线段数。如图为两种不同的在门上放置电线的方式，以及切割所有电线所需要的切割数最少的方案。

输入格式

第一行有三个整数 $n,w,h$，分别表示电线的数量 $(1 \le n \le 10^6)$，以及门的大小 $(1 \le w,h \le 10^8)$。

接下来 $n$ 行，每行代表一根电线。每行含有四个整数 $x1,y1,x2,y2 (0 \le x1,x2 \le w,0 \le y1,y2 \le h)$，表示有一根电线从 $(x1,y1)$ 连向 $(x2,y2)$。每根电线连接门的两个不同边框。没有一根电线的端点为门的四个角落之一。输入的所有端点各不相同。

输出格式

输出一个最小的切割方案与所有的电线相交。首先输出最少需要的切割数量。接下来输出切割，每行应有四个数 $x1\ y1\ x2\ y2$ 表示 $(x1,y1)$ 与 $(x2,y2)$ 之间的切割。每条切割线的两端必须在门的不同边框上。切割线端点与任一角落或电线端点的距离不能小于 $10^{-6}$。

切割可以以任意顺序输出。每个切割的起点和终点可以交换。如果有多组切割方案达到最小切割，输出任意一种。

4 4 6
0 1 4 4
0 5 2 0
0 3 3 6
2 6 4 2

1
0 4 4 3

5 4 6
0 2 2 0
0 3 2 6
1 6 3 0
1 0 4 4
3 6 4 2

2
0 4 4 4.5
0 1 4 1

数据范围与提示

在不侵犯原题版权的情况下，本题面中文翻译基于知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议发布，注明出处时需指向本题链接。