Problem description
Jaś bardzo lubi gofry. Lubi je do tego stopnia, że postanowił kupić sobie jednego ogromnego gofra. Gofry jak wszyscy dobrze wiedzą składają się z kwadracików układające się w kształ kraty, więc ma sens aby ich długość i szerokość mierzyć właśnie tymi kwadracikami. Gofr Jasia ma wymiary N na M kwadracików.
Jako entuzjasta gofrów, Jaś ma w swojej kuchni sporą kolekcję dodatków. Jest ona na tyle duża, że półka na której ona leży ledwo wytrzymuje ciężar tejże kolekcji. No i problem w tym, że półka ta nie wytrzymała i wszystkie dodatki spadły na majestatycznego gofra Jasia.
Jasio początkowo był zdruzgotany całym zajściem, gdyż nakładanie dodatków jest jego ulubioną czynnością, ale po chwili zauważył, że część tego gofra da się jeszcze odratować. Jego planem jest wycinanie kawałków gofra, które nie mają na sobie żadnych dodatków. Oczywiście herezją byłoby przecięcie gofra przechodzące przez kwadraciki lub wycięcie gofra, który nie jest prostokątem, dlatego rozważamy tylko prostokątne kawałki gofra, które albo zawierają dany kwadracik w całości albo wcale.
Jako że możliwości wycięcia pierwszego kawałka jest całkiem dużo, to Jasio poprosił Ciebie o pomoc w policzeniu dla każdych możliwych wymiarów A i B ile jest możliwości wycięcia suchego gofra o tych wymiarach. Jasiu ma wyjątkowo wprawione oko, dlatego rozróżniamy gofry o wymiarach A na B oraz gofry o wymiarach B na A.
Wejście
W pierwszym wierszu wejścia znajdują się dwie dodatnie liczby
całkowite N i M będące odpowiednio liczbą wierszy
oraz liczbą kolumn gofra.
W następnych N wierszach
znajduje się opis gofra, w i–tym wierszu znajduje się ciąg
znaków Si
o długości M. Jeżeli Si, j
jest równe ‘#’, to kwadracik w i–tym wierszu i j–tej kolumnie gofra został pokryty
dodatkami. W przeciwnym wypadku Si, j
będzie równe ‘.’.
Wyjście
W pierwszych (jedynych) N wierszach wyjścia powinno się znaleźć po M liczb całkowitych, j–ta liczba w i–tym wierszu powinna być równa liczbie sposób wycięcia gofra o wymiarach i na j.
Ograniczenia
1 ≤ N, M ≤ 2 000.
Przykład
| Wejście | Wyjście | |
|
|