На нескінченному столі задано дві різні точки $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: Можна показати, що за оптимального розміщення паличок мураху можна повністю заблокувати.