The government of Treeland wants to build a new road network. There are \(2N\) cities in Treeland. The unfinished plan of the road network already contains \(N\) road segments, each of which connects two cities with a straight line. No two road segments have a common point (including their endpoints). Your task is to determine \(N-1\) additional road segments satisfying the following conditions:
The first line of the standard input contains \(N\) (\({2 \leq N \leq 10^5}\)) – the number of existing road segments. Each of the following \(N\) lines contains four integers: \(x_1,y_1, x_2, y_2\), where \((x_1, y_1)\) and \((x_2, y_2)\) are the coordinates of the endpoints of the segment \((-10^7 \leq x_i,y_i\leq 10^7)\).
The standard output must contain \(N-1\) lines, each of them containing four integers, \(x_1, y_1, x_2, y_2\), where \((x_1,y_1)\) and \((x_2, y_2)\) are the coordinates of the cities that are the endpoints of a new road segment. If there are multiple solutions, your program may output any of them.
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
1500 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач