Два кільця
У 21XX році людство успішно встановило контакт з позаземними формами життя. Ми знайшли кілька планет, де живуть розумні істоти, і насолоджуємося міжпланетним спілкуванням. Вегетаблія є однією з таких планет. Жителі Вегетаблії виглядають як овочі на Землі, тому ми називаємо їх Вегетабліанами з повагою та дружелюбністю.
Одного дня пан Картопля, один з ваших друзів Вегетабліан, повідомив вам, що вирішив одружитися зі своєю дівчиною, пані Помідор. Він сказав: "По правді кажучи, ми повинні зробити одну річ перед нашим весіллям."
"На Вегетаблії існує традиційна практика шлюбів. Згідно з цією практикою, чоловік і жінка, які хочуть одружитися, повинні окремо здійснити подорож навколо Вегетаблії та розширити свої знання перед весільною церемонією. Кожен з них починає подорож з окремої точки на планеті і продовжує рухатися вперед, поки не досягне своєї початкової точки. Ця практика називається обітницею двох кілець, тому що шляхи їхніх подорожей схожі на два кільця на планеті."
"Існує відома плітка про це: 'пара, яка зустрілася під час подорожі, стане щасливою'. Я сподіваюся, що це здійсниться, але я зрозумів, що є випадки, коли ми ніколи не можемо зустрітися, залежно від наших початкових точок і напрямків. Я дійсно хочу знати, чи можемо ми зустрітися."
Як добрий друг пана Картоплі, ви хочете вирішити цю проблему для нього. Планета Вегетаблія вважається одиничною сферою, а шлях подорожі виражається як поверхня перетину сфери. Враховуючи два шляхи, ваше завдання - знайти координати їхніх точок перетину (якщо вони існують).
Вхідні дані
Вхідні дані складаються з кількох тестових випадків.
Перша строка вхідних даних містить ціле число, яке позначає кількість тестових випадків.
Кожен тестовий випадок складається з описів двох різних кіл на сфері, кожне з яких представлено двома координатами широти/довготи. Дві координати широти/довготи p[1] і p[2] вказують на коло, діаметр якого збігається з відрізком p[1]-p[2]. Кожна координата широти/довготи задається наступним чином:
lat [N|S] long [E|W]
де lat і long - це широта і довгота точки в градусах відповідно. Другий (N або S) і четвертий токен (E або W) вказують, до якої півкулі належить точка. Значення lat і long задовольняють умови 0 ≤ lat ≤ 90 і 0 ≤ long ≤ 180.
У кожному представленні координат можна припустити, що p[1] і p[2] ніколи не збігаються, а відрізок p[1] - p[2] не є діаметром одиничної сфери. Також можна припустити, що значення широти і довготи у вхідних даних є цілими числами. Гарантовано, що є два перетини, якщо є якісь перетини.
Вихідні дані
Для кожного тестового випадку виведіть рядок "Case n:", де n - номер тестового випадку. Після рядка виведіть "No intersection.", якщо два кола ніколи не перетинаються. В іншому випадку виведіть координати перетинів у тому ж форматі, що й у вхідних даних. Значення повинні бути надруковані з трьома знаками після коми. Якщо координати можуть бути представлені кількома способами, будь-який з них підходить. Усі значення повинні бути надруковані без знаків мінус.
Виведіть порожній рядок між кожним тестовим випадком.