비행접시 길 안내

흔히들 오해하지만, 외계인의 비행접시는 지구 위를 마음대로 날아다닐 수 없다. 착륙과 이륙 동작에 어마어마한 에너지가 들기 때문에, 모든 임무는 신중하게 계획된다. 비행접시는 미리 정한 한 지점에 착륙하고, 지면 위를 떠다니며 임무를 수행한 뒤 이륙한다. 인류 문명이 아직 어렸을 때는 이 일이 쉬웠다. 비행접시가 모든 나무와 건물 위를 떠다닐 수 있었으므로, 두 임무 지점 사이의 최단 경로는 대개 단순한 직선이었다. 그러나 현대 도시에는 그 위로 떠다닐 수 없을 만큼 높은 고층 건물이 있어, 도시를 이동하는 일이 복잡해졌다.

한 외계 첩자가 당신을 고용해, 비행접시에게 도시의 이동 경로를 알려 주는 소프트웨어를 만들게 했다. 첫 번째 임무로, 비행접시가 출발점에서 도착점까지 이동해야 하는 최단 거리를 구하여라. 외계인들은 이 값으로 임무에 필요한 에너지를 계획한다.

문제는 다음과 같이 단순화된다. 비행접시는 대부분의 건물 위를 떠다닐 수 있으므로, 고층 건물만 고려하면 된다. 상황은 2차원이다. 모든 것을 위에서 내려다본다고 보고, 모든 물체가 직교좌표 OXY 평면 위에 있다고 하자. 비행접시는 반지름이 $r$인 원이다. 현대의 고층 건물은 반듯하므로, 각 건물은 변이 OX축과 OY축에 평행한 축 정렬 직사각형으로 나타낸다.

비행접시의 위치는 그 중심의 위치이고, 이동 경로의 길이는 중심이 그리는 경로의 길이이다. 임무 동안 비행접시는 건물에 닿을 수는 있지만, 건물의 내부와 겹쳐서는 안 된다. 따라서 최단 경로는 직선 구간과, 건물의 모서리를 감싸는 반지름 $r$의 원호로 이루어진다.

첫째 줄에 두 정수 $r$과 $n$이 주어진다 ($1 \le r \le 100$, $0 \le n \le 30$). $r$은 비행접시의 반지름, $n$은 고층 건물의 개수이다.

둘째 줄에 네 정수 $x_A$, $y_A$, $x_B$, $y_B$가 주어진다 ($-1000 \le x_A, y_A, x_B, y_B \le 1000$). $(x_A, y_A)$는 임무의 출발점, $(x_B, y_B)$는 도착점이다.

다음 $n$개의 줄에 각 고층 건물이 네 정수 $x_1$, $y_1$, $x_2$, $y_2$로 주어진다 ($-1000 \le x_1, y_1, x_2, y_2 \le 1000$, $x_1 < x_2$, $y_1 < y_2$). 이는 직사각형에서 마주 보는 두 꼭짓점의 좌표이다.

어떤 두 고층 건물도 서로 겹치거나 닿지 않는다. 출발점과 도착점은 비행접시가 놓일 수 있는 올바른 위치이다. 즉 그 지점에서 비행접시는 어떤 건물과도 내부가 겹치지 않으며, 다만 닿을 수는 있다.

비행접시가 출발점에서 도착점에 도달할 수 없으면 no solution을 (따옴표 없이) 출력한다.

그렇지 않으면 한 개의 수, 즉 비행접시가 출발점에서 도착점까지 이동해야 하는 최단 거리를 출력한다. 소수점 아래 정확히 여섯 자리로 반올림하여 출력한다.