Сфера — Eolymp

Вхідні дані

У першому рядку задано ціле число $N$ ( $1 \leq N \leq 1000$ 1 \leq N \leq 1000) — кількість міст. Далі задано два цілих числа $S_{1}$ S_1 та $S_{2}$ S_2 ( $1 \leq S_{1}, S_{2} \leq N$ 1 \leq S_1, S_2 \leq N, $S_{1} \neq = S_{2}$ S_1 \ne S_2) — індекси міст, між якими потрібно здійснити подорож. Потім задано ціле число $R$ ( $0 < R \leq 1 0^{11}$ 0 < R \leq 10^{11}) — радіус планети. Наступне ціле число $D$ ( $0 < D \leq 4 \cdot 1 0^{11}$ 0 < D \leq 4 \cdot 10^{11}) — максимальна відстань, яку можна пройти за один день. Далі йдуть $N$ рядків — координати міст у вигляді $G_{1}$ G_1 $T_{1}$ T_1 $G_{2}$ G_2 $T_{2}$ T_2, де:

$G_{1}$ G_1 — дійсне число, широта ( $0 \leq G_{1} \leq 90$ 0 \leq G_1 \leq 90);
$T_{1}$ T_1 — символ широти: N — північна, S — південна;
$G_{2}$ G_2 — дійсне число, довгота ( $0 \leq G_{2} \leq 180$ 0 \leq G_2 \leq 180);
$T_{2}$ T_2 — символ довготи: E — східна, W — західна.

Вихідні дані

Виведіть мінімальну кількість днів, необхідних для такої подорожі, або $- 1$ , якщо дістатися з міста $S_{1}$ S_1 до міста $S_{2}$ S_2 неможливо.

Приклади

Приклад 1

Loading