At one of the many climate protests, Skylar fell in love with a fellow environmental activist. Unfortunately, the two young lovers live on opposite sides of the planet and long distance travel is only practical by (gasp) air. Skylar had scolded friends and family for flying, heavily handing out the recent Swedish export flygskam (verbatim translation: flight shame). But alas, the things we do for love! Now they want your help to calculate the minimum amount of flygskam Skylar will accumulate on a one-way trip across the globe.

To calculate the best route you models the planet as a perfect sphere and assumes that all flights fly at the distance $6381$ km from the center of the earth. The amount of shame for a single point-to-point flight is calculated as the distance between the airports in km, plus a take-off and landing penalty of $100$, that is, two airports with the flight distance $1000$ km will result in $1100$ shame.

-----Latitude and longitude-----
The positions of the airports are given as the latitude and longitude in (decimal) degrees. The latitude of a point $P$ on the earths surface is the angle between the equatorial plane and a line passing through $P$ and the center of the earth. The equator has latitude $0^\circ$, points north of the equator has positive values and points south of the equator has negative values, the North Pole has latitude $90^\circ$ and the South Pole latitude $-90 ^\circ$. Half circles that run from the North to the South pole are called meridians. The zero meridian runs through Greenwich. The longitude of a point $Q$ is the angle between the zero meridian plane and the line that run through $Q$ and the center of the earth, with values from $- 180^\circ$ to $+180^\circ$, with positive values east of Greenwich.

-----Input-----
Input starts with one line with two integers $1 \leq N \leq 10000$, the number of airports and $1 \leq M \leq 100000$, the number of two-way flight routes. The second line has two strings $S$ and $T$, Skylar’s start position and Skylar’s target position. Then follows $N$ lines, each starts with a three letter (uppercase) airport code, followed by two real values numbers, the latitude and longitude in degrees. Then follows $M$ lines, each with two strings $a$ and $b$, the airports with a two-way flight connection.

All flight airports have unique names and all connections are between existing airports.

-----Output-----
Output a real value with the minimum amount of flygskam Skylar will obtain on a one-way trip. If the target is unreachable and Skylar will be forever alone, output -1. Answers within a relative or absolute error of $10^{-6}$ will be accepted.

-----Examples-----
Sample Input 1:
4 4
ARN SCR
ARN 59.6467921 17.9370443
SCR 61.156603 12.837360
CPH 55.618023 12.650763
OSL 60.197646 11.100008
ARN OSL
ARN CPH
SCR OSL
OSL CPH
Sample Output 1:
729.09706162045

Sample Input 2:
2 1
LAX AKL
AKL -37.006131 174.783781
LAX 33.941589 -118.408531
LAX AKL
Sample Output 2:
10603.3297338597

见题面

见题面