Sphere
The Winter School in Kharkiv 2011 kicked off with the problem "Tangents to Spheres", crafted by Stanislav Pak. The first day was entirely devoted to spatial geometry, a subject the contest author has cherished since his school days. He once tackled a spatial geometric problem that he particularly enjoyed, and now it's your turn to solve it:
"On a spherical planet, there are N cities. You can only travel during daylight, and in one day, you can cover a distance of no more than D. Your task is to travel from one city to another in the fewest possible days."
Input
The input begins with an integer N (1 ≤ N ≤ 1000), representing the number of cities. Following this, two integers S_1 and S_2 (1 ≤ S_1, S_2 ≤ N, S_1 ≠ S_2) are provided, indicating the cities between which you need to find a route. Next, an integer R (0 < R ≤ 10^11) is given, representing the planet's radius. Then, an integer D (0 < D ≤ 4·10^11) is specified, denoting the maximum distance you can travel in a day. The subsequent N lines describe the locations of the cities in the format G_1 T_1 G_2 T_2, where:
G_1 — a real number indicating the latitude (0 ≤ G_1 ≤ 90);
T_1 — the latitude direction: 'N' for north, 'S' for south;
G_2 — a real number indicating the longitude (0 ≤ G_2 ≤ 180);
T_2 — the longitude direction: 'E' for east, 'W' for west.
Output
Output the minimum number of days required to complete the journey, or –1 if the journey is not possible.