在处理完数字之后，龙 Evirir 太累了，于是他决定玩一个电子游戏。

Evirir 正在玩一款名为 Escape 的电子游戏！

游戏发生在一个有 $N$ 行 $M$ 列的网格上。行从上到下编号为 $1, 2, \dots, N$，列从左到右编号为 $1, 2, \dots, M$。第 $i$ 行第 $j$ 列的格子记为 $(i, j)$。如果两个不同的格子有公共边，则称它们相邻（因此每个格子最多与 4 个格子相邻：上、下、左、右）。形式化地说，格子 $(i, j)$ 与 $(i - 1, j)$、$(i + 1, j)$、$(i, j - 1)$、$(i, j + 1)$ 相邻（如果这些格子存在）。

网格中的每个格子属于以下四种类型之一，每种类型用一个字符表示：

• . 表示空格子
• d 表示有一只狗的格子
• e 表示一个逃生门
• # 表示墙

Evirir 想要到达一个逃生门并且避开狗。初始时，Evirir 有 2 点生命值（HP），并且位于一个非墙格子上。每一秒按以下顺序发生：

1. 如果 Evirir 的生命值小于或等于 0，则他立即失败。
2. 如果 Evirir 位于一个逃生门上（且生命值至少为 1），则他立即获胜。
3. Evirir 可以选择不动，或者移动到一个相邻且不是墙的格子。
4. 然后，每只狗可以选择不动，或者移动到一个相邻且不是墙的格子。多只狗可以移动到同一个格子。
5. 接着，对于每一只与 Evirir 位于同一格子的狗，这只狗会咬 Evirir，使其生命值减少 1，然后该狗会从网格中永久消失。

此外，在游戏开始之前，Evirir 必须先决定好他将要经过的格子序列。也就是说，他必须在不知道狗如何移动的情况下，预先固定自己的移动计划。随后，狗可以看到 Evirir 的计划并据此移动。

我们称一个格子为“必胜格子”，当且仅当它不是墙格子，并且如果 Evirir 从该格子出发，按照预先制定的计划移动，无论狗如何移动，他都能获胜。注意，Evirir 可以从逃生门格子或有狗的格子开始。

由于龙 Evirir 很懒，他请你计算网格中必胜格子的数量。

输入格式

第一行包含两个整数 $N$ 和 $M$（$1 \le N, M \le 3000$）。

接下来 $N$ 行，每行包含 $M$ 个字符，描述网格。第 $i$ 行的第 $j$ 个字符表示格子 $(i, j)$ 的类型。

输出格式

输出一个整数，表示必胜格子的数量。

子任务

• 子任务 1（11 分）：网格中至多有一只狗。
• 子任务 2（13 分）：$N = 1$
• 子任务 3（15 分）：$N, M \le 10$
• 子任务 4（15 分）：$N, M \le 40$
• 子任务 5（17 分）：至多有一个逃生门。
• 子任务 6（19 分）：$N, M \le 2000$
• 子任务 7（10 分）：无其他限制。

样例数据

standard input

4 5
...d.
.e#e.
..d#d
.e.d.

standard output

14

说明

假设我们从格子 $(4, 5)$ 出发，并选择如下路径：

...d.
.e#e.
..d#d
.XXXX

其中 X 表示所选择的路径。

在这种情况下，位于 $(4, 4)$ 的狗保持不动，而位于 $(3, 3)$ 的狗在玩家第一次移动之后立即向下移动。

游戏开始前，玩家在 $(4, 5)$，生命值为 2。

...d.
.e#e.
..d#d
.e.dP

其中 P 表示玩家当前位置。

现在他向左移动，此时在格子 $(4, 4)$ 有一只狗，因此他的生命值变为 1。同时，位于 $(3, 3)$ 的狗向下移动，网格变为：

...d.
.e#e.
...#d
.edP.

可以明显看出，在下一次移动后（玩家再次向左移动后），他将立即失败。

由此可以观察到，在考虑所有可能的路线后，格子 $(4, 5)$ 不是一个必胜格子。