Sphere#1969
On a spherical planet, there are cities. You can only travel during daylight, and in one day, you can travel no more than units of distance. Find the minimal number of days needed to travel from one city to another.
The input starts with the integer (1 \leq N \leq 1000), the number of cities. Next, two integers S_1 and S_2 (1 \leq S_1, S_2 \leq N, S_1 \ne S_2) are given—the indices of the cities to travel between. Then the integer (0 < R \leq 10^{11}) is given—the planet's radius. Then the integer (0 < D \leq 4 \cdot 10^{11}) is given—the maximum distance you can travel in one day. The next lines describe the cities' positions as G_1 T_1 G_2 T_2, where:
G_1 is a real number—the latitude (0 \leq G_1 \leq 90);
T_1 is the latitude symbol: N for north, S for south;
G_2 is a real number—the longitude (0 \leq G_2 \leq 180);
T_2 is the longitude symbol: E for east, W for west.
Output the minimum number of days needed for the trip, or if the journey is impossible.
Example 1