고대 기념비

시간 제한8초메모리 제한256 MB

요약

상자와 글리프가 담긴 비트맵을 해석해 거울 읽기 방향을 판정하고 괄호로 묶은 음역 문장을 출력합니다.

난이도: 보통10점 중 7점
유형: 행렬, 재귀, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

앨리스는 숲에서 오래된 비석을 발견했다. 비석에 새겨진 문장은 옛 언어로 적혀 있다. 문장은 글리프와 글리프를 둘러싼 직사각형으로 이루어지고, 문장 안에는 좌우로 뒤집힌 글리프도 섞여 있다.

앨리스는 문장을 아스키 문자로 옮겨 적기로 했다. 사전에 실린 글리프마다 소문자 하나를 배정하고, 직사각형은 [와 ]로 적는다. 문장에 뒤집힌 글리프가 들어 있으면 그 문장은 오른쪽에서 왼쪽으로 읽는다.

문장은 다음 구조를 따른다.

문장 <seq>는 <term>을 0개 이상 나열한 것이다.
항 <term>은 글리프이거나 <box>다. 글리프는 뒤집혀 있을 수 있다.
<box>는 <seq>를 둘러싼 직사각형이다. 상자의 높이는 그 안에 있는 어떤 글리프보다도 크다.

비석에 새겨진 문장은 비어 있지 않은 <seq>다. 나열된 각 항은 직사각형 경계 상자에 들어가지만 글리프의 경계 상자는 그려져 있지 않다. 이웃한 두 항의 경계 상자는 서로 겹치지 않는다.

음역 함수를 $f$ 라고 하자. 수열 $s = t_1 t_2 \dots t_m$ 은 왼쪽에서 오른쪽으로 적혀 있거나 오른쪽에서 왼쪽으로 적혀 있다. 어느 쪽이든 $t_1$ 은 문장에서 가장 왼쪽에 있는 항이고, $t_2$ 는 왼쪽에서 두 번째 항이며, 나머지도 같은 방식으로 센다.

글리프 $g$ 를 뒤집은 글리프는 $\dot{g}$ 로 쓴다. 뒤집지 않으면 읽을 수 없는 글리프 항이 수열에 하나라도 있으면, 다시 말해 $t_i$ 가 글리프 하나 $g$ 이면서 $g$ 는 글리프 사전에 없고 $\dot{g}$ 는 사전에 있는 정수 $i$ 가 존재하면 그 수열은 오른쪽에서 왼쪽으로 적힌 것이다. 이때 $f(s) = f(t_m) f(t_{m-1}) \dots f(t_1)$ 이고, 그렇지 않으면 $f(s) = f(t_1) f(t_2) \dots f(t_m)$ 이다. 뒤집지 않으면 읽을 수 없는 글리프가 하나라도 있는 수열은 그 안의 글리프가 모두 뒤집혀 있다.

항 $t_i$ 가 수열 $s'$ 을 둘러싼 상자면 $f(t_i) =$ [ $f(s')$ ]이다. 항 $t_i$ 가 글리프 $g$ 면 $f(t_i)$ 는 $g$ 에 배정된 문자이고, $g$ 가 속한 수열이 오른쪽에서 왼쪽으로 적혀 있으면 $\dot{g}$ 에 배정된 문자다.

비석에 새겨진 문장을 음역하는 프로그램을 작성하라.

입력

입력은 여러 개의 데이터 집합으로 이루어진다. 공백 하나로 구분된 0 두 개가 입력의 끝을 나타낸다.

각 데이터 집합의 형식은 다음과 같다.

n m
glyph1
...
glyphn
string1
...
stringm

$n$ ( $1 \leq n \leq 26$ )은 글리프의 개수, $m$ ( $1 \leq m \leq 10$ )은 비석의 개수다. 각 $glyph_i$ 의 형식은 다음과 같다.

c h w
b11...b1w
...
bh1...bhw

$c$ 는 앨리스가 그 글리프에 배정한 소문자다. $h$ 와 $w$ ( $1 \leq h \leq 15$ , $1 \leq w \leq 15$ )는 글리프 비트맵의 높이와 너비다. 행렬 $b$ 가 비트맵이며 흰 칸은 ., 검은 칸은 *로 나타낸다.

글리프에 배정된 문자는 서로 다르다. 글리프 비트맵의 모든 열에는 검은 칸이 하나 이상 있고, 첫 행과 마지막 행에도 검은 칸이 하나 이상 있다. 글리프 비트맵은 서로 모두 다르지만, 어떤 비트맵을 뒤집은 결과가 다른 비트맵과 같을 수 있고 좌우 대칭인 비트맵도 있을 수 있다.

각 $string_i$ 의 형식은 다음과 같다.

h w
b11...b1w
...
bh1...bhw

$h$ 와 $w$ ( $1 \leq h \leq 100$ , $1 \leq w \leq 1000$ )는 문장 비트맵의 높이와 너비다. 글리프 사전과 마찬가지로 $b$ 가 비트맵이고 흰 칸은 ., 검은 칸은 *다.

비트맵에는 잡음이 없다. 검은 칸은 모두 글리프 하나 또는 직사각형 하나에 속한다. 직사각형의 높이는 3 이상이고 사전에서 가장 높은 글리프의 높이보다 크다. 직사각형의 너비는 3 이상이다. 상자는 테두리 안쪽에 흰 칸 한 줄의 여백을 둔다.

글리프가 세로로 쌓이는 일은 없다. 직사각형 두 개, 또는 직사각형과 글리프가 같은 열을 차지하면 둘 중 하나가 나머지를 포함한다. 글리프의 경계 상자와 직사각형의 검은 칸 가운데 어느 두 개 사이에도 흰 칸이 하나 이상 있다. 비트맵에는 검은 칸이 하나 이상 있다.

출력

비석마다 음역한 문장을 한 줄에 출력한다. 한 데이터 집합의 출력이 끝나면 #을 한 줄에 출력한다.

예제4

예제 1

입력

2 1
a 11 9
****.....
.*.*.....
.*.*.....
.*..*....
.**..*...
..**..*..
..*.*....
..**.*.*.
..*..*.*.
..*****.*
******.**
b 10 6
....*.
....*.
....*.
....*.
....*.
....*.
....*.
....*.
.**..*
*****.
19 55
*******************************************************
*.....................................................*
*.********************.********************...........*
*.*..................*.*..................*...........*
*.*.****.............*.*.............****.*.****......*
*.*..*.*..........*..*.*..*..........*.*..*..*.*......*
*.*..*.*..........*..*.*..*..........*.*..*..*.*......*
*.*..*..*.........*..*.*..*.........*..*..*..*..*.....*
*.*..**..*........*..*.*..*........*..**..*..**..*....*
*.*...**..*.......*..*.*..*.......*..**...*...**..*...*
*.*...*.*.........*..*.*..*.........*.*...*...*.*.....*
*.*...**.*.*......*..*.*..*......*.*.**...*...**.*.*..*
*.*...*..*.*......*..*.*..*......*.*..*...*...*..*.*..*
*.*...*****.*..**..*.*.*.*..**..*.*****...*...*****.*.*
*.*.******.**.*****..*.*..*****.**.******.*.******.**.*
*.*..................*.*..................*...........*
*.********************.********************...........*
*.....................................................*
*******************************************************
2 3
a 2 3
.*.
***
b 3 3
.*.
***
.*.
2 3
.*.
***
4 3
***
*.*
*.*
***
9 13
************.
*..........*.
*.......*..*.
*...*..***.*.
*..***.....*.
*...*......*.
*..........*.
************.
.............
3 1
a 2 2
.*
**
b 2 1
*
*
c 3 3
***
*.*
***
11 16
****************
*..............*
*....*********.*
*....*.......*.*
*.*..*.***...*.*
*.**.*.*.*.*.*.*
*....*.***.*.*.*
*....*.......*.*
*....*********.*
*..............*
****************
0 0

예상 출력

[[ab][ab]a]
#
a
[]
[ba]
#
[[cb]a]
#

예제 2

입력

4 1
a 2 2
*.
**
b 2 2
**
.*
c 3 3
***
*.*
***
d 1 1
*
7 13
......*******
......*.....*
......*.***.*
......*.*.*.*
......*.***.*
*..**.*.....*
**..*.*******
0 0

예상 출력

ab[c]
#

예제 3

입력

4 4
a 2 2
*.
**
b 2 2
**
.*
c 3 3
***
*.*
***
d 1 1
*
4 3
***
*.*
*.*
***
8 7
*******
*.....*
*.***.*
*.*.*.*
*.*.*.*
*.***.*
*.....*
*******
5 5
*****
*...*
*.*.*
*...*
*****
3 3
***
*.*
***
0 0

예상 출력

[]
[[]]
[d]
c
#

예제 4

입력

4 3
a 2 2
*.
**
b 2 2
**
.*
c 3 3
***
*.*
***
d 1 1
*
2 5
.*.**
**.*.
7 12
...*********
...*.......*
...*.***...*
...*.*.*...*
...*.***.*.*
**.*.......*
*..*********
6 13
*********....
*.......*....
*..*.**.*....
*.**.*..*.***
*.......*.*.*
*********.***
0 0

예상 출력

ba
[cd]b
[ba]c
#