Tivoli

The image shows the first sample case and one optimal solution.

Lisa has arrived at the amusement park and has chosen $N$ attractions to ride. Each attraction has two identical facilities, so there are $2N$ facilities in total. She rides each attraction exactly once. Given the positions of all facilities, choose which $N$ facilities to visit and the order in which to visit them so that the total distance Lisa walks is as short as possible. She starts at the entrance and must return there. The entrance is at the origin.

The first line contains an integer $N$ ($1 \le N \le 15$), the number of attractions. The next $N$ lines describe attractions $1$ to $N$ in order. Each line contains four integers: the x and y coordinates of the first facility, followed by the x and y coordinates of the second facility. The absolute value of every coordinate is less than one million.

No facility is at the same position as another facility, and no facility is at the origin.

The first line contains the distance Lisa walks as a real number. Then print $N$ lines, each with two integers. The first integer is the attraction number ($1$ to $N$) that Lisa visits, and the second is the facility number ($1$ or $2$) she uses for it.

If several routes give the same shortest distance, print any of them. Reversing a route gives the same distance, so there are always at least two valid answers. The relative or absolute error must be less than $10^{-5}$.