## Problem E: Gopher that walks and swims

A gopher lives in the flatlands of Northern Saskatchewan and
frequently visits his cousins living in the South-East part of the
same province. When going on a visit the gopher has to cross
a lot of ditches.
Saskatchewan has been suffering years of severe drought.
Recently, however, they experienced a period of
unusually heavy rains which resulted in flooding all the ditches on
the gopher's route.

The ditches run along straight lines in the
West-East or South-North direction and each ditch is of a constant
width. The gopher still wants to make his travels but being not a
very good swimmer, he wants to minimize the distance that he has to
swim across the ditches. With this requirement satisfied, he also
wants to walk as little as possible on the dry land. Your task is to
find the length of the gopher's route which minimizes his swimming and
then his walking.

We are given a system of orthogonal coordinates, where the *x* axis
is directed from West to East and the *y* axis is directed from South
to North. Given are positive real numbers: *D* and *L*,
*L+L* < *D*, such that
a point (*x*, *y*) is on dry land if and only if there exist
integers *m* and *n* such that

*m*D+L* <= *x* <= *(m+1)*D-L* and

*n*D+L* <= *y* <= *(n+1)*D-L*.
Given is the starting point of the gopher (*x*_{s},
y_{s}) and its target point (*x*_{t},
y_{t}). Both these points are on dry land and also

0 < *x*_{s} <= x_{t},

*y*_{s} >= y_{t} > 0,

*x*_{t}-x_{s} <= *y*_{s}-y_{t}.
It is also known that the gopher on his way to the target point will
not have to swim through more than 300 ditches.
Each line of
input contains six numbers: *D*, *L*, *x*_{s},
y_{s}, *x*_{t}, y_{t}. For each
line of input, output one line with the needed information in the
format shown in the sample output. The last line of input has the value
of *D* equal to zero and this line should not be processed.

### Sample input

100.0 10.0 50.0 150.0 150.0 50.0
100.0 10.0 50.0 250.0 150.0 50.0
10.0 1.0 5 95 45 5
10.0 1.0 5 95 35 5
10.0 1.0 1.01 95 39 8.99
0 0 0 0 0 0

### Output for sample input

The gopher has to swim 28.28 meters and walk 113.14 meters.
The gopher has to swim 48.28 meters and walk 183.06 meters.
The gopher has to swim 21.31 meters and walk 78.96 meters.
The gopher has to swim 20.49 meters and walk 75.89 meters.
The gopher has to swim 20.49 meters and walk 75.21 meters.

*Piotr Rudnicki*

ACPC 2006