Problema A - Tabuleiros Axadrezados

A X&X (Xadrez & Xadrez, Lda.) é uma grande empresa industrial que produz e exporta para todo o mundo tabuleiros para jogos como o Xadrez ou as Damas. Os tabuleiros são fabricados por uma máquina chamada MUT (Máquina Universal de Tabuleiros). A MUT é alimentada com pequenas células quadradas de duas cores e fabrica enormes tabuleiros retangulares, por justaposição dessas células. Esses tabuleiros são depois cortados em retângulos mais pequenos, com a dimensão desejada.

A X&X está interessada apenas em tabuleiros com a forma de retângulos axadrezados. Dizemos que um retângulo é axadrezado se não contiver duas células adjacentes com a mesma cor (células adjacentes são aquelas que têm um lado comum). A figura seguinte mostra quatro retângulos axadrezados:

Infelizmente a MUT tem um "bug" que faz com que por vezes algumas das células saiam com as cores trocadas, fazendo com que o tabuleiro produzido não tenha um padrão axadrezado perfeito. A figura seguinte mostra um tabuleiro defeituoso:

Apesar de este tabuleiro estar defeituoso, tem partes boas (ou seja, subretângulos axadrezados perfeitos), que se podem aproveitar, cortando o tabuleiro estrategicamente. De entre todos as partes boas, as mais valiosas são as de maior área. A figura seguinte mostra um tabuleiro defeituoso com quatro retângulos bons, todos com área 12. Para o caso deste tabuleiro, esta é a melhor área que se consegue arranjar, e estes são os únicos retângulos bons com essa área.

De forma a otimizar o seu processo de fabrico, a X&X pretende automatizar o identificação dos retângulos bons de área máxima num tabuleiro axadrezado defeituoso. Estes retângulos podem ser tão pequenos como uma única célula, ou serem tão grandes como todo o tabuleiro. Tens de ajudá-los a realizar esta importante tarefa!

O Problema

Dado um tabuleiro retangular inicial constituído por L linhas e C colunas de células de duas cores diferentes, uma clara outra escura, a tua tarefa é descobrir qual a área máxima de um subretângulo axadrezado, bem como o número de subretângulos axadrezados diferentes cuja área é igual à área máxima.

Input

A primeira linha contém dois inteiros L e C, separados por um único espaço, indicando respectivamente o número de linhas e o número de colunas do tabuleiro.

As L linhas seguintes representam a constituição do tabuleiro. Cada uma dessas linhas contém C caracteres que podem ser '#', significando uma célula escura, ou '.', significando uma célula clara.

Output

O output é constituído por uma linha na qual existem dois números separados por um espaço: o primeiro indica a área máxima e o segundo indica o número de subretângulos axadrezados que têm área máxima.

Restrições

São garantidos os seguintes limites em todos os casos de teste:

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 40% dos pontos, acontece sempre que L e C são menores ou iguais a 20.

Para um conjunto de casos de teste valendo 60% dos pontos, acontece sempre que L e C são menores ou iguais a 80.

Para um conjunto de casos de teste valendo 80% dos pontos, acontece sempre que L e C são menores ou iguais a 300.

Exemplo de Input 1

8 8
.#.###.#
#.#.##.#
.#.#..#.
.#.#.#.#
.##.#.#.
#..#.##.
...#...#
#.#.#.#.

Exemplo de Output 1

12 4

Explicação do Input/Output 1

Corresponde à figura do enunciado.

Exemplo de Input 2

4 6
....#.
.....#
..#...
##....

Exemplo de Output 2

4 2

Explicação do Input/Output 2