Древний памятный монолит
Однажды в лесу Алиса нашла старый монолит.
Она исследовала монолит и обнаружила, что это предложение, написанное на древнем языке. Оно состоит из глифов и прямоугольников, которые их окружают. Для приведенного выше примера имеются следующие глифы.
Обратите внимание, что некоторые глифы в предложении перевернуты по горизонтали.
Алиса решила транслитерировать его, используя ASCII-символы, присваивая каждой глифе букву алфавита, а '[' и ']' — прямоугольникам. Если предложение содержит перевернутый глиф, она транслитерирует его справа налево. Например, она могла бы присвоить 'a' и 'b' указанным выше глифам соответственно. Тогда указанное выше предложение будет транслитерировано в "[[ab][ab]a]".
После изучения предложения Алиса поняла, что оно организовано по следующей структуре:
Предложение [seq] — это последовательность, состоящая из нуля или более [term].
Термин [term] — это либо глиф, либо [box]. Глиф может быть перевернут.
[box] — это прямоугольник, окружающий [seq]. Высота прямоугольника больше, чем у любых глифов внутри.
Теперь предложение, написанное на монолите, является непустой [seq]. Каждый термин в последовательности помещается в прямоугольную ограничивающую рамку, хотя рамки явно не указаны для глифов. Эти ограничивающие рамки для соседних терминов не перекрываются. Алиса формализовала правила транслитерации следующим образом.
Пусть f будет функцией транслитерации.
Каждая последовательность s = t_1t_2...t_m записывается либо слева направо, либо справа налево. Однако, обратите внимание, что здесь t_1 соответствует самому левому термину в предложении, t_2 — второму термину слева и так далее.
Определим, что это перевернутый глиф g. Последовательность должна быть записана справа налево, если последовательность содержит один или более одно-глифовых терминов, которые невозможно прочитать без переворота, то есть существует целое число i, где t_i — это один глиф g, и g отсутствует в словаре глифов, предоставленном отдельно, тогда как есть. В таких случаях f(s) определяется как f(t_m)f(t_{m-1})...f(t_1), в противном случае f(s) = f(t_1)f(t_2)...f(t_m). Гарантируется, что все глифы в последовательности перевернуты, если есть один или более глифов, которые невозможно прочитать без переворота.
Если термин t_i — это прямоугольник, содержащий последовательность s′, то f(t_i) = '['f(s′)']'. Если термин t_i — это глиф g, то f(t_i) отображается в букву алфавита, соответствующую глифу g, или если последовательность, содержащая g, записана справа налево.
Пожалуйста, создайте программу для транслитерации предложений на монолитах, чтобы помочь Алисе.
Входные данные
Входные данные состоят из нескольких наборов данных. Конец входных данных обозначается двумя нулями, разделенными одним пробелом.
Каждый набор данных имеет следующий формат.
n m
glyph_1
...
glyph_n
string_1
...
string_m
n (1 ≤ n ≤ 26) — количество глифов, а m (1 ≤ m ≤ 10) — количество монолитов. glyph_i задается в следующем формате.
c h w
b_11...b_1w
...
b_h1...b_hw
c — это строчная буква алфавита, которую Алиса присвоила глифу. h и w (1 ≤ h ≤ 15, 1 ≤ w ≤ 15) определяют высоту и ширину битовой карты глифа соответственно. Матрица b указывает битовую карту. Белая ячейка представлена символом '.', а черная ячейка — символом '*'.
Можно предположить, что все глифы имеют разные символы. Можно предположить, что каждый столбец битовой карты содержит хотя бы одну черную ячейку, а первая и последняя строки битовой карты содержат хотя бы одну черную ячейку. Каждая битовая карта отличается от других, но возможно, что перевернутая битовая карта совпадает с другой битовой картой. Более того, могут быть симметричные битовые карты.
string_i задается в следующем формате.
h w
b_11...b_1w
...
b_h1...b_hw
h и w (1 ≤ h ≤ 100, 1 ≤ w ≤ 1000) — это высота и ширина битовой карты последовательности. Аналогично словарю глифов, b указывает битовую карту, где белая ячейка представлена символом '.', а черная ячейка — символом '*'.
Шума нет: каждая черная ячейка в битовой карте принадлежит либо одному глифу, либо одному прямоугольнику. Высота прямоугольника составляет не менее 3 и больше максимальной высоты самого высокого глифа. Ширина прямоугольника составляет не менее 3.
Прямоугольник должен иметь отступ в 1 пиксель по краю.
Можно предположить, что глифы никогда не располагаются вертикально. Более того, можно предположить, что если два прямоугольника или прямоугольник и глиф находятся в одном столбце, то один из них содержит другой. Для всех ограничивающих рамок глифов и черных ячеек прямоугольников между каждыми двумя из них есть хотя бы одна белая ячейка. Можно предположить, что в битовой карте есть хотя бы одна черная ячейка.
Выходные данные
Для каждого монолита выведите транслитерированное предложение в одной строке. После вывода для одного набора данных выведите '#' в одной строке.