Piramidy

Archeolodzy poszukujący nowych odkryć postanowili skorzystać z najnowocześniejszych dostępnych środków aby odkryć ruiny ukryte w pustynnych piaskach Bajtahary. Za pomocą wojskowych satelitów szpiegowskich wykonali zdjęcia pewnego rejonu i po ich analizie odkryli, że starożytni zamieszkujący ów rejon przed 32 (a może 64, naukowcy nie są zgodni w swoich ocenach) wiekami budowali swoje domy w taki sposób, że ściany tworzyły prostokąt.

Na przykładowym zdjęciu odkryto 5 budynków:

   1        2        3        4        5
........ ........ ........ ........ .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.. ........ ........ ........ ........

Niestety, na dostarczonych zdjęciach nie jest łatwo odnaleźć kształt i rozmiar budynków, ponieważ starożytni budowali swoje nowe domostwa na miejscu starych i pozostałości murów nowych i starych domostw mieszają się jak na obrazie poniżej.

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

Jest to dobra rzecz dla archeologii, natomiast strasznie utrudnia ona analizę dostarczonych przez satelitę danych. Jednak archeolodzy dali sobie z nim radę i na podstawie odcieni elementów na dostarczonych zdjęciach są w stanie wyznaczyć kontury budynków. Twoim zadaniem jest sprawdzenie w jakiej kolejności budynki były stawiane, aby naukowcy mogli potwierdzić swoje tezy o wpływie czasu na kształty budowanych domostw.

Możesz założyć następujące rzeczy:

1. Grubość wyznaczonego budynku to zawsze 1 znak a boki nigdy nie są krótsze niż 3 znaki.
2. Zawsze możliwe jest zobaczenie na zdjęciu kawałka każdej z 4 ścian tworzących pojedynczy kontur. Narożnik konturu określa pozycję dwóch ścian.
3. Kontury będą oznaczone dużymi literami i dwa różne kontury nie będą posiadały tej samej litery jako oznaczenia.

Dane wejściowe:

Pierwsza linia danych zawiera jedną liczbę określającą liczbę bloków danych.
Każdy blok danych rozpoczyna się od dwóch linii po jednej liczbie w każdej, które to liczby określają wysokość H i szerokość zdjęcia W (w tej kolejności); 3 ≤ H,W ≤ 30. Kolejne H linii zawiera W znaków opisujących zdjęcie. Miejsca, w których nie znajduje się żaden kontur określone są znakiem '.' (kropką).

Dane wyjściowe:

Na wyjście programu mają zostać wypisane wszystkie możliwe ułożenia budynków od dołu (domostwa zbudowanego najdawniej) do góry (najnowszego dziejowo domu). Jeśli istnieje wiele możliwych ułożeń wypisz każde z nich w osobnej linii w kolejności alfabetycznej. Zawsze będzie istniało co najmniej jedno możliwe do wyznaczenia ułożenie dla każdego bloku danych. Po wszystkich możliwych odpowiedziach dla danego bloku danych wypisz jedną dodatkową linię zawierającą wyłącznie znak '#' (hash, kratka);

Przykładowe dane wejściowe:

2
9
8
.CCC....
ECBCBB..
DCBCDB..
DCCC.B..
D.B.ABAA
D.BBBB.A
DDDDAD.A
E...AAAA
EEEEEE..
10
10
..AAAAA...
..ACCCA...
..AC.CA...
..AC.CA...
..ACCCA...
..AAAAA...
..........
...BBB....
...B.B....
...BBB....
        

Przykładowe dane wyjściowe:

EDABC
#
ABC
ACB
BAC
BCA
CAB
CBA
#