시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB415410.526%

문제

Лондон --- очень старинный город. По ходу истории город разрастался, и в нем появлялись новые дороги. Сейчас дороги в Лондоне бывают двух типов: кольцевые и радиальные. Количество кольцевых дорог равно $k$. Пронумеруем их от $1$ до $k$, тогда $i$-я кольцевая дорога представляет собой квадрат со сторонами параллельными осям координат, и с противоположными углами в точках $(-i, -i)$ и $(i, i)$. Любая радиальная дорога является отрезком и соединяет две кольцевые дороги с номерами, отличающимися ровно на $1$, или кольцевую дорогу с номером $1$ и точку $(0, 0)$. При этом, она не имеет других общих точек с кольцевыми дорогами, кроме своих концов. Никакие две радиальные дороги не пересекаются, но могут иметь общие концы.

Паддингтон хочет добраться из точки $a$ с координатами $(x_a, y_a)$ в точку $b$ с координатами $(x_b, y_b)$, перемещаясь только по дорогам. Найдите минимальное расстояние, которое ему придется преодолеть.

Смотрите пояснение к тестам из примера для лучшего понимания условия.

입력

В первой строке дано два целых числа $n$ и $k$ --- количество радиальных дорог и количество кольцевых дорог ($0 \le n \le 10^5$, $1 \le k \le 10^9$). В следующих $n$ строках дано по $4$ целых числа $x_{i1}$, $y_{i1}$, $x_{i2}$ и $y_{i2}$ --- координаты начала и конца $i$-й радиальной дороги ($-k \le x_{i1}, y_{i1}, x_{i2}, y_{i2} \le k$). В последней строке дано четыре целых числа $x_a$, $y_a$, $x_b$, $y_b$ --- координаты точек $a$ и $b$, соответственно ($-10^9 \le x_a, y_a, x_b, y_b \le 10^9$).

Гарантируется, что дороги удовлетворяют ограничениям, описанным в условии.

출력

Выведите одно вещественное число с абсолютной или относительной погрешностью не более $10^{-6}$ --- кратчайшее расстояние из точки $a$ до точки $b$. Или $-1$, если пути не существует.

예제 입력 1

1 1
0 0 1 1
-1 -1 0 0

예제 출력 1

5.414213562373095

예제 입력 2

5 3
1 0 2 2
2 1 3 2
-1 1 0 2
-1 -2 0 -1
-3 -1 -2 -1
-3 -1 3 2

예제 출력 2

10.414213562373096

예제 입력 3

5 3
0 0 1 1
3 -3 2 -2
2 0 1 0
0 -1 0 0
-2 0 -3 0
1 3 0 0

예제 출력 3

14.828427124746192

노트

Рис. 1: Пояснение для первого теста

Рис. 2: Пояснение для второго теста

Рис. 3: Пояснение для третьего теста