Sojusze

Limit pamięci: 256 MB

W urojonym świecie znajduje się prostokątna wyspa. Ma ona mil szerokości oraz mil długości i jest podzielona na kwadratowych pól. Niektóre pola są niezamieszkałe, a w pozostałych znajdują się wioski różnych istot: elfów, ludzi, krasnoludów oraz hobbitów. Mówimy, że dwie wioski sąsiadują ze sobą, jeśli pola, na których są położone, mają wspólny bok.

Ostatnimi czasy wioski sparaliżował strach przed Bajtozłem. Aby poczuć się bezpieczniej, każda z wiosek chce zawrzeć sojusze militarne z niektórymi ze swych sąsiadów. Sojusz zawierany jest zawsze pomiędzy dwoma sąsiadami i jest porozumieniem obustronnym.

Zależnie od rasy, mieszkańcy wioski nie będą czuli się bezpiecznie, jeśli ich wioska nie zawrze konkretnej konfiguracji sojuszy:

• Elfy są pewne siebie i potrzebują dokładnie jednego sojuszu.
• Ludzie potrzebują sojuszy z dokładnie dwoma sąsiadami. Co więcej, pozostawienie dwóch przeciwległych stron ich wioski bez ochrony jest złe z taktycznego punktu widzenia. W związku z tym, wspomniani dwaj sojusznicy nie mogą być położeni po przeciwległych stronach wioski.
• Krasnoludy potrzebują sojuszy z dokładnie trzema sąsiadami.
• Hobbici są niesłychanie bojaźliwi, więc potrzebują sojuszy ze wszystkimi czterema sąsiadami.

Innymi słowy, nie licząc ludzi, każda wioska potrzebuje konkretnej liczby sojuszników i nie przejmuje się tym, którzy z sąsiadów będą jej sojusznikami. Ludzie natomiast mają dodatkowe wymaganie: sojusznicy nie mogą znajdować się po przeciwległych stronach wioski.

Warunki te muszą być spełnione niezależnie od położenia wioski na mapie. Przykładowo, wioska krasnoludów potrzebuje trzech sojuszników. Jeśli jest położona na brzegu, oznacza to, że musi mieć sojusze ze wszystkimi trzema sąsiadami. Jeśli znajduje się w rogu wyspy, jej mieszkańcy nigdy nie będą czuli się bezpiecznie.

Zadanie

Masz dany opis wyspy. Twoim zadaniem jest ustalić, czy możliwe jest takie utworzenie sojuszy, aby wszyscy mieszkańcy wyspy czuli się bezpiecznie. Jeśli odpowiedź jest pozytywna, powinieneś także znaleźć jakąś poprawną konfigurację sojuszy. W przypadku wielu możliwych konfiguracji wybierz dowolną z nich.

Specyfikacja wejścia

Pierwszy wiersz wejścia zawiera dwie liczby i oznaczające wymiary wyspy. Kolejne wierszy zawiera opis wyspy. Każdy z wierszy zawiera pooddzielanych pojedynczymi odstępami liczb od 0 do 4:

• 0 oznacza niezamieszkałe pole,
• 1 oznacza wioskę elfów,
• 2 oznacza wioskę ludzką,
• 3 oznacza wioskę krasnoludów,
• 4 oznacza wioskę hobbitów.

Ograniczenia

We wszystkich testach zachodzi .

W testach wartych łącznie 55 punktów zachodzi . Wśród nich znajdują się testy warte łącznie 15 punktów, w których zachodzi .

Kolejna grupa testów warta 10 punktów zawiera mapy, w których występują wyłącznie pola niezamieszkałe oraz wioski ludzkie. (Te testy nie są zawarte w testach wartych 55 punktów, o których mowa wyżej).

Specyfikacja wyjścia

Jeśli nie istnieje poprawne rozwiązanie, wypisz jeden wiersz z napisem "Impossible!" (bez cudzysłowów). W przeciwnym wypadku wypisz jedną z poprawnych map sojuszy w formacie opisanym poniżej.

Każde pole jest reprezentowane na wyjściu jako macierz znaków. Jeśli jest niezamieszkałe, odpowiadająca macierz powinna być wypełniona znakami '.' (kropka). W przeciwnym wypadku w środku powinien znaleźć się znak 'O' (wielka litera O) reprezentujący samą wioskę oraz znaki 'X' (wielka litera X) oznaczające konfigurację sojuszników. Pozostała część macierzy powinna być wypełniona znakami '.' (kropka).

Wszystkie możliwe konfiguracje sojuszników dla wiosek poszczególnych ras są przedstawione poniżej.

Przykłady

Dla danych wejściowych:

3 4
2 3 2 0
3 4 3 0
2 3 3 1

poprawną odpowiedzią jest:

............
.OXXOXXO....
.X..X..X....
.X..X..X....
.OXXOXXO....
.X..X..X....
.X..X..X....
.OXXOXXOXXO.
............

natomiast dla danych wejściowych:

1 2
2 1

poprawnym wynikiem jest:

Impossible!

Autor zadania: Marek Zeman.