Billiard Table

Time limit1sMemory limit128 MB

Summary

A billiard ball must bounce off the table cushions exactly N times before reaching a target point; find the minimum travel distance, with corners counting as two bounces.

Level: Hard8 of 10
Topics: Geometry, Math, Brute force, Implementation
Solved: No attempts yet

Problem

A white ball and a red ball are placed on a rectangular billiard table. Before the white ball hits the red ball, it must hit the cushions (the four edges of the table) exactly $N$ times. Among all such paths, find the minimum distance that the white ball travels.

At every cushion the angle of incidence equals the angle of reflection.
The diameter of a ball is negligible (treat each ball as a point).
One corner of the table is the origin, and all four edges are parallel to the $x$ -axis or the $y$ -axis.
If the ball hits a corner (vertex) of the table, it counts as hitting a cushion $2$ times.
The total number of cushion hits before striking the red ball must be exactly $N$ .

Input

The input consists of several test cases. Each test case is a single line of seven space-separated integers.

L W CX CY TX TY N

$L$ and $W$ are the width and height of the table ( $2 \le L, W \le 100$ ).
$(CX, CY)$ is the position of the white ball and $(TX, TY)$ is the position of the red ball ( $0 < CX, TX < L$ , $0 < CY, TY < W$ ).
The two balls occupy distinct positions, i.e. $(CX, CY) \ne (TX, TY)$ .
$N$ is the number of cushions that must be hit before striking the red ball ( $0 \le N \le 100$ ).

The last line contains seven zeros and must not be processed.

Output

For each test case, print on its own line the minimum distance the white ball travels. Round the value to three decimal places (rounding at the fourth decimal place).

Examples2

Example 1

Input

20 15 10 1 12 1 1
10 20 1 2 7 16 2
0 0 0 0 0 0 0

Expected output

2.828
19.698

Example 2
Input
```
10 10 2 2 8 8 0
0 0 0 0 0 0 0
```
Expected output
```
8.485
```