Лазерний постріл
Ви — дроїд, і ваша мета — влучити в Джедая, який перебуває в кімнаті. Відомо, що Джедай може відбити лазер своїм світловим мечем, тому прямий постріл не спрацює. Однак, якщо ви вистрілите два лазери так, щоб вони вразили його одночасно з різних кутів, він не зможе відбити обидва. На щастя, стіни квадратної кімнати дзеркальні, що дозволяє відбивати лазерні постріли. Проте дзеркала не ідеальні, тому кожен лазер може відбитися лише обмежену кількість разів, перш ніж розсіється.
Як дроїд, ви маєте інші завдання, тому прагнете мінімізувати час між пострілами двох лазерів. У вас є два лазерні пістолети та дроїдні рефлекси, що дозволяють стріляти з будь-яким малим інтервалом (включаючи одночасно).
Кімната має розміри 1000000 футів з кожного боку. Її нижній лівий кут знаходиться в (0, 0), а верхній правий — в (1000000, 1000000). Ви перебуваєте в точці (x_1, y_1), а Джедай — в (x_2, y_2). Лазер, що відбивається і проходить через (x_1, y_1), продовжить свій шлях (ви ж запланували постріл, тому можете ухилитися), але зупиняється, як тільки потрапляє в (x_2, y_2). Лазер, випущений у стіну, дотримується звичайних правил відбиття (кут падіння дорівнює куту відбиття, і відбиття не додає затримки). Лазер, випущений прямо в кут, відбивається в протилежному напрямку і вважається, що він відбився двічі. Для простоти припустимо, що швидкість світла (і лазера) становить 1 фут за наносекунду.
Вхідні дані
Кожен тестовий випадок складається з одного рядка з 5 цілих чисел, розділених пробілами: x_1, y_1, x_2, y_2, n, де x_1, y_1, x_2, y_2 описані вище, а n — максимальна кількість відбиттів. 1 ≤ x_1, y_1, x_2, y_2 ≤ 999999, і 1 ≤ n ≤ 100. Гарантується, що дроїд і Джедай не знаходяться в одному місці, тобто (x_1, y_1) ≠ (x_2, y_2). Останній тестовий випадок супроводжується "0 0 0 0 0", який не слід обробляти.
Вихідні дані
Для кожного тестового випадку виведіть в одному рядку мінімальну затримку між пострілами лазерів у наносекундах, з точністю до 5 знаків після коми. Зверніть увагу, що тестові дані сконструйовані так, щоб жодна з відповідей не була в межах 1e-6 від межі округлення.
