Istnieje znany fakt matematyczny, który mówi, że jeśli położysz mapę parku całkowicie wewnątrz tego parku, to istnieje punkt na mapie, który pokrywa się z punktem, który reprezentuje.
Mio bardzo lubi ten fakt, więc kładzie mapę swojego ulubionego parku całkowicie wewnątrz parku. Park $P$ można przedstawić jako prostokąt. Mapa parku jest po prostu mniejszą (lub równą) wersją parku wydrukowaną na papierze. Mapa jest podobna do oryginalnego prostokąta. Każdy punkt na mapie odpowiada punktowi w parku poprzez przekształcenie podobieństwa.
Możemy formalnie zdefiniować mapę: Mapa to prostokąt $M$ (o mniejszym lub równym rozmiarze) wraz z dodatnią liczbą rzeczywistą $r$ oraz bijektywną funkcją $f : M \to P$ spełniającą warunek:
- Dla każdej pary różnych punktów $a, b \in M$, $|f(a) - f(b)| / |a - b| = r$.
$|x - y|$ oznacza odległość euklidesową między punktami $x$ oraz $y$.
Jak w wielu grach, Mio może teleportować się za pomocą mapy. Dokładniej, gdy Mio znajduje się w pewnym punkcie $x$ na mapie (wliczając brzeg), może teleportować się do odpowiadającego mu punktu $f(x)$ w parku. Może również zdecydować się nie teleportować. Odwrotność również jest prawdziwa. Gdy znajduje się w punkcie $y$ w parku (wliczając brzeg), może teleportować się do punktu $f^{-1}(y)$ na mapie, reprezentującego jej aktualną lokalizację. Może również zdecydować się nie teleportować.
Mio może wykonać co najwyżej $n$ (i co najmniej 0) teleportacji. Każda teleportacja zajmuje $k$ sekund. Mio może również poruszać się pieszo z prędkością 1 jednostki na sekundę.
Mając dane dwa punkty $s$ oraz $t$, znajdź minimalny czas, jakiego Mio potrzebuje, aby dotrzeć z $s$ do $t$.
Każda teleportacja może odbyć się w dowolnym kierunku (z mapy do parku lub z parku do mapy). Mapa może być położona do góry nogami. Ponieważ mapa znajduje się wewnątrz parku, możliwe jest, że Mio znajduje się jednocześnie na mapie i w parku. W takim przypadku może teleportować się w dowolnym kierunku.
Na przykład na poniższym rysunku park to $ABCD$, a mapa to $A'B'C'D'$. Kiedy Mio znajduje się wewnątrz mapy, jest jednocześnie na mapie i w parku. Kiedy znajduje się w punkcie $D'$, może teleportować się z mapy do parku (docierając do $D$) oraz z parku do mapy (docierając do $D'$).
Na rysunku park to ABCD, a mapa to A'B'C'D'.
Wejście
Pierwsza linia zawiera pojedynczą liczbę całkowitą $T$ ($1 \le T \le 100$) oznaczającą liczbę zestawów danych.
Dla każdego zestawu danych pierwsza linia zawiera 4 wierzchołki prostokąta reprezentującego park. Wierzchołki podane są w kolejności zgodnej lub przeciwnej do ruchu wskazówek zegara. Gwarantuje się, że 4 wierzchołki są różne.
Druga linia zawiera 4 wierzchołki prostokąta reprezentującego mapę. $i$-ty wierzchołek mapy odpowiada $i$-temu wierzchołkowi parku dla wszystkich $1 \le i \le 4$. Zauważ, że możesz określić, czy mapa jest położona do góry nogami, na podstawie kolejności wierzchołków. Wierzchołki podane są w kolejności zgodnej lub przeciwnej do ruchu wskazówek zegara. Gwarantuje się, że mapa znajduje się wewnątrz parku. (Brzeg mapy może przecinać brzeg parku w jednym lub więcej punktach). Gwarantuje się, że mapa jest poprawna, tzn. istnieje dodatnia liczba rzeczywista i funkcja bijektywna z mapy do parku spełniająca powyższą definicję.
Trzecia linia zawiera dwa punkty $s$ oraz $t$. Gwarantuje się, że $s$ oraz $t$ znajdują się wewnątrz (lub na brzegu) parku.
Czwarta linia zawiera dwie liczby całkowite $k, n$ ($0 \le k \le 2 \times 10^6$, $0 \le n \le 100$), czas potrzebny na każdą teleportację oraz maksymalną liczbę teleportacji.
Każdy punkt w wejściu jest reprezentowany przez parę liczb całkowitych, których wartości bezwzględne nie przekraczają $2 \times 10^6$. Liczby całkowite są oddzielone pojedynczymi spacjami.
Wyjście
Dla każdego zestawu danych wypisz w jednej linii liczbę reprezentującą odpowiedź. Twoja odpowiedź jest uważana za poprawną, jeśli jej błąd bezwzględny lub względny nie przekracza $10^{-9}$.
Przykład
Wejście 1
2 0 0 0 2 4 2 4 0 0 0 0 1 2 1 2 0 2 1 4 2 1 1 0 0 3 6 3 6 0 0 1 1 0 3 2 2 3 0 0 4 2 0 3
Wyjście 1
1.0000000000 1.2272623352