Frame Stacking

Time limit1sMemory limit128 MB

Summary

Given a picture of several stacked lettered frames on a grid, recover the bottom-to-top stacking order, printing all valid orders alphabetically.

Level: Medium7 of 10
Topics: Graph, Topological sort, DFS, Implementation
Solved: No attempts yet

Problem

Consider the following five picture frames placed on a 9 x 8 grid.

........ ........ ........ ........ .CCC....
EEEEEE.. ........ ........ ..BBBB.. .C.C....
E....E.. DDDDDD.. ........ ..B..B.. .C.C....
E....E.. D....D.. ........ ..B..B.. .CCC....
E....E.. D....D.. ....AAAA ..B..B.. ........
E....E.. D....D.. ....A..A ..BBBB.. ........
E....E.. DDDDDD.. ....A..A ........ ........
E....E.. ........ ....AAAA ........ ........
EEEEEE.. ........ ........ ........ ........

   1         2        3        4        5

Now stack them on top of one another, starting with frame 1 at the bottom and ending with frame 5 on top. Wherever one frame covers another, it hides the covered part of the frame below. Looking down at the stack of five frames, we see the following.

.CCC....
ECBCBB..
DCBCDB..
DCCC.B..
D.B.ABAA
D.BBBB.A
DDDDAD.A
E...AAAA
EEEEEE..

In what order were the frames stacked, from bottom to top? For this picture the answer is EDABC. Your task is to determine the bottom-to-top stacking order given a picture of the stacked frames. The rules are:

Every frame is exactly one character thick, and no side is shorter than three characters.
At least one part of each of the four sides of every frame is visible. A corner reveals two sides.
Each frame is labeled with a distinct capital letter; no two frames share a letter.

Input

Each block of input begins with the height $h$ ( $h \le 30$ ) on the first line and the width $w$ ( $w \le 30$ ) on the second line. The picture of the stacked frames then follows as $h$ lines of exactly $w$ characters each.

The input may contain several such blocks, one immediately after another with no blank lines between them. Process every block in order.

Output

For each block, print the letters of the frames in the order they were stacked from bottom to top. If more than one stacking order is consistent with the picture, print all of them, one per line, in alphabetical order. Every block has at least one valid ordering. Print the results for all blocks in sequence, with no blank lines anywhere (not even between blocks).

Examples4

Example 1

Input

9
8
.CCC....
ECBCBB..
DCBCDB..
DCCC.B..
D.B.ABAA
D.BBBB.A
DDDDAD.A
E...AAAA
EEEEEE..

Expected output

EDABC

Example 2
Input
```
3
3
AAA
A.A
AAA
```
Expected output
```
A
```
Example 3
Input
```
3
7
AAA.BBB
A.A.B.B
AAA.BBB
```
Expected output
```
AB
BA
```

Example 4

Input

6
6
AAAA..
A..A..
A.BBBB
AABA.B
..B..B
..BBBB

Expected output

AB