На бесконечном столе даны две различные точки $A = (A_x, A_y)$ и $B = (B_x, B_y)$.
У вас также есть $M$ палочек, каждая из которых представляет собой отрезок длины $W$. Вы можете размещать эти палочки где угодно на столе, в любом положении и под любым углом. Палочки могут перекрываться. Однако ни одна палочка не может содержать точку $A$ или точку $B$.
Муравей начинает движение из точки $A$ и хочет добраться до точки $B$. Он может ходить где угодно по столу, но не может пересекать ни одну палочку.
Вы хотите разместить палочки так, чтобы длина кратчайшего пути муравья из $A$ в $B$ была как можно больше.
Если можно полностью заблокировать муравья так, что пути из $A$ в $B$ не будет существовать, ответом является $-1$.
В противном случае пусть $L$ — точная верхняя грань (супремум)$^\dagger$ длин кратчайших путей из $A$ в $B$ по всем допустимым размещениям палочек. Если существует размещение, на котором достигается это значение, то $L$ — это просто максимум. Если ни одно конкретное размещение его не достигает, но размещения могут приближаться к нему сколь угодно близко, вы всё равно должны вывести $L$.
$^\dagger$ Точная верхняя грань (наименьшая верхняя граница) множества вещественных чисел — это наименьшее вещественное число, которое больше или равно каждому значению в множестве. Она может как достигаться, так и не достигаться на некотором элементе множества.
Входные данные
Входные данные даны в следующем формате:
T A_x A_y B_x B_y M W ...
- Все входные значения являются целыми числами.
- $1 \le T \le 10^4$
- $0 \le A_x, A_y, B_x, B_y \le 10^9$
- $1 \le M, W \le 10^9$
- Гарантируется, что $(A_x, A_y) \ne (B_x, B_y)$.
Выходные данные
Для каждого набора входных данных:
- Выведите $-1$, если муравья можно полностью заблокировать;
- В противном случае выведите одно вещественное число — определённое выше значение $L$.
Пусть $X$ — правильный ответ, а $Y$ — ваш вывод. Ваш вывод считается правильным тогда и только тогда, когда $|Y - X| \le 10^-6 \cdot \max(1, |X|)$.
Пример
Входные данные 1
2 0 0 1 1 343 434 4 5 786331192 707731892 1 639711202
Выходные данные 1
-1 1425074478.231629371643066
Примечание
Тестовый пример 1: Можно показать, что при оптимальном размещении палочек муравья можно полностью заблокировать.