Descripción

El cuartel general ha enviado un equipo de espías altamente entrenados para infiltrarse en la Fábrica de Bastones de Caramelo y descubrir el secreto de las deliciosas y coloridas golosinas. Aunque la moral es alta, la victoria no está asegurada: hay un escuadrón de guardias de élite que ha establecido una estrecha vigilancia sobre todo el recinto.

El plano del recinto puede modelarse como una cuadrícula rectangular de caracteres. Cada caracter es igual a uno de los siguientes:

• # que indica una celda de pared

• . que indica una celda del piso que no está ocupada por una persona

• P que indica una celda del piso que está ocupada por un espía o un guardia (nótese que los espías se han puesto uniformes robados, y ahora son indistinguibles de los guardias)

Sorprendentemente, el Cuartel General ha extraviado su registro de misiones, y nadie puede recordar el número exacto de espías que fueron enviados al complejo. La única información que tiene el Cuartel General es la siguiente:

• Un guardia nunca estará directamente adyacente a (es decir, compartirá frontera con) más de una celda del muro. porque, de lo contrario, su visión del recinto estaría demasiado obstruida.

• Un espía siempre estará directamente adyacente a al menos una celda de pared, porque, de lo contrario, estaría demasiado expuesto.

El cuartel general ha entrado en el centro de mando y ahora tiene acceso a la señal de vídeo de todo el complejo. Para no poner más en peligro la misión, deben determinar el número de espías que enviaron a la Fábrica de Dulces con la mayor precisión posible.

Tarea

Dado el plano del recinto, determine el número mínimo y máximo posible de espías que formaban parte del equipo enviado por el Cuartel General.

Entrada

La primera línea de entrada contiene dos enteros, ~n~ y ~m~ (~1 \le n \le 100~; ~1 \le m \le 100~), que representan la altura y anchura de la planta del recinto, respectivamente. Una descripción del plano de la planta figurará en las ~n~ líneas siguientes. Cada una de las ~n~ líneas contendrá ~m~ caracteres. Se garantiza que cada carácter del plano es un #, un . o una P.

Salida

Salida de dos enteros separados por espacios: el número mínimo y máximo posible de espías que fue enviado por el cuartel general.

Restruicciones

• (40 puntos), ~n \le 50~; ~n \le 100~
• (60 puntos), en otros casos.

Ejemplos de entrada y salida

Entrada de Entrada #1

5 5
#####
#P..#
#.PP#
#...#
#####

Ejemplo de Salida #1

1 2

Entrada de Entrada #2

4 4
###P
P#PP
P#PP
####

Ejemplo de Salida #2

4 6

Entrada de Entrada #3

7 7
#######
#..P..#
#.....#
#P...P#
#.....#
#..P..#
#######

Ejemplo de Salida #3

0 4

Entrada de Entrada #4

5 7
#######
#.....#
#..P..#
#.....#
#######

Ejemplo de Salida #4

0 0