2 From My Canoe to You

After winning several Olympic gold medals for rowing, Marnie has gone into business delivering parcels on a lake in cottage country. To save herself time, Marnie uses a canoe (unlike a rowing shell, it's big enough to fit all her cargo), faces in the direction of travel, and manages to go from customer to customer using only left turns (the shape of the lake makes it possible).

Marnie knows that the real money is in franchising, so she's hired you to write a program to find left-only routes for her franchisees who work on similarly shaped lakes.

Input Each run of your program will handle the problem for a single lake. The data are specified as follows:

• A positive integer n indicating the number of customers on the lake; n at least 3
• n pairs of integers, each specifying the x and y coordinates, in that order, of a customer (x increases as you go east, y increases as you go north). All customer locations are distinct. One of the pairs will be the origin, 0 0.

There will be at most 1000 customers on a lake. No coordinate will have absolute value greater than 10000. Whitespace separates integers, so two consecutive vertices may appear on the same line, or a newline may separate the x and y coordinates of a vertex, etcetera. Output: Output the coordinates of customers in an order so that only left turns are made from one customer to the next, and the return trip from the last customer to the home base is a left turn as well. There will always be such an order; in particular, no three customers lie on the same straight line. The franchisee's base counts as a customer site and always has coordinates 0 0; it should be listed first and only once.

Sample input:

5
0 0 
 2 1 
0    1
1 2
2 0

Corresponding sample output:

0 0
2 0
2 1
1 2
0 1