Su un tavolo infinito ti vengono dati due punti distinti $A = (A_x, A_y)$ e $B = (B_x, B_y)$.
Hai anche $M$ bastoncini, ciascuno dei quali è un segmento di lunghezza $W$. Puoi posizionare questi bastoncini ovunque sul tavolo, con qualsiasi posizione e orientamento. I bastoncini possono sovrapporsi. Tuttavia, nessun bastoncino può contenere il punto $A$ o il punto $B$.
Una formica parte da $A$ e vuole raggiungere $B$. Può camminare ovunque sul tavolo, ma non può attraversare alcun bastoncino.
Vuoi posizionare i bastoncini in modo che la lunghezza del percorso più breve per la formica da $A$ a $B$ sia la più grande possibile.
Se è possibile bloccare completamente la formica in modo che non esista alcun percorso da $A$ a $B$, la risposta è $-1$.
Altrimenti, sia $L$ l'estremo superiore (supremum)$^\dagger$ delle lunghezze dei percorsi più brevi da $A$ a $B$ su tutte le disposizioni valide dei bastoncini. Se esiste una disposizione che raggiunge questo valore, $L$ è semplicemente il massimo. Se nessuna singola disposizione lo raggiunge, ma le disposizioni possono avvicinarsi arbitrariamente ad esso, devi comunque stampare $L$.
$^\dagger$ L'estremo superiore (minimo dei maggioranti) di un insieme di numeri reali è il più piccolo numero reale che è maggiore o uguale a ogni valore nell'insieme. Può essere raggiunto o meno da un valore nell'insieme.
Input
L'input è fornito nel seguente formato:
T A_x A_y B_x B_y M W ...
- Tutti i valori di input sono numeri interi.
- $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$
- È garantito che $(A_x, A_y) \ne (B_x, B_y)$.
Output
Per ogni caso di test:
- Stampa $-1$ se la formica può essere bloccata completamente;
- Altrimenti, stampa un singolo numero reale — il valore $L$ definito sopra.
Sia $X$ la risposta corretta e $Y$ il tuo output. Il tuo output è considerato corretto se e solo se $|Y - X| \le 10^-6 \cdot \max(1, |X|)$.
Esempio
Input 1
2 0 0 1 1 343 434 4 5 786331192 707731892 1 639711202
Output 1
-1 1425074478.231629371643066
Note
Caso di test 1: Si può dimostrare che posizionando i bastoncini in modo ottimale, la formica può essere bloccata completamente.