题目描述

译自 ROI 2013 Day2 T4. Флешмоб

为奥林匹克参赛者准备了一场在 U 市主广场上举行的快闪游戏。主广场铺满了瓷砖，形成了一个网格状的场地。

游戏首先制定计划：每位快闪参与者会获得一个进入广场的顺序编号以及两块不同瓷砖的坐标，这两块瓷砖位于同一行或同一列。随后，奖品被放置在广场上，参与者按顺序进入广场。每位参与者会拿走指定两块瓷砖以及它们之间所有瓷砖上的奖品。

奖品必须放置在确保每位参与者至少能获得一个奖品的位置上。

你需要编写一个程序，根据游戏计划，计算所需的最小奖品数量以及奖品应放置的具体瓷砖位置。

输入格式

输入文件的第一行包含一个整数 $N$ $(1 \leq N \leq 123456)$，表示快闪参与者的数量。

接下来的 $N$ 行，每行包含四个整数 $x_{1i}, y_{1i}, x_{2i}, y_{2i}$，表示第 $i$ 位参与者的两块瓷砖坐标（$1 \leq x_{1i}, y_{1i}, x_{2i}, y_{2i} \leq 10^{9}$；且满足 $x_{1i}=x_{2i}$ 或 $y_{1i}=y_{2i}$）。参与者按进入广场的顺序排列。

输出格式

输出文件的第一行应包含一个整数 $M$，表示需要在广场上放置的最小奖品数量。

接下来的 $M$ 行，每行包含两个整数 $px_i$ 和 $py_i$，表示第 $i$ 个奖品应放置的瓷砖坐标。

如果存在多个满足条件的奖品放置方案，可以输出任意一种。如果不存在解决方案，则输出唯一的数字 $0$。

5
2 1 2 4
2 4 4 4
5 1 1 1
4 4 4 2
4 2 1 2

5
1 2
4 3
1 1
3 4
2 3

3
1 1 1 3
2 1 2 3
1 2 2 2

0

4
1 1 1 3
2 1 2 3
3 3 3 1
1 3 4 3

4
4 3
3 1
2 1
1 1

数据范围与提示

详细子任务附加限制及分值如下表所示：