Laser Shot

You are a droid trying to hit a Jedi standing inside a mirrored, square room. A Jedi can block a single laser with his lightsaber, so a direct shot is useless. Instead you fire two lasers so that they reach the Jedi at the same instant from two different directions — he cannot block both at once.

The walls are mirrors, so a laser can bounce off them, but the mirrors are imperfect: each laser can bounce at most $n$ times before it dissipates. You carry two laser pistols and have droid reflexes, so you may fire the two shots with an arbitrarily small gap between them (including firing both simultaneously). Because the lasers travel at a fixed speed, making them arrive together means the delay between the two shots equals the difference between the two path lengths; your goal is to make that delay as small as possible.

The room is a square $1{,}000{,}000$ feet on each side, with its lower-left corner at $(0, 0)$ and its upper-right corner at $(1{,}000{,}000, 1{,}000{,}000)$. You are at $(x_1, y_1)$ and the Jedi is at $(x_2, y_2)$. A laser that bounces around and later passes back through your position $(x_1, y_1)$ keeps going (you planned the shot and can dodge it), but a laser stops immediately the first time it reaches the Jedi at $(x_2, y_2)$. Reflections obey the usual rule — angle of incidence equals angle of reflection — and add no delay. A laser aimed exactly at a corner rebounds straight back along the direction it came from and counts as having bounced twice. The laser travels at $1$ foot per nanosecond.

Two shots that arrive along the same final direction count as a single angle (the Jedi could block them together), so the two lasers must reach him along different final directions.

The input contains several test cases. Each test case is a single line with five space-separated integers $x_1$, $y_1$, $x_2$, $y_2$, $n$, where $(x_1, y_1)$ is your position, $(x_2, y_2)$ is the Jedi's position, and $n$ is the maximum number of bounces. The constraints are $1 \le x_1, y_1, x_2, y_2 \le 999{,}999$ and $1 \le n \le 100$, and the droid and the Jedi are never at the same location, i.e. $(x_1, y_1) \ne (x_2, y_2)$. The line $0\ 0\ 0\ 0\ 0$ marks the end of the input and must not be processed.

For each test case, print on its own line the minimum possible delay, in nanoseconds, between firing the two lasers, rounded to exactly $5$ decimal places. The test data guarantee that no answer lies within $10^{-6}$ of a rounding boundary.