该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

有一个 $n\times m$ 的地图。地图中包含三种位置：

• `.` 表示空地；
• `#` 表示障碍物；
• `S` 表示感染源。

第 $0$ 天时，所有感染源均已经被感染。此后每天，感染都会从已经感染的位置向上、下、左、右四个方向扩散一格。感染不能进入或穿过障碍物。

给定整数 $k$，求经过 $k$ 天以后，还有多少个最初为空地且没有被感染的位置。

输入格式

第一行三个整数 $n,m,k$。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，表示地图。

输出格式

输出一个整数，表示经过 $k$ 天后仍未被感染的空地数量。

样例 1

输入：

5 5 2
S....
.##..
.....
..#..
....S

输出：

11

提示与约束

数据范围

对于所有数据：

• $1\le n,m\le 1000$；
• $0\le k\le 10^9$；
• 地图中至少存在一个感染源。

来源：Luogu_U719062。本站使用重新构建的测试数据。