Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

M. Marooned
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Image by the U.S. Navy, from commons.wikimedia.org

Konrá$$$\eth$$$'s hobbyist aeroplane, an on-board squat rack, and a banana peel have together produced what the aviation industry calls a rapid unscheduled disassembly. Konrá$$$\eth$$$ is now somewhere. The aeroplane is now everywhere.

He regained consciousness on a plank, the one part of the aeroplane still in one piece. Whether it is bobbing on the open sea or lying on dry land, he cannot tell in the fog. He did get one look at his GPS before it, too, gave up, so he knows exactly where he is.

Maybe he is in the middle of the ocean and needs to swim to land. The swim would be shorter if the Flat Earth Society were right, but Konrá$$$\eth$$$ has to make do with the Earth he has. Take it to be a perfect sphere of radius $$$6371$$$ kilometres, with the origin of the coordinate system at its centre, so that every coordinate in this problem is a distance in kilometres. Take each landmass to be a polygon on the surface of that sphere, whose sides are great circle arcs. Konrá$$$\eth$$$'s Earth has no lakes, and therefore no islands in lakes either.

How far does Konrá$$$\eth$$$ have to swim?

Input

The input consists of:

  • One line with three real numbers $$$x$$$, $$$y$$$, and $$$z$$$, the position of Konrá$$$\eth$$$.
  • One line with an integer $$$n$$$ ($$$1 \leq n \leq 100$$$), the number of landmasses.
  • $$$n$$$ descriptions of landmasses, each of which consists of:
    • One line with an integer $$$k$$$ ($$$3 \leq k \leq 100$$$), the number of corners of the landmass.
    • $$$k$$$ lines, each with three real numbers $$$x$$$, $$$y$$$, and $$$z$$$, a corner of the landmass.

Every point in the input lies within $$$10^{-5}$$$ kilometres of the surface of the Earth, and is given with at most eight digits after the decimal point.

The corners of a landmass are given in the order in which they appear along its coast, with the land on the left — that is, counter-clockwise as seen from outside the Earth. Consecutive corners are joined by the shorter of the two great circle arcs between them; no two consecutive corners are antipodal. No two corners are within $$$0.1$$$ kilometres of each other in a straight line. The landmasses are simple polygons, no two of them intersect, and none lies inside another.

Output

Output the distance Konrá$$$\eth$$$ has to swim to reach the nearest landmass, measured along the surface of the Earth. If he is on land already, output $$$0$$$.

Your answer should have an absolute or relative error of at most $$$10^{-5}$$$.

Examples
Input
3067.758708 -3067.758708 4665.549702
2
3
4579.569933 -954.077069 4325.149381
4849.239323 -4019.764175 957.086708
5605.919436 2994.070608 445.925410
5
-2733.658938 4005.128211 4132.275139
-4775.862665 -1082.528871 4075.402808
447.156539 -4918.721930 4024.408852
4433.618367 1710.109941 4243.606151
1778.729143 5907.921798 1588.151021
Output
735.645204147872
Input
3541.698871 -4520.488559 2758.839121
1
9
3900.268462 -4879.058077 1253.929506
5845.673734 -771.280493 2413.061541
3682.390263 -877.940063 5124.340367
-967.569723 -3996.218857 4866.588608
-105.699984 -6270.499063 1122.189832
2913.818439 -4997.307324 -2669.498570
6011.437191 2003.809064 661.069691
3208.348180 1858.558946 5180.917062
6288.929998 -504.340000 885.800000
Output
0.0
Note

Explanation of samples

Image of sample 1.

Image of sample 2.