Статус не Кво
Доктор Ужасный отчаянно стремится вступить в Лигу Зла, но ему сложно доказать свою гениальность как злодея. Лига возглавляется Злым Конем, который с недоверием оценивает его заявку. В это время его заклятый враг, Капитан Молот, герой народа и корпоративный инструмент, делает жизнь Доктора Ужасного невыносимой. Однако ситуация скоро изменится. Доктор Ужасный планирует крупное ограбление: вондефлониум, необходимый для завершения его замораживающего луча, перевозится в курьерском фургоне — словно конфетка у ребенка. К сожалению, все оказалось не так просто, как он думал. Устройство, которое он создал для управления фургоном, превратилось в клубок проводов, который нужно распутать. Он бы поручил это своему соседу по комнате Влажному, но это, вероятно, плохая идея — подпускать Влажного к электронике (по очевидным причинам). Лучше сделать это самому и быстро, иначе это конец — кружевные, мягко колышущиеся занавески.
Рисунок 1: Метки точек подключения
Вы можете помочь, определив конечное положение данного провода на основе его начального положения для различных печатных плат. Печатные платы представляют собой прямоугольные сетки из квадратов, и каждый квадрат имеет 8 точек подключения, по две на каждой стороне. Квадраты могут иметь любое количество проводов (от 0 до 4 включительно), соединяющих одну точку подключения квадрата с другой. Точка подключения квадрата может быть использована только одним проводом или не использоваться вовсе; разветвлений нет. Точки подключения квадрата обозначаются буквами от A до H (всегда заглавными), начиная с левой точки подключения на верхнем краю и двигаясь по часовой стрелке. Каждый квадрат можно описать как набор проводов, соединяющих одну названную точку с другой. Например, если квадрат имеет провод, идущий от левой точки подключения на верхнем краю к нижней точке подключения на правом краю, провод от левой точки подключения нижнего края к правой точке подключения нижнего края и провод от правой точки подключения верхнего края к верхней точке подключения левого края, то квадрат можно описать как AD BH EF. Для согласованности каждая пара проводов описывается в алфавитном порядке (BH вместо HB), и все пары проводов для каждого квадрата перечисляются в алфавитном порядке.
Квадраты выровнены друг с другом со всех сторон, чтобы составить печатную плату. Для любого данного квадрата точки подключения A и B соединяются с F и E соответственно с квадратом над ним, и наоборот для квадрата под ним. Точки подключения C и D соединяются с H и G соответственно с квадратом справа от него, и наоборот для квадрата слева от него. Если квадрат имеет провод к любой данной точке подключения, его соответствующая точка подключения в соседнем квадрате гарантированно продолжает путь этого провода от своей точки подключения к другой точке подключения. Нет разорванных путей; все пути начинаются и заканчиваются на краю печатной платы.
Входные данные
Ввод состоит из нескольких наборов головоломок. Каждый набор головоломок разбит на две части: описание платы и набор начальных точек. Описание платы начинается с одной строки, содержащей два целых числа, h и w, оба от 1 до 20 включительно, разделенные пробелом. Это высота и ширина, соответственно, печатной платы в квадратах. После этого идут n (1 ≤ n ≤ h·w) строк, содержащих описания квадратов, которые идут в произвольном порядке. Каждая из этих строк описывает один квадрат и начинается с числового обозначения квадрата. Квадраты нумеруются последовательно слева направо, сверху вниз, начиная с 1; например, верхний правый квадрат имеет номер w. После номера идет описание проводки для квадрата, как определено выше. Номер и все описания проводов разделены одиночными пробелами. Не все квадраты могут иметь описание, и квадрат будет описан не более одного раза на печатной плате. Квадраты без строк не имеют подключенных проводов.
Описание платы отделено от набора начальных точек строкой, содержащей только число ноль ("1"). Начальные точки даны в следующей строке, каждая из которых состоит из числа и буквы вместе. Начальные точки разделены друг от друга одиночными пробелами. Число начальной точки — это квадрат, а буква — точка подключения квадрата, которую нужно использовать. Будут даны только точки подключения на внешней стороне печатной платы. Будут даны только точки подключения, используемые проводом. После этой строки идет одна пустая строка перед началом следующего набора головоломок.
Конец файла отмечен двумя нулями, разделенными пробелом, вместо стандартной первой строки набора головоломок.
Выходные данные
Для каждого набора головоломок в одной строке выведите "Board", за которым следует пробел, затем номер платы (номер первой головоломки начинается с 1 и увеличивается на 1 для каждой следующей головоломки), затем двоеточие (":").
Для каждой начальной точки в наборе выведите конечную точку этого провода в формате "startpoint is connected to endpoint" в одной строке. Например, если данная начальная точка была 1A, а конечная точка была 9H, вывод для этой начальной точки будет "1A is connected to 9H". Важна регистрозависимость. Все провода двунаправленные, поэтому для той же головоломки, если начальная точка была 9H, вывод будет "9H is connected to 1A". Буквенная часть начальной и конечной точки должна быть заглавной. Не должно быть других знаков или пунктуации.
Вывод для каждого набора головоломок должен быть разделен пустой строкой.
Рисунок 2: Первый пример случая