Статус не є Кво#3578
Др. Хоррибл відчайдушно прагне потрапити до Ліги Зла, але йому важко довести свою компетентність як геніального лиходія. Залізним копитом Лігою править Жеребець Зла, і він оцінює заявку доктора з неабиякою підозрою. Тим часом заклятий ворог, Капітан Молот, герой народу і корпоративний слуга, неабияк ускладнює життя нашому негіднику. Але все ось-ось зміниться. Др. Хоррибл готується до масштабного пограбування: вондефлоній, необхідний для завершення роботи над його морозною гарматою, транспортують фургоном кур'єрської служби — дрібнична справа! На жаль, все не так просто, як здавалося. Пристрій, який він створив для керування фургоном, перетворився на клубок дротів, який треба терміново розплутати. Він би й доручив це вологому сусіду Мокрому, але це, мабуть, погана ідея — Мокрому взагалі не варто наближатися до електроніки (з очевидних причин). Вам краще взятися за це, і якнайшвидше, інакше вам кінець — мереживний, легко майорить завісою.
Рисунок 1: Позначення контактних точок
Ви можете допомогти, визначивши кінцеву позицію заданого дроту, знаючи його початкову позицію для різних електронних плат. Тут електронна плата — це прямокутна сітка з квадратів, і кожен квадрат має контактних точок, по дві з кожного боку. У кожному квадраті може бути будь-яка кількість дротів (від до включно), що з'єднують одну контактну точку з іншою. Кожна контактна точка може бути задіяна лише одним дротом або взагалі не бути задіяна; розгалужень немає. Позначаючи контактні точки квадрата літерами від A до H (завжди великі літери), починаючи з лівої точки верхнього краю та рухаючись за годинниковою стрілкою, ви можете описати кожен квадрат як сукупність дротів, що йдуть від однієї позначеної точки до іншої. Наприклад, якщо в квадраті є дріт, що з'єднує ліву точку на верхньому краї з нижньою точкою правого краю, дріт з лівої точки нижнього краю до правої точки нижнього краю та дріт з правої точки верхнього краю до верхньої точки лівого краю, то такий квадрат можна описати як AD BH EF. Для однаковості кожна пара точок у дроті записується в алфавітному порядку (BH замість HB), а всі пари для кожного квадрата записуються в алфавітному порядку при описі квадрата.
Квадрати розташовані поруч один з одним з усіх боків, утворюючи електронну плату. Для будь-якого квадрата контактні точки A та B з'єднуються, відповідно, з F та E квадрата вище, і навпаки для квадрата нижче. Контактні точки C та D з'єднуються з H та G відповідно з квадратом праворуч, і навпаки — для квадрата ліворуч. Якщо у квадраті є дріт, підключений до даної контактної точки, то відповідна контактна точка в сусідньому квадраті обов'язково продовжує шлях цього дроту до своєї точки. Розірваних ланцюгів немає; всі шляхи починаються і закінчуються на краю електронної плати.
Вхід містить кілька наборів задач. Кожен набір складається з двох частин: опису плати та набору початкових точок. Опис плати починається з одного рядка, у якому два цілих числа і , обидва від до включно, розділені пробілом. Це, відповідно, висота та ширина електронної плати в квадратах. Далі йде (1 \leq n \leq h \cdot w) рядків із описами квадратів, які можуть йти у довільному порядку. Кожен із цих рядків описує один квадрат і починається з числового позначення квадрата. Квадрати нумеруються зліва направо, зверху вниз, починаючи з ; наприклад, верхній правий квадрат має номер . Далі йде опис проводки у квадраті, як визначено вище. Число та всі пари дротів розділені одним пробілом. Не всі квадрати можуть бути описані, і описуватись вони будуть не більше одного разу на плату. Квадрати без опису не мають жодного дроту.
Опис плати відокремлений від набору початкових точок рядком, що містить лише число нуль (0). Початкові точки наведено в наступному рядку, кожна складається з числа та літери разом. Початкові точки розділяються одним пробілом. Число означає номер квадрата, а літера — контактну точку даного квадрата, з якої починається шлях. Будуть задані лише контактні точки, розташовані на зовнішньому краї плати. Будуть задані лише ті точки, до яких підключено дріт. За цим рядком іде один порожній рядок, після якого починається наступний набір задач.
Кінець вхідного файлу позначається двома нулями, розділеними пробілом, замість стандартного першого рядка набору задач.
Для кожного набору задач виведіть одним рядком "Board" і пробіл, номер плати (номер першої задачі — , він збільшується на з кожною наступною задачою), далі двокрапка (:).
Для кожної початкової точки у цьому наборі виведіть кінцеву точку цього дроту у форматі "startpoint is connected to endpoint" в окремому рядку. Наприклад, якщо дана початкова точка — 1A, а кінцева — 9H, то відповідь має виглядати "1A is connected to 9H". Важливий регістр літер. Усі дроти двосторонні, тож для тієї ж задачі, якщо стартова точка — 9H, потрібно вивести "9H is connected to 1A". Літера у стартовій та кінцевій точках має бути великою. Не повинно бути жодних інших символів чи пунктуації.
Відповідь для кожного набору задач має бути відокремлена порожнім рядком.
Рисунок 2: Перша тестова задача
Приклад 1