The Elusive Dimaquha

Time Limit: 1 Second    Memory Limit: 32768 KB

Every year, when the nights are at their longest, the menfolk of Baga set out at dawn to gather the elusive herb dimaquha for their midnight rites. Under the guidance of a seemingly erratic medicine man, they take with them the sacred platform mounted on runners (for none else may bear the elusive dimaquha), and for its sake they cut furrows through the plains and the woodlands as they wander at the medicine man's bidding.

Though seemingly erratic, their medicine man never fails, each year somehow finding the elusive herb . . . but cutting furrows is hard work, and the exhausted men of Baga would prefer to return using the tracks created by their initial wanderings.

Input

Input will consist of a series of Cartesian coordinates, delimited by a comma, one per line, that mark the initial path taken by the sacred platform. Each series of coordinates will consist of anywhere between 1 and 1,000 points, inclusive. As the file may contain more than one set of coordinates, the end of each set will be marked by a line containing a single period. Input will be terminated by an empty set - that is, two consecutive lines each containing a single period. Each coordinate will have at most 2 decimal places and, if necessary, will have a leading zero. The range of the coordinates is from -32,768 to 32,767 inclusive.

Output

The output for each set should be a series of Cartesian coordinates, one per line, that mark the shortest path from the last point to the first point. Note that this return path may contain points that are not present in the input set - one day is not enough to fill in the marks of their wanderings, and the men folk of Baga may create new intersections when two of their furrows cross. Should one such intersection provide a shorter route home, the men folk of Baga will not hesitate to use it to guide back the sacred platform.

All values should be truncated to two decimal places. The end of each set should be followed by a line containing a single period.

Sample Input

0, 0
.
0.25, -1
1, 15
.
0, 0
15, 0
10, 0
10, -5
5, -5
5, 5
.
.

Sample Output

0.00, 0.00
.
1.00, 15.00
0.25, -1.00
.
5.00, 5.00
5.00, 0.00
0.00, 0.00
.

Submit

Source: Asia 2003, Manila (Philippine)