You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【题目描述】

在网上观看太多机械 DIY 视频的后果就是，Farmer John 偶然在他的农场上制造了一个可以自我复制的机器人！

农场可以用一个 N×N 的方阵表示（3≤N≤1000），其中每个方格是空的或有岩石，并且所有边界上的方格均有岩石。某些没有岩石的方格被指定为机器人可能的起始位置。

Farmer John 初始将机器人放置在可能的起始位置之一。在之后的每一个小时，机器人的所有副本会沿着相同的方向移动一格，向北、向南、向东或向西。每 D 个小时（1≤D≤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' 表示一个可能的机器人起始位置。'#' 表示一块岩石。

所有第一行、最后一行、第一列、最后一列的字符均为 '#'。

【输出格式】

输出一个整数，表示可能在某个时刻含有机器人的方格数量。

【输入输出样例】

输入 #1复制

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

输出 #1复制

15

输入 #2复制

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

输出 #2复制

28

输入 #3复制

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

输出 #3复制

10

【样例说明】

样例 1 解释：

在以下的图中，x 表示机器人。

可能含有机器人的位置为：

以下是一个可能的事件序列：

FJ 将机器人放在了左上的起始位置。 机器人向右移动一个单位。 机器人进行自我复制。 所有机器人向右移动一个单位。 再一次自我复制会导致存在机器人撞到岩石，所以该过程终止。

样例 2 解释：

可能含有机器人的位置为：

样例 3 解释：

可能含有机器人的位置为：

测试点性质：

测试点 4-5 满足 D=10^9。

测试点 6-8 满足 D=1。

测试点 9-12 满足 N≤100。

测试点 13-20 没有额外限制。