Problems
Сфера
Сфера
\includegraphics{https://static.e-olymp.com/content/f4/f442cf357c4fa03438c9e9fd42236ed031dfafc2.jpg}
\textbf{Зимняя школа в Харькове 2011} началась задачкой "\href{/problems/1829}{Касательные к сферам}", предложенной Станиславом Паком. Первый день был полностью посвящён геометрии в пространстве, полюбившейся автору контеста ещё со школьных времён, когда он сам решал очень понравившуюся ему пространственную жизненную геометрическую задачку, предлагаемую ниже и вам:
"\textit{На планете, представляющей собой сферу, есть }\textit{\textbf{N}}\textit{ городов. Передвигаться по планете можно только днём, и за один день можно пройти расстояние не больше }\textit{\textbf{D}}\textit{. Требуется за наименьшее количество дней добраться из одного города в другой.}"
\InputFile
В начале входного файла задано целое число \textit{\textbf{N}} (\textbf{1} ≤ \textit{\textbf{N}} ≤ \textbf{1000}). Затем заданы два целых числа \textit{\textbf{S}}\textbf{_1} и \textit{\textbf{S}}\textbf{_2} (\textbf{1} ≤ \textit{\textbf{S}}\textbf{_1}, \textit{\textbf{S}}\textbf{_2} ≤ \textit{\textbf{N}}, \textit{\textbf{S}}\textbf{_1} ≠ \textit{\textbf{S}}\textbf{_2}) --- номера городов, путь между которыми необходимо найти. Затем задано целое число \textit{\textbf{R}} (\textbf{0} < \textit{\textbf{R}} ≤ \textbf{10^11}) --- радиус планеты. Затем задано целое число \textit{\textbf{D}} (\textbf{0} < \textit{\textbf{D}} ≤ \textbf{4·10^11}). Следующие \textit{\textbf{N}} строк задают расположение городов в виде \textit{\textbf{G}}\textbf{_1 }\textit{\textbf{T}}\textbf{_1 }\textit{\textbf{G}}\textbf{_2 }\textit{\textbf{T}}\textbf{_2}, где:
\begin{itemize}
\item \textit{\textbf{G}}\textbf{_1} --- вещественное число, задающее широту (\textbf{0} ≤ \textit{\textbf{G}}\textbf{_1} ≤ \textbf{90});
\item \textit{\textbf{T}}\textbf{_1} --- символ широты: '\textbf{N}' --- северная, '\textbf{S}' --- южная;
\item \textit{\textbf{G}}\textbf{_2} --- вещественное число, задающее долготу (\textbf{0} ≤ \textit{\textbf{G}}\textbf{_2} ≤ \textbf{180});
\item \textit{\textbf{T}}\textbf{_2} --- символ долготы: '\textbf{E}' --- восточная, '\textbf{W}' --- западная.
\end{itemize}
\OutputFile
В выходной файл выведите минимальное число дней, необходимое для путешествия, или --1, если путешествие невозможно.
Input example #1
2 1 2 10000 31416 89 S 13.12 W 89 N 78.8 E
Output example #1
1