Karty [A]
Limit pamięci: 256 MB
Bajtazar pracuje jako programista w latach 60. XX wieku.
Jest to praca mozolna, gdyż programy wprowadza do komputera nie za pomocą klawiatury, lecz przy użyciu kart perforowanych.
Karta rozmiaru składa się z jednakowych, prostokątnych pól ułożonych w kolumn po wierszy.
Każde z pól może zostać przedziurkowane.
Układ dziurek w karcie koduje treść programu.
Na poniższym rysunku przedstawiono przykładową kartę rozmiaru .
Dziurki w polach zostały zaznaczone czarnymi prostokątami.
Bajtazar ma już w głowie program i wie, które pola powinien przedziurkować.
Chciałby jednak przygotować kartę możliwie efektywnie.
W tym celu postanowił, że wykona prostokątną matrycę, która przyłożona do karty przedziurkuje wszystkie pola
w wybranym przez Bajtazara fragmencie rozmiaru (tj. pola należące do przecięcia kolejnych wierszy z kolejnymi kolumnami).
Rozmiar tej matrycy powinien być dobrany tak, by przy jej użyciu dało się wykonać kartę perforowaną
posiadającą dziurki dokładnie w tych miejscach, w których zaplanował je Bajtazar.
Jednocześnie, matryca powinna być jak największa.
Ponieważ pola na karcie nie są kwadratowe, matrycy nie wolno obracać (np. by otrzymać matrycę rozmiaru ).
Programowanie komputerów zajmuje dziś znacznie mniej czasu niż kiedyś, dlatego Bajtazar poprosił Cię
o napisanie programu, który wyznaczy wymiary największej matrycy, za pomocą której można zapisać jego program na karcie.
Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite oraz
().
Oznaczają one, odpowiednio, liczbę wierszy oraz kolumn na karcie perforowanej.
Kolejne wierszy zawiera opis programu Bajtazara.
Każdy z tych wierszy składa się z znaków "_" lub "X".
Znak "X" oznacza pole karty, które powinno zostać przedziurkowane, zaś "_" - pole, którego nie należy dziurawić.
Możesz założyć, że opis karty zawiera przynajmniej jeden znak "X".
Wyjście
Twój program powinien wypisać dwie liczby całkowite i opisujące wymiary matrycy, która
może posłużyć do wykonania karty opisanej w wejściu.
Iloczyn tych dwóch liczb powinien być jak największy.
Jeśli istnieje wiele poprawnych odpowiedzi, Twój program powinien wypisać tę o jak najmniejszej wartości .
Przykład
Dla danych wejściowych:
4 5
_XXX_
XXXX_
XXXXX
_XXXX
poprawną odpowiedzią jest:
2 3
Autor zadania: Jakub Łącki.