Шлях польоту
Клуб застарілих транспортних засобів вирішив відсвяткувати 5 травня 5555 року великими польотами копій стародавніх літаків. Члени клубу побудували в різних місцях на поверхні Землі N (2 ≤ N ≤ 1000) аеродромів і підготували літаки. Однак, через нову поправку до закону про екологічні податки, клуб змушений провести святкування у скороченому форматі. Було обрано два аеродроми, і лише один літак буде літати між ними, використовуючи найкоротший можливий шлях! Максимальна відстань, яку він може пролетіти без посадок, становить R км, тому, якщо необхідно, він може використовувати проміжні аеродроми.
Допоможіть клубу знайти найкоротший маршрут, вважаючи поверхню Землі точною сферою з довжиною екватора рівно 40000 км і ігноруючи вплив висоти польоту на відстань.
Вхідні дані
Перший рядок вхідних даних містить R — максимальну відстань прямого польоту (в кілометрах, 10 ≤ R ≤ 50000). Другий рядок містить кількість аеродромів N. Наступні N рядків містять географічні координати аеродромів. Формат координат: спочатку широта (велика літера N або S — Північ або Південь, потім градуси, хвилини і секунди), потім довгота (аналогічно, але з використанням літери E або W — Схід або Захід), всі числа і літери розділені одним пробілом. У останньому рядку вхідних даних два цілі числа позначають аеродроми, обрані як стартовий і фінішний (1-базова нумерація, тобто нумерація починається з 1).
Вихідні дані
Ваша програма повинна вивести три рядки. 1-й рядок повинен містити одне число з плаваючою комою — мінімально можливу довжину маршруту від старту до фінішу, в кілометрах, з точністю до метрів. 2-й рядок повинен містити рівно одне ціле число K — кількість проміжних аеродромів на маршруті. 3-й рядок повинен містити список цих проміжних аеродромів, у порядку від старту до фінішу. Якщо існують різні правильні відповіді, ваша програма повинна знайти будь-яку з них. Якщо літак може досягти фінішу від старту без посадок, 2-й рядок повинен містити 0, а 3-й рядок повинен бути порожнім. Якщо літак не може досягти фінішу від старту, 1-й рядок повинен містити число 123456789.000, 2-й — число 0, а 3-й повинен бути порожнім.