Driving Directions

Contrary to popular belief, alien flying saucers cannot fly arbitrarily around planet Earth. Their landing and take-off maneuvers consume enormous amounts of energy, so every mission is planned carefully: the saucer touches down at one chosen spot, hovers above the ground to carry out its work, then takes off. This was easy when human civilization was young — a saucer could hover above every tree and building, and the shortest path between two mission points was simply a straight line. Modern cities, however, have skyscrapers too tall to hover over, so navigating a city has become a complex task.

An alien spy has hired you to write software that gives flying saucers driving directions through a city. As your first assignment, compute the shortest distance a saucer must travel from a start point to a finish point. The aliens will use this to plan the energy budget of a mission.

The problem is simplified as follows. Because a saucer can hover above most buildings, only the skyscrapers matter. The situation is two-dimensional: view everything from above and treat all objects as lying on the Cartesian OXY plane. The saucer is a circle of radius $r$. Because modern skyscrapers are regular, each skyscraper is an axis-aligned rectangle whose sides are parallel to the OX and OY axes.

The saucer's location is the location of its center, and the length of its path is the length of the path traced by its center. During a mission the saucer may touch a skyscraper but must never overlap its interior. A shortest path therefore consists of straight segments together with circular arcs of radius $r$ that hug the corners of the skyscrapers.

The first line contains two integers $r$ and $n$ ($1 \le r \le 100$, $0 \le n \le 30$), where $r$ is the radius of the flying saucer and $n$ is the number of skyscrapers.

The second line contains four integers $x_A$, $y_A$, $x_B$, and $y_B$ ($-1000 \le x_A, y_A, x_B, y_B \le 1000$), where $(x_A, y_A)$ is the start point of the mission and $(x_B, y_B)$ is the finish point.

Each of the next $n$ lines describes one skyscraper with four integers $x_1$, $y_1$, $x_2$, and $y_2$ ($-1000 \le x_1, y_1, x_2, y_2 \le 1000$, $x_1 < x_2$, $y_1 < y_2$) — the coordinates of two opposite corners of the rectangle.

No two skyscrapers intersect or touch. The start and finish points are valid saucer locations: at each of them the saucer does not overlap any skyscraper, although it may touch one.

If the flying saucer cannot reach the finish point from the start point, print no solution (without the quotes).

Otherwise print a single number — the shortest distance the saucer must travel from the start point to the finish point, rounded to exactly six digits after the decimal point.