Problema B - Publicidade via Satélite

Nos dias de hoje é comum o acesso a uma ferramenta de mapas online sempre que desejamos planear uma viagem ou simplesmente visitar "virtualmente" um determinado sítio. Certos da massificação dessa utilização, os responsáveis pelo marketing não perderam a oportunidade de a rentabilizar. Como uma das vistas mais comuns é a de satélite, com imagens vistas completamente por cima, arranjaram maneira de criar uma publicidade que sobressai precisamente quando estamos a visualizar o mapa online.

Tu trabalhas para a SONI (SOluções Nacionais Inteligentes), uma enorme empresa tecnológica cujo logotipo principal assenta na figura geométrica de um losango. É sabido que o maior fornecedor de imagens de satélite vai amanhã actualizar as imagens da região, tirando novas fotografias de satélite. De acordo com o plano, a SONI quer criar um enorme logotipo no chão, num terreno inutilizado que possui. O problema é que o terreno está cheio de frondosas árvores, algumas das quais de espécies protegidas, que se fossem cortadas fariam levantar um coro de protestos dos ecologistas, da população local e das autoridades. Sendo assim, é preciso descobrir qual o maior losango que se pode criar sem deitar abaixo nenhuma árvore. Fazer isso à mão é muito demorado e pouco rigoroso e por isso a SONI veio encomendar-te o serviço!

O mapa do terreno é dado como um quadriculado de C colunas por L linhas, onde '.' representa uma quadrícula vazia e 'A' representa uma árvore. Um exemplo de um mapa de 9 colunas por 6 linhas (com as colunas e linhas numeradas começando do topo esquerdo) seria:

 
1
2
3
4
5
6
7
8
9


1
A 
.
.
.
A 
.
.
A 
.


2
.
.
.
A 
.
.
.
.
.


3
.
.
.
.
A 
.
.
.
A 


4
.
.
.
.
.
.
.
.
.


5
.
.
.
.
A 
.
.
.
.


6
A 
.
.
.
.
A 
.
.
A 

O losango que se quer desenhar é uma figura geométrica com quatro lados de igual comprimento, com os lados a serem paralelos dois a dois. A empresa apenas quer losangos "perfeitos" que podem ser vistos na figura seguinte, detalhando um losango de tamanho 1, um de tamanho 2, outro de tamanho de 3 e finalmente um de tamanho 4. O "tamanho" do losango é representando pela medida do lado:

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
#
.
.
.
.


.
.
.
.
.
.
.
.
.
.
.
#
.
.
.
.
.
.
#
#
#
.
.
.


.
.
.
.
.
#
.
.
.
.
#
#
#
.
.
.
.
#
#
#
#
#
.
.


.
#
.
.
#
#
#
.
.
#
#
#
#
#
.
.
#
#
#
#
#
#
#
.


.
.
.
.
.
#
.
.
.
.
#
#
#
.
.
.
.
#
#
#
#
#
.
.


.
.
.
.
.
.
.
.
.
.
.
#
.
.
.
.
.
.
#
#
#
.
.
.


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
#
.
.
.
.


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

Para o mapa indicado anteriormente, o maior losango que se pode criar sem deitar abaixo nenhum árvore tem tamanho 3 e está indicado na figura seguinte, com o seu ponto superior na intersecção da 3ª coluna com a 2ª linha:

 
1
2
3
4
5
6
7
8
9


1
A 
.
.
.
A 
.
.
A 
.


2
.
.
#
A 
.
.
.
.
.


3
.
#
#
#
A 
.
.
.
A 


4
#
#
#
#
#
.
.
.
.


5
.
#
#
#
A 
.
.
.
.


6
A 
.
#
.
.
A 
.
.
A 

Nota que para um caso geral, o tamanho máximo do losango é apenas limitado pelo mapa. Caso existam vários losangos de tamanho máximo possível, a SONI decidiu que deves escolher aquele cujo ponto superior esteja o mais acima possível, ou seja, com o menor número de linha possível. Caso subsista um empate, deves escolher o losango que esteja o mais à esquerda possível, ou seja, com o menor número de coluna possível. Por exemplo, no mapa dado, um losango de tamanho 3 podia também ser criado com o ponto superior na intersecção da 7ª coluna com a 2ª linha. No entanto, pelas regras de desempate, preferimos o losango anteriormente indicado, que está nas mesmas linhas, mas mais à esquerda.

O Problema

Dado um mapa com C colunas e L linhas e a localização de um conjunto de árvores nos limites desse mapa, a tua tarefa é descobrir qual o maior losango que é possível criar nesse mesmo mapa que não toque em nenhuma das árvores. Caso existam vários losangos de tamanho máximo, deves escolher aquele que estiver o mais acima possível e em caso de novo empate deves escolher o que estiver mais à esquerda.

Input

Na primeira linha do input vêm dois números inteiros C e L, separados por um espaço, indicando o número de colunas e o número de linhas do mapa, respectivamente.

Seguem-se exactamente L linhas, cada uma contendo exactamente C caracteres, descrevendo o mapa. Cada um dos caracteres pode ser:

• '.', indicando que a quadrícula está vazia;
• 'A', indicando que a quadrícula tem uma árvore.

É garantido que em todos os testes haverá pelo menos uma quadrícula sem árvore.

Output

O output deve ser constituído exactamente por duas linhas. A primeira deve conter um único número inteiro indicando o tamanho do maior losango que é possível de criar no mapa. A segunda linha deve conter dois números inteiros, separados por um espaço, indicando respectivamente a coluna e a linha do ponto superior do losango a criar.

Se existirem vários losangos possíveis de tamanho máximo, deves escolher aquele estiver o mais acima possível (menor número de linha) e em caso de novo empate aquele que estiver o mais à esquerda (menor número de coluna).

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 50% dos pontos, o número de linhas e de colunas é inferior ou igual a 25.

Exemplo de Input

9 6
A...A..A.
...A.....
....A...A
.........
....A....
A....A..A

Exemplo de Output

3
3 2