AlgoLiga 2018

Spadające słówka

Spadające słówka to łamigłówka w formie diagramu o trzech wierszach i kilkunastu kolumnach. Początkowo diagram uzupełniony jest literami i znakiem _ oznaczającym spację. Łamigłówka polega na zamianie komórek parami w obrębie kolumny tak, aby w każdym wierszu powstały wyłącznie słowa z dostępnego słownika. Zadanie polega na napisaniu programu, który będzie rozwiązywał tak zdefiniowaną łamigłówkę.

Pisząc program należy założyć, ze każda podana na wejściu łamigłówka jest rozwiązywalna oraz dla każdej łamigłówki dostępny jest słownik złożony z 43583 słów. Ponadto kazdy wiersz rozpoczyna się literą i w każdym wierszu występuje co najmniej jedno ukryte słowo, a w przypadku dwóch lub więcej słów w wierszu, rozdzielone są one pojedynczym znakiem spacji _.

Wejście
Pierwszy wiersz wejścia zawiera liczbę wyrazów w słowniku i jest ona stała. Drugi wiersz zawiera 43583 słów ze słownika, który można pobrać wyżej.
Trzeci wiersz to liczba przypadków testowych d (1 ≤ d ≤ 20) do rozpatrzenia. Dalej opisane są przypadki testowe. Każdy przypadek to cztery wiersze. W pierwszym wierszu podana jest liczba n (10 ≤ n ≤ 20) oznaczająca liczbę kolumn diagramu. Kolejne trzy wiersze opisują diagram, na które składają się ciągi długości n złożone z małych liter i znaku _ oznaczającego spację.

Wyjście
Dla każdej łamigłówki należy wypisać trzy wiersze przedstawiające rozwiązany diagram. Ponieważ łamigłówki mogą posiadać wiele rozwiązań, należy znaleźć takie, którego porządek leksykograficzny ciągów w wierszach (od góry do dołu) będzie najmniejszy. Między przypadkami testowymi dozwolony jest dodatkowy znak końca linii.

Przykład

Wejście

43583
abak abaka abakan abakus ...
2
10
kajkz_s___
fonduo____
barnyr____
13
koto_ktokoat_
kttekokotkow_
koo_k_t__kt_a

Wyjście

bardzo____
fajny_____
konkurs___

kotek_kotka__
koto_kto_kot_
kto_kot_kotwa