Сфера
Зимова школа у Харкові 2011 почалась задачкою "Дотичні до сфер", запропонованої Станіславом Паком. Перший день було повністю присвячено геометрії у просторі, якп сподобалась автору контеста ще зі шкільних часів, коли він сам розв'язував просторову життєву геометричну задачку, яка дуже сподобалась йому і запропоновану нижче і вам:
"На планеті, яка являє собою сферу, є N міст. Пересуватись по планеті можна лише вдень, і за один день можна пройти відстань не більшу D. Потрібно за найменшу кількість днів дістатись від одного міста до іншого."
Вхідні дані
На початку вхідного файлу задано ціле число N (1 ≤ N ≤ 1000). Потім задано два цілих числа S_1 і S_2 (1 ≤ S_1, S_2 ≤ N, S_1 ≠ S_2) — номери міст, шлях між якими необхідно знайти. Потім задано ціле число R (0 < R ≤ 10^11) — радіус планети. Далі задано ціле число D (0 < D ≤ 4·10^11). Наступні N рядків задають розміщення міст у вигляді G_1 T_1 G_2 T_2, де:
G_1 — дійсне число, яке задає широту (0 ≤ G_1 ≤ 90);
T_1 — символ широти: 'N' — північна, 'S' — південна;
G_2 — дійсне число, яке задає довготу (0 ≤ G_2 ≤ 180);
T_2 — символ довготи: 'E' — східна, 'W' — західна.
Вихідні дані
У вихідний файл виведіть мінімальну кількість днів, потрібну для подорожі, або –1, якщо подорож неможлива.