Problema B - Escolas

Metropolis é uma enorme cidade famosa pelos muitos programadores que lá vivem. Em tempos de crise, o presidente da Câmara Municipal está à procura de uma maneira de reduzir a despesa pública e pensou que uma das melhores formas de o fazer seria encerrar uma das muitas escolas existentes, garantido contudo que toda a população continua com uma escola por perto.

A cidade tem uma malha ortogonal de estradas tal como Nova Iorque, ou seja, as ruas e avenidas são perpendiculares umas às outras formando um extenso reticulado. Cada quarteirão da cidade pode ser então identificado pela sua posição neste reticulado, que funciona como se fosse uma matriz. Os quarteirões são numerados de norte para sul e de oeste para este. Quando se diz que um quarteirão está na posição (Y,X), estamos a dizer que está na Y-ésima posição a contar de cima (cima é o norte) e na X-ésima posição a contar da esquerda (a esquerda é o oeste). Os quarteirões são também caracterizados pela sua utilização social. No nosso caso, apenas nos interessa saber quais são os que têm escolas (quarteirões escolares) e os que têm casas (quarteirões residenciais).

A figura seguinte ilustra um exemplo de uma cidade de 5 linhas por 7 colunas com os respectivos quarteirões escolares (letra 'E') e residenciais (letra 'R'):

Os habitantes de Metropolis deslocam-se pela cidade usando as estradas do reticulado. Assim, a distância entre dois quarteirões é dada pela soma da diferença entre as posições horizontais e a diferença entre as posições verticais. Por exemplo, a distância entre o quarteirão (1,6) e (2,2) é de 5 = 1+4. De modo a minorar o impacto do encerramento da escola, o presidente da câmara quer calcular a que distância da escola mais próxima ficaria o quarteirão residencial mais afastado de qualquer escola. Mais precisamente, ele quer saber qual é o quarteirão escolar que, quando encerrado, tem como resultado uma cidade onde o quarteirão residencial mais afastado de qualquer escola fica o mais perto possível de uma escola.

Usando a cidade exemplo da figura anterior, estas seriam as 4 possibilidades de encerramento de escolas. Em cada uma delas são indicados a vermelho os quarteirões residenciais mais distantes de uma escola e a respectiva distância à escola mais próxima.

Neste caso a melhor hipótese seria encerrar a escola em (1,6), uma vez que o quarteirão mais longe de uma escola ficaria à distância 3. Todas as outras hipóteses de encerramento teriam como consequência uma maior distância do quarteirão residencial mais longínquo.

O Problema

Dadas as dimensões de uma cidade (L linhas por C colunas), a localização dos quarteirões escolares e a localização dos quarteirões residenciais, a tua tarefa é calcular o melhor quarteirão escolar a encerrar de modo a minimizar a distância à escola mais próxima do quarteirão residencial mais longínquo (o que fica mais longe de qualquer escola),

Input

A primeira linha de input contém dois números inteiros L e C indicando as dimensões da cidade. L dá o número de linhas e C o número de colunas (1 ≤ L,C ≤ 500).

Seguem-se exactamente L linhas, cada uma delas com C caracteres descrevendo a cidade: a letra 'E' representa um quarteirão escolar, a letra 'R' representa um quarteirão residencial e o caracter '.' (ponto) representa um outro tipo de quarteirão.

É garantido que o número de quarteirões escolares é sempre superior a 1 e inferior ou igual a 20 000. É também garantido que o número de quarteirões residenciais é maior que zero.

Output

O output deve conter duas linhas. A primeira linha deve conter dois números inteiros Y e X separados por um único espaço indicando qual a escola que deve ser retirada. A segunda linha deve conter um único número inteiro D indicando a distância a que ficam os quarteirões residenciais mais longínquos (os que ficam mais longe de qualquer escola).

Caso existam várias escolhas óptimas (ou seja, que correspondem a um mesmo D mínimo) deves escolher aquela que fica mais a norte - menor Y - e em caso de novo empate aquela que fique mais a oeste - menor X.

Nota sobre a Avaliação

Para um conjunto de casos de teste valendo 50% dos pontos, o número de linhas L e o número de colunas C é inferior ou igual a 50 e o número de quarteirões escolares é inferior ou igual a 200.

Exemplo de Input

5 7
.R.RRE.
RE.RR..
R....E.
..RR..R
R.RE..R

Exemplo de Output

1 6
3