Description

The government of Treeland plans to build a brand-new road network. Treeland has a total of $2N$ cities. Currently, $N$ roads have already been built, and each road is a line segment connecting two cities. These $N$ roads do not intersect each other in pairs (including at endpoints). You now need to build another $N-1$ roads, such that:

1. Each road is a line segment connecting two cities.
2. Roads may intersect only at endpoints.
3. For any two cities, it must be possible to travel between them using this road network.

Input Format

The first line contains an integer $N$.

The next $N$ lines each contain four integers $x_1, y_1, x_2, y_2$, indicating that there is a road directly connecting the two cities at $(x_1, y_1)$ and $(x_2, y_2)$.

Output Format

Output $N-1$ lines.

Each line contains four integers $x_1, y_1, x_2, y_2$, representing a newly built road connecting the two cities at $(x_1, y_1)$ and $(x_2, y_2)$.

If there are multiple solutions, output any one.

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

Hint

Sample Explanation

In the figure below, solid lines are roads that have already been built, and dashed lines are new roads.

Subtasks

All testdata satisfy: $2 \leq N \leq 10^5$, $-10^7 \leq x_1, y_1, x_2, y_2 \leq 10^7$.

The constraints for each subtask are as follows:

Note that the actual scoring distribution in the judge is different from the agreement above.

Translated by ChatGPT 5