Фермер Джон зробив робота!

Ферма може бути представлена решіткою \(N\times N\) (\(3\le N\le 1000\)), де кожна комірка або порожня або заповнена скелею і всі граничні комірки заповнені скелею. Деякі порожні комірки визначені як можливі стартові позиції робота

ФД спочатку має в своєму розпорядженні робота на одній з можливих стартових позицій. Кожної наступної години всі копії робота як одна скоординована маса рухаються у певному напрямі - північ, південь, захід чи схід. Після \(D\) годин (\(1 \leq D \leq 10^9\)), кожна копія робота реплікується --- робот у комірці \((x,y)\) який реплікується, створює нові копії в комірках \((x+1,y)\), \((x-1,y)\), \((x,y+1)\), \((x,y-1)\); оригінальний робот залишається в комірці \((x, y)\). Після деякого часу багато роботів можуть зайняти одну і ту ж комірку.

Якщо рух чи реплікація призведуть до того, що робот вріжеться в скелю, тоді всі роботи негайно зупиняються. Зауважимо, з цього випливає, що роботи обов'язково колись зупиняться, оскільки межа ферми вся зі скелі.

Допоможіть коровам обчислити кількість порожніх квадратів, які потенційно у певний момент часу зможуть мати робота.

Формат вхідних даних

Перший рядок містить два розділені пропуском цілих числа \(N\) і \(D\). Кожен із наступних \(N\) рядків містить по \(N\) символів. Кожен символ - один із '.', 'S', '#'. '.' і 'S' представляють порожні комірки, причому 'S' позначає можливу стартову позицію робота. '#' позначає скелю.

Всі символи у першому та останньому рядку, у першому та останньому стовпці - '#'.

Формат вихідних даних

Одне ціле число, що містить кількість комірок, які можуть у певний момент часу мати робота.

Приклад вхідних даних

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

Приклад вихідних даних

15

У діаргамах нижче символи 'x' позначає роботів.

Позиції, які можуть бути зайняті роботами:

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

Одна з можливих послідовностей подій:

• ФД розміщує робота верхній лівий кут як стартову позицію.
• Робот рухається на одну позицію вправо
• Робот реплікується.
• Всі роботи рухаються на одну позицію праворуч.
• Наступна реплікація призведе до того, що робот вріжеться в скелю, тому процес завершується.

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

Приклад вхідних даних

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

Приклад вихідних даних

28

Позиції, які можуть бути зайняті роботами:

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

Приклад вхідних даних

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

Приклад вихідних даних

 10

Позиції, які можуть бути зайняті роботами:

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

ОЦІНЮВАННЯ:

• У тестах 4-5 \(D=10^9\).
• У тестах 6-8 \(D=1\).
• У тестах 9-12 \(N\le 100\).
• У тестах 13-20 немає додаткових обмежень.