Tsp

MGG is a poor truckman. One day he is asked to deliver packages for customers. There are n customers, where each customer specifies a location to pick up his/her package, and a location to deliver the package. Customers are labeled from 1 to n. For customer i, we denote the pickup location as i+, and the delivery location as i-. To deliver package for customer i, Mo must visit i+ before visiting i-.

However, the truck Mo drives has only a rear door, so the truck works as a stack: the last picked up package must be delivered first. If there are two packages i and j in the truck, and i is picked up before j, then i cannot be delivered unless j is delivered.

Mo knows all the coordinates of pickup and delivery locations. However, due to the censorship of the Great Fire Wall, Mo cannot visit any location more than once. What's worse, there are additional restrictions:

- Mo can't go to location j+ from i+ if j > i;
- Mo can't go to location j- from i- if j < i;
- If Mo has visited location i-, location j+ will be removed from the world and cannot be visited any more if j < i.

Now Mo can choose any location to start. He wants to choose a shortest path to deliver packages for all the n customers. Please find the shortest path for him.

There are multiple test cases.
For each test case, the first line is an integer n, 0 < n <= 100.
Then n lines follow. There are 4 integers in each line. The integers in the i-th line indicate the x and y coordinates of i+, and the x and y coordinates of i-, respectively.

The distance between two locations is the Euclidean distance between them.

Input is terminated by end-of-file.

For each test case, output the path in a line.
It is guaranteed that there is a unique solution for each test case.

3
1 3 5 2
2 4 2 3
6 0 2 2
5
5 0 6 0
2 0 5 0
7 0 1 0
6 0 9 0
4 0 6 0

1+ 1- 3+ 2+ 2- 3-
2+ 1+ 1- 2- 3+ 3- 5+ 4+ 4- 5-

2013 ACM/ICPC Asia Regional Changchun Online