Для того чтобы понять ранние цивилизации, археологи часто изучают тексты, написанные на древних языках. Один из таких языков, используемых в Египте более 3000 лет назад, был основан на символах, называемых иероглифами. Рисунок С.1 показывает шесть иероглифов и их названия. В этой задаче Вам следует написать программу, которая будет распознавать эти шесть символов.
Рисунок C.1: Шесть иероглифов
Входные данные состоят из нескольких тестов, каждый из которых описывает изображение, содержащее один или более иероглифов, изображенных на рисунке C.1. Изображения задаются в виде последовательности горизонтальных сканирующих линий, состоящих из черных точек (представляемых 1) и белых точек (представляемых 0). Во входных данных сканирующая прямая закодирована в шестнадцатеричной системе счисления. Например, последовательность точек 10011100 (одна черная точка, за ней следует две белых и так далее) представляется шестнадцатеричным числом 9c. В шестнадцатеричной записи чисел используются только прописные буквы от a до f. Первая строка каждого теста содержит два целых числа H и W. H (0 < H ≤ 200) - количество сканирующих линий в изображении. W (0 < W ≤ 50) - количество шестнадцатеричных символов в каждой строке. Следующие H строк содержат шестнадцатеричные символы изображения, заданные сверху вниз. Входные изображения удовлетворяют следующим условиям:
Изображение содержит только иероглифы, представленные на рисунке C.1.
Каждое изображение содержит как минимум один иероглиф.
Каждая черная точка в изображении является частью иероглифа.
Каждый иероглиф состоит из замкнутого множества черных точек, при этом каждая черная точка имеет соседнюю черную точку или сверху, или снизу, или слева, или справа.
Иероглифы не касаются друг друга и никакой иероглиф не находится внутри другого.
Если две черные точки касаются по диагонали, то обязательно будет еще одна черная точка, которая касается их обоих.
Иероглифы могут быть искаженными, но каждый из них должен быть топологически эквивалентным одному из символов, изображенных на рисунке C.1 (Две фигуры являются топологически эквивалентными, если каждая из них может быть преобразована в другую растяжением без разрывов).
Последний тест завершается строкой, содержащей два ноля.
Для каждого теста следует вывести его номер и строку, содержащую по одному символу для каждого иероглифа, распознанного в изображении, используя следующую кодировку:
Ankh: A Wedjat: J Djed: D Scarab: S Was: W Akhet: K
В каждой выходной строке коды следует выводить в алфавитном порядке как показано в примере выхода.
Пример входа содержит тесты, показанные на рисунках C.2 и C.3. Из-за ограничений на размер не все входные данные представлены в примере.