Найкоротший маршрут польоту
Комерційні рейси статистично досить безпечні (в термінах кількості смертей на пасажиро-кілометр, лише політ на Місяць безпечніший). Проте існують причини для запобіжних заходів і правил безпеки. Одним із ранніх таких правил було так зване правило "60 хвилин", яке вимагало, щоб двомоторний літак завжди знаходився в межах 60 хвилин від найближчого відповідного аеропорту вздовж усього маршруту польоту. Існувала різноманітність подібних правил, але в основі вони залишаються однаковими: маршрут польоту не може віддаляти літак на певну максимальну дозволену відстань від найближчого аеропорту. Через ці обмеження літаки не завжди можуть використовувати прямий маршрут для польоту з одного аеропорту до іншого.
У цій задачі ми обчислимо найкоротший маршрут польоту між двома аеропортами, дотримуючись правила максимально дозволеної відстані. На малюнку нижче, який ілюструє перший зразок тестового випадку, будь-який маршрут польоту повинен залишатися в межах трьох кіл. Таким чином, літак, що летить з аеропорту 2 до аеропорту 3, повинен об'їжджати прямий маршрут через регіон навколо аеропорту 1. Зверніть увагу, що літак не обов'язково повинен летіти до самого аеропорту 1.
Ситуація ускладнюється тим, що літаки мають обмежений запас пального, і для подолання більших відстаней їм може знадобитися зупинка в проміжних аеропортах. Таким чином, залежно від ємності бака, літак, що летить з аеропорту 2 до аеропорту 3 на малюнку, може змушений зупинитися в аеропорту 1 (або ємність бака може бути занадто малою навіть для польоту до аеропорту 1, у такому випадку подорож буде неможливою).
Ми робимо такі спрощувальні припущення:
Поверхня землі є сферою радіусом 6370 км.
І час, і витрати пального прямо пропорційні пройденій відстані. Іншими словами, нас цікавить лише загальна пройдена відстань.
Різниця у відстані, викликана польотами літаків на різних висотах, є незначною. Таким чином, фактично, ми припускаємо, що вони летять уздовж поверхні землі.
Літак може зупинятися для дозаправки в стількох проміжних аеропортах, скільки потрібно, кожного разу отримуючи повний бак.
Вхідні дані
Перша строка кожного тестового випадку містить два цілі числа N та R, де 2 ≤ N ≤ 25 — це кількість аеропортів, а 1 ≤ R ≤ 10000 — це максимально дозволена відстань польоту (в км) від найближчого аеропорту. Кожна з наступних N строк містить два цілі числа φ, θ, що задовольняють 0 ≤ φ < 360 та -90 ≤ θ ≤ 90, довготу та широту (відповідно) аеропорту, у градусах. Аеропорти пронумеровані відповідно до їх порядку у вхідних даних, починаючи з одиниці. Жодні два аеропорти не знаходяться в одній і тій самій позиції.
Після цього йде строка, що містить ціле число Q, яке задовольняє 1 ≤ Q ≤ 100. Кожна з наступних Q строк містить три цілі числа s, t, c, що задовольняють 1 ≤ s, t ≤ N, s ≠ t, та 1 ≤ c ≤ 50000, що вказують на літак, який летить з аеропорту s до аеропорту t з ємністю бака, що дає запас ходу c км.
Вихідні дані
Для кожного тестового випадку виведіть номер випадку, а потім одну строку для кожного запиту, що містить довжину в км найкоротшого маршруту польоту між аеропортами s та t, з урахуванням обмеження на пальне c. Виведіть довжину з точністю до трьох десяткових знаків. Якщо немає допустимого маршруту між двома аеропортами, виведіть слово неможливо замість цього.
Ви можете припустити, що відповідь є чисельно стабільною для збурень до 0.1 км для R або c.