Я буду поруч
Звичайне дорожнє перехрестя в Європі, яке стає популярним у Сполучених Штатах, — це "кільцева розв'язка". Коли водій в'їжджає на кільцеву розв'язку, він поступається дорогою автомобілям, які вже знаходяться на кільцевій розв'язці, а потім продовжує рух до правильного виїзду. Кільцеві розв'язки можуть мати кілька смуг для в'їзду, руху по колу та виїзду з дорожньої структури, яка містить центральну зону, зазвичай круглу. У США автомобілі рухаються проти годинникової стрілки, тоді як у Великобританії та в районах, де норма — їздити ліворуч, автомобілі рухаються за годинниковою стрілкою.
У певній країні, Кругославії, використовують кільцеві розв'язки для всіх дорожніх перехресть. Також, оскільки кільцеві розв'язки настільки популярні, уряд вирішив, що центральне коло може бути досить великим. Вони планують розмістити парки в центрі. Це створює проблему для туристичного бюро Кругославії; відстань між двома точками на карті, яку вони хотіли б надрукувати в туристичних путівниках, буде більшою через збільшену відстань на перехрестях.
Кругославці їздять праворуч, тому вони рухаються проти годинникової стрілки. Таким чином, автомобіль, що в'їжджає на перехрестя справа (Схід) і виїжджає внизу (Південь), зробить три чверті (¾) кола. Якщо центральний острівець має діаметр 500 метрів, автомобіль проїде ¾ довжини кола діаметром 500 метрів. Загалом, якщо ми вважаємо Схід за 0 градусів, Північ за 90 градусів, Захід за 180 градусів і так далі, ми можемо переформулювати це як "автомобіль в'їжджає з нульового градуса і виїжджає на 270 градусах". Кільцеві розв'язки розташовані так, щоб мінімізувати кількість дороги, необхідної між ними, тому автомобілі можуть в'їжджати в довільній точці, скажімо, 48 градусів, і виїжджати на 190 градусах. Також інші автомобілі можуть в'їжджати на 190 і виїжджати на 48.
При розрахунку відстаней між місцями на карті, туристичне бюро бажає включити ці додаткові відстані руху по кільцевій розв'язці, щоб відвідувачі країни мали точну оцінку того, скільки часу займе їхня поїздка.
Маючи дані про набір кільцевих розв'язок, дороги, що їх з'єднують, та початкову і кінцеву кільцеві розв'язки, визначте мінімальну відстань між початковою та кінцевою кільцевими розв'язками та відповідний маршрут. Правильний маршрут завжди буде унікальним.
Вхідні дані
Буде розглянуто довільну кількість випадків. Вхід починається з рядка, що містить одне ціле число, яке вказує кількість випадків. Цей рядок супроводжується вхідними даними для першого випадку, потім вхідними даними для другого випадку і так далі.
Вхідні дані для кожного випадку починаються з рядка, що містить одне ціле число NRB (1 ≤ NRB ≤ 25), яке є кількістю кільцевих розв'язок. Цей рядок супроводжується NRB рядками, де I-й рядок (1 ≤ I ≤ NRB) вказує діаметр I-ї кільцевої розв'язки в метрах.
Наступний рядок у вхідних даних для кожного випадку містить одне ціле число NRD (1 ≤ NRD ≤ 100), яке є кількістю доріг, що з'єднують кільцеві розв'язки. Цей рядок супроводжується NRD рядками (тобто по одному для кожної дороги), кожен з яких містить п'ять (5) цілих чисел, розділених одним або кількома пробілами. Перші два цілі числа ідентифікують кільцеві розв'язки, які з'єднані дорогою. Третє ціле число вказує довжину дороги в метрах, але не включає жодної відстані, яка може бути пройдена всередині кільцевих розв'язок. Четверте ціле число вказує кут (у градусах), під яким дорога з'єднується з кільцевою розв'язкою, вказаною першим цілим числом. Аналогічно, п'яте ціле число вказує кут, під яким дорога з'єднується з кільцевою розв'язкою, вказаною другим цілим числом. Кути завжди будуть невід'ємними і меншими за 360 градусів.
Останній рядок у вхідних даних для кожного випадку містить два цілі числа, розділені пробілом. Ці числа ідентифікують початкову та кінцеву кільцеві розв'язки, між якими потрібно визначити мінімальну відстань та відповідний маршрут.
Дороги можуть трохи вигинатися; виїзд з кільцевої розв'язки під 90 градусів не обов'язково означає в'їзд в іншу під 270 градусів. Ми не переймаємося цим. Також немає односторонніх доріг, і є не більше однієї дороги, що безпосередньо з'єднує будь-яку пару кільцевих розв'язок.
При визначенні відстані, пройденої в межах однієї кільцевої розв'язки, розрахунок слід проводити з використанням дійсних чисел, а потім скорочувати до цілого числа.
На в'їзді на кільцеву розв'язку не дозволяються "розвороти". Щоб в'їхати і виїхати під тим самим кутом, водій повинен об'їхати повністю — 360 градусів.
Приклад: Розгляньте вхідні дані, наведені в прикладі введення (нижче). Є два випадки для розгляду. Перший випадок має 9 кільцевих розв'язок (з діаметрами 500, 450, …, 1500) та 12 доріг. Перша дорога з'єднує кільцеві розв'язки 6 і 1, і має довжину 15000 метрів. Вона з'єднується з кільцевою розв'язкою 6 під кутом 0 градусів, а з кільцевою розв'язкою 1 під кутом 180 градусів. Для цього випадку ви повинні знайти відповідний маршрут між кільцевими розв'язками 6 і 9.
Зверніть увагу, що немає додаткової відстані, пов'язаної з в'їздом або виїздом з кінцевих точок. У першому прикладі випадку, початковий виїзд з кільцевої розв'язки шість не додає додаткової відстані, і в'їзд на кільцеву розв'язку дев'ять також не додає додаткової відстані. Як простий приклад, припустимо, що вас запитали про відстань між кільцевими розв'язками один і шість. Це буде просто 15000 метрів. Як інший приклад, відстань від одного до одного становить нуль метрів. Маршрут у цьому випадку — 1.
Вихідні дані
Для кожного випадку введення надрукуйте номер випадку (1, 2, …), відстань між початковою та кінцевою точками та маршрут у форматі, показаному нижче. Відступіть рядки "Відстань: " та "Шлях: " на три пробіли та включіть порожній рядок як останній рядок у виході для кожного випадку. Дотримуйтесь показаного формату.