Como resultado de mirar muchos videos de ingeniería "hágalo usted mismo" en internet, el Granjero Juan ha liberado un robot auto-replicante en su granja.

La granja puede ser representada con una cuadrícula ~N \cdot N~ grid donde cada celda de la cuadrícula o está vacía u ocupada con una roca, y todos los cuadrados del borde tienen una roca. Algunas celdas vacias se designan como posibles ubicaciones incialea para el robot.

El Granjero Juan ubica inicialmente al robot en una de las posicones iniciales posibles. En cada hora que sigue, todas las copias del robot se mueven en una masa coordenada en la misma dirección, o norte, sur, este u oeste. Después de ~D~ horas, cada copia del robot se replica - un robot en la celda ~(x,y)~ que se replica crea nuevas copias en las celdas ~(x+1,y), (x-1,y)~, ~(x,y+1)~, y ~(x,y-1)~; el robot original permanece en ~(x,y)~. Con el tiempo, varios robots podrían ocupar la misma celda.

Si moverse o replicarse causaría que cualquiera de los robots se muevan en una roca, entonces todos los robots se apagan inmediatamente. Note que esto implica que los robots deben eventualmente apagarse, debido a que el borde de la granja está lleno de rocas.

Ayude a las vacas a encontrar el número de cuadrados desocupados que podrían potencialmente en algún momento en el tiempo tener un robot.

Entrada

La primera línea contiene dos enteros separados por espacio ~N~ y ~D~. Cada una de las ~N~ líneas de entrada cotienen ~N~ caracteres. Cada caracter es uno de '.', 'S', o '#'. Ambos caracters '.' y 'S' representan celdas desocupadas, con 'S' denotando una posición inicial posible del robot. '#' denota una roca. Todos los caracteres en la primera y en la última fila y en la primera y en la última columna son '#'.

Salida

Un entero contando el número de celdas que podrían en algún momento del tiempo tener un robot.

Restricciones

• ~3 \leq N \leq 1000~
• ~1 \leq D \leq 10^9~

Ejemplo #1 de Entrada

10 1
##########
#........#
#S.......#
#........#
##########
#S....S..#
##########
##########
##########
##########

Ejemplo #1 de Salida

15

En el diagrama siguietne, las x's denotan robots.

Posiciones que podrían ser ocupadas por robots:

##########
#xxx.....#
#xxxx....#
#xxx.....#
##########
#xx..xxx.#
##########
##########
##########
##########

Una secuencia posible de eventos podría ser como sigue:

• GJ coloca el robot en la posición incial más arriba ya la izquierda.
• El robot se mueve una unidad a la derecha.
• El robot se replica.
• Todos los robots se mueven una unidad a la derecha.
• Otra replicación causaría que una copia de un robot se moviera en una roca, entonces el proceso termina.

``

##########    ##########    ##########    ##########
#........#    #........#    #.x......#    #..x.....#
#x.......#    #.x......#    #xxx.....#    #.xxx....#
#........#    #........#    #.x......#    #..x.....#
########## -> ########## -> ########## -> ##########
#........#    #........#    #........#    #........#
##########    ##########    ##########    ##########
##########    ##########    ##########    ##########
##########    ##########    ##########    ##########
##########    ##########    ##########    ##########

``

Ejemplo #2 de Entrada

10 2
##########
#.#......#
#.#......#
#S.......#
#.#......#
#.#......#
##########
##########
##########
##########

Ejemplo #2 de Salida

28

Posiciones que podrían ser ocupadas por robots:

##########
#x#.xxx..#
#x#xxxxx.#
#xxxxxxxx#
#x#xxxxx.#
#x#.xxx..#
##########
##########
##########
##########

Ejemplo #3 de Entrada

10 2
##########
#.S#.....#
#..#.....#
#S.......#
#..#.....#
#..#.....#
##########
##########
##########
##########

Ejemplo #3 de Salida

10

Posiciones que podrían ser ocupadas por robots:

##########
#xx#.....#
#xx#.....#
#xxx.....#
#xx#.....#
#x.#.....#
##########
##########
##########
##########

**USACO 2020 December Contest, Gold. Problem 1. Replication.