题目描述

为参赛者在城市"U"的中心广场计划举办一场快闪形式的游戏。中心广场铺有地砖，形成一个网格状场地。

首先制定游戏计划：每个快闪活动参与者获得一个出场顺序编号和广场上两个不同地砖的坐标，这两个地砖位于同一行或同一列。之后在广场上放置奖品，然后参与者按顺序出场。当前参与者拾取指定给他的两个单元格及其之间所有单元格中的所有奖品。

奖品必须被放置得使每个参与者至少获得一个奖品。

需要编写一个程序，根据游戏计划找出所需的最小奖品数量，以及应该将这些奖品放置在哪些地砖上。

输入格式

输入文件的第一行包含数字 $N$——快闪活动的参与者数量（$1 \le N \le 123,456$）。

随后的 $N$ 行每行包含四个整数 $x_{1i}$, $y_{1i}$, $x_{2i}$, $y_{2i}$——第 $i$ 个参与者的地砖坐标（$1 \le x_{1i}, y_{1i}, x_{2i}, y_{2i} \le 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

提示

评分

本题包含三个子任务。每个子任务的评分使用独立的测试组。 前两个子任务的得分仅当通过该组所有测试时才会被计入。 第三个子任务的每个测试独立评分。

子任务 1

$N \le 123$。所有坐标不超过 $234$。 该子任务分值为 21 分。

子任务 2

$N \le 2543$。 该子任务分值为 23 分。

子任务 3

$N \le 123,456$。 该子任务分值为 56 分。