题目描述

题目译自 CEOI 2020 Day1 T2「Roads」

Treeland 政府准备建立一个全新的道路网。Treeland 共有 $2N$ 个城市，目前已经修建了 $N$ 条道路，每条道路都是一条连接两个城市的线段。这 $N$ 条道路两两没有交点（包括端点处）。你现在需要再修建 $N-1$ 条道路，要求：

1. 每条道路都是一条连接两个城市的线段。
2. 道路只能在端点处相交。
3. 对于任意两个城市，均能通过该路网相互抵达。

输入格式

输入第一行包含一个整数 $N$。

接下来 $N$ 行，每行包含四个整数 $x_1,y_1,x_2,y_2$，表示 $(x_1,y_1)$ 和 $(x_2,y_2)$ 两座城市间存在一条道路直接相连。

输出格式

输出 $N-1$ 行。

每行包含四个整数 $x_1,y_1,x_2,y_2$，代表新修一条连接 $(x_1,y_1)$ 和 $(x_2,y_2)$ 两座城市间的道路。

如果存在多种方案，任意输出一种即可。

样例

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

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

下图中，实线表示已经修建的道路，虚线代表新修道路。

数据范围与提示

所有数据均满足：$2 \leq N \leq 10^5$，$-10^7 \leq x_1,y_1,x_2,y_2 \leq 10^7$。

各子任务的约束条件如下：