Incident in Atlantis

In the year 2222 BCE, a terrible tragedy took place on the island of Atlantis. To this day it is known only from historical accounts; nobody has ever found physical evidence of the incident. To fix this, Doctor Quem decided to use his time machine to travel back to Atlantis just before the disaster.

Being cautious, as soon as he arrived in Atlantis Doctor Quem set up a time portal that will bring him straight back to the present. He then began exploring, and what he found was surprising. Atlantis is a circular island on which an extremely advanced civilization was founded. The proof is the many booths of the teleporter network built across the island. The booths work with light beams, so teleporting is possible only if there is an unobstructed line of sight between the origin booth and the destination booth. Unsurprisingly, the booths are among the most imposing buildings on the island, tens of meters tall, and only the giant murals that depict the history of Atlantis since its founding are taller. The murals are huge concrete walls. They cannot be crossed, so the famous scientist has to walk around them to continue on his way, which makes exploring hard.

While exploring, Doctor Quem was surprised to find the island deserted. After thinking for a long time, the reason became obvious: he had set his time machine wrong and arrived right before the tidal wave that destroyed Atlantis (the Atlantean geologists had already predicted the tidal wave and ordered the immediate evacuation of the island). Realizing this, Doctor Quem immediately started planning his escape.

He intends to use the teleporters to get back to the time portal, but he found out that, because of the tidal wave, the power system can only handle a limited number of teleports. He wants to know the shortest distance he has to walk to reach the time portal, and he needs your help.

• Doctor Quem can walk freely on the island but cannot cross a wall. Walls have negligible thickness, so he may pass through a wall endpoint or walk along a wall.
• One teleport moves him from one booth to another booth, and the distance does not count as walking. Teleporting is possible only if the segment joining the two booths shares no point with any wall. A segment that merely touches a wall endpoint counts as blocked.
• He can teleport at most $T$ times in total.

The input contains several test cases and continues until end of file. The first line of each test case contains three integers $T$, $M$, and $C$: the number of times the teleporter network can still be used, the number of murals in Atlantis, and the number of teleporter booths.

The next $M$ lines describe the murals, all of which are straight segments. Each line contains four integers $X_1$, $Y_1$, $X_2$, and $Y_2$, the coordinates of the two endpoints of a mural. Murals have negligible thickness, and no two murals intersect, not even at their endpoints.

The next $C$ lines describe the booth positions. Each line contains two integers $X_C$ and $Y_C$, the position of one teleporter booth.

Finally, the last line of the test case contains four integers $X_Q$, $Y_Q$, $X_P$, and $Y_P$: the coordinates of Doctor Quem's starting position and of the portal, respectively.

Constraints

• $0 \le T, M, C \le 50$
• Every coordinate in the input has absolute value at most $2 \times 10^4$.
• The center of the island is the point $(0, 0)$ and its radius is $10^5$.
• The positions of Doctor Quem, the time portal, and the teleporter booths are all distinct and do not lie on any mural.

For each test case, print on a single line the distance Doctor Quem has to walk to reach his portal, not counting the distance covered by teleporting. Round the distance to one decimal place (for example 8.1 or 10.0).