Существует известный математический факт: если положить карту парка полностью внутрь самого парка, то найдется точка на карте, которая совпадает с точкой, которую она представляет.
Мио очень нравится этот факт, поэтому она кладет карту своего любимого парка полностью внутрь этого парка. Парк $P$ можно представить в виде прямоугольника. Карта парка — это просто уменьшенная (или равная) версия парка, напечатанная на бумаге. Карта подобна исходному прямоугольнику. Каждая точка на карте соответствует точке в парке посредством преобразования подобия.
Мы можем формально определить карту: карта — это прямоугольник $M$ (меньшего или равного размера) вместе с положительным вещественным числом $r$ и биективной функцией $f : M \to P$, удовлетворяющей условию: * Для любой пары различных точек $a, b \in M$, $|f(a) - f(b)| / |a - b| = r$.
$|x - y|$ обозначает евклидово расстояние между точками $x$ и $y$.
Как и во многих играх, Мио может телепортироваться, используя карту. Точнее, когда Мио находится в некоторой точке $x$ на карте (включая границу), она может телепортироваться в соответствующую точку $f(x)$ в парке. Она также может выбрать не телепортироваться. Обратное также верно. Когда она находится в точке $y$ в парке (включая границу), она может телепортироваться в точку $f^{-1}(y)$ на карте, представляющую её текущее местоположение. И она также может выбрать не телепортироваться.
Мио может телепортироваться не более $n$ раз (и не менее 0). Каждая телепортация занимает $k$ секунд. Мио также может ходить пешком со скоростью 1 единица в секунду.
Даны две точки $s$ и $t$, найдите минимальное время, необходимое Мио, чтобы добраться из $s$ в $t$.
Каждая телепортация может быть совершена в любом направлении (с карты в парк или из парка на карту). Карта может быть расположена вверх ногами. Поскольку карта находится внутри парка, возможно, что Мио находится на карте и в парке одновременно. В этом случае она может телепортироваться в любом направлении.
Например, на следующем рисунке парк — это $ABCD$, а карта — $A'B'C'D'$. Когда Мио находится внутри карты, она одновременно находится на карте и в парке. Когда она находится в точке $D'$, она может телепортироваться с карты в парк (попав в $D$), и из парка на карту (попав в $D'$).
На рисунке парк — это ABCD, а карта — A'B'C'D'.
Входные данные
Первая строка содержит единственное целое число $T$ ($1 \le T \le 100$), обозначающее количество тестовых случаев.
Для каждого тестового случая первая строка содержит 4 вершины прямоугольника, представляющего парк. Вершины даны в порядке по часовой стрелке или против часовой стрелки. Гарантируется, что 4 вершины различны.
Вторая строка содержит 4 вершины прямоугольника, представляющего карту. $i$-я вершина карты соответствует $i$-й вершине парка для всех $1 \le i \le 4$. Заметьте, что вы можете определить, перевернута ли карта, по порядку вершин. Вершины даны в порядке по часовой стрелке или против часовой стрелки. Гарантируется, что карта находится внутри парка. (Граница карты может пересекаться с границей парка в одной или нескольких точках.) Гарантируется, что карта корректна, т.е. существует положительное вещественное число и биективная функция из карты в парк, удовлетворяющая приведенному выше определению.
Третья строка содержит две точки $s$ и $t$. Гарантируется, что $s$ и $t$ находятся внутри (или на границе) парка.
Четвертая строка содержит два целых числа $k, n$ ($0 \le k \le 2 \times 10^6$, $0 \le n \le 100$), время, необходимое для каждой телепортации, и максимальное количество телепортаций.
Каждая точка во входных данных представлена парой целых чисел, абсолютные значения которых не превышают $2 \times 10^6$. Целые числа разделены пробелами.
Выходные данные
Для каждого тестового случая выведите одно число, представляющее ответ, в одной строке. Ваш ответ считается верным, если его абсолютная или относительная погрешность не превышает $10^{-9}$.
Примеры
Входные данные 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
Выходные данные 1
1.0000000000 1.2272623352