Aaron đang chơi một trò chơi video có tên là Escape!. Trò chơi diễn ra trên một lưới có ~N~ hàng và ~M~ cột:

• Các hàng được đánh số từ ~1, 2, \dots, N~ từ trên xuống.
• Các cột được đánh số từ ~1, 2, \dots, M~ từ trái sang phải.
• Ô ở hàng ~i~ và cột ~j~ được ký hiệu là ~(i, j)~.

Hai ô khác nhau được coi là kề nhau nếu chúng có chung một cạnh (tối đa 4 ô kề nhau cho mỗi ô). Cụ thể:

• Ô ~(i, j)~ kề với ~(i-1, j)~, ~(i+1, j)~, ~(i, j-1)~, và ~(i, j+1)~ nếu các ô đó tồn tại.

Mỗi ô trên lưới thuộc một trong bốn loại dưới đây, và được biểu diễn bởi một ký tự:

• .: Ô trống.
• d: Ô có quái vật.
• e: Ô cửa thoát hiểm.
• #: Ô tường.
• Nếu một ô ban đầu chứa quái vật thì sau khi quái vật đó rời đi, ô đó là ô trống. Điều tương tự xảy ra với người chơi.

Aaron muốn an toàn đến được cửa thoát hiểm. Ban đầu, Aaron có 2 HP (tượng trưng cho ~2~ máu) và bắt đầu ở một ô không phải tường. Mỗi giây, các sự kiện sau diễn ra theo thứ tự:

1. Nếu HP của Aaron ~\leq 0~, trò chơi kết thúc và Aaron thua ngay lập tức.
2. Nếu Aaron đang ở ô cửa thoát hiểm (và HP ~\geq 1~), trò chơi kết thúc và Aaron thắng ngay lập tức.
3. Aaron có thể chọn đứng yên hoặc di chuyển đến một ô kề không phải tường.
4. Sau đó, mỗi quái vật sẽ có thể chọn đứng yên hoặc di chuyển đến một ô kề không phải tường. Nhiều quái vật có thể di chuyển đến cùng một ô.
5. Cuối cùng:
   • Mỗi quái vật ở cùng ô với Aaron sẽ tấn công Aaron, giảm HP của Aaron đi ~1~. Sau đó, quái vật đó biến mất khỏi lưới.

Yêu cầu

Trước khi bắt đầu trò chơi, do mạng quá lag, Aaron phải quyết định trước chuỗi các ô sẽ di chuyển tới. Nói cách khác, Aaron cần cố định các bước đi của mình mà không biết trước chuyển động của các quái vật. Do đó, các quái vật có thể xem kế hoạch của Aaron và di chuyển theo kế hoạch đó.

Một ô được gọi là ô lợi thế nếu và chỉ nếu:

• Nó không phải là tường.
• Nếu Aaron bắt đầu ở ô đó, di chuyển theo kế hoạch của mình, và luôn thắng bất kể cách di chuyển của các quái vật.

Nhiệm vụ của bạn là tính số lượng ô lợi thế trên lưới.

Dữ liệu vào từ tệp văn bản: MECUNG.INP

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ (~1 \leq N, M \leq 3000~).
• Tiếp theo là ~N~ dòng, mỗi dòng gồm ~M~ ký tự mô tả các ô trên lưới:
  • Ký tự thứ ~j~ trong dòng thứ ~i~ biểu diễn loại của ô ~(i, j)~.

Kết quả ghi ra tệp văn bản: MECUNG.OUT

In ra một số nguyên duy nhất: số lượng ô lợi thế.

Scoring

• Subtask 1 (~15\%~ số điểm): Chỉ có tối đa 1 quái vật trên lưới.
• Subtask 2 (~15\%~ số điểm): ~N = 1~.
• Subtask 3 (~10\%~ số điểm): ~N, M \leq 10~.
• Subtask 4 (~20\%~ số điểm): ~N, M \leq 40~.
• Subtask 5 (~10\%~ số điểm): Chỉ có tối đa 1 cửa thoát hiểm.
• Subtask 6 (~20\%~ số điểm): ~N, M \leq 2000~.
• Subtask 7 (~10\%~ số điểm): Không có ràng buộc thêm.

Example

Sample Input 1

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

Sample Output 1

14

Sample Input 2

4 3
e.e
##.
.#.
.#d

Sample Output 2

6

Explanation

Sample 1

Giả sử chúng ta bắt đầu tại ô (4,5) và lộ trình được chọn như sau:

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

X biểu thị lộ trình đã chọn.

Với lộ trình này, quái vật tại (4,4) đứng yên và quái vật tại (3,3) di chuyển xuống ngay sau khi người chơi thực hiện bước đầu tiên.

Trước khi trò chơi bắt đầu, người chơi có 2 HP và đang ở vị trí (4,5).

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

P biểu thị vị trí của người chơi.

Bây giờ, người chơi di chuyển sang trái, đến ô (4,4). Tại đây có một quái vật, nên người chơi chỉ còn 1 HP. Đồng thời, quái vật tại (3,3) di chuyển xuống và lưới bây giờ như sau:

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

Rõ ràng, người chơi sẽ thua ngay tại bước tiếp theo, ngay sau khi di chuyển sang trái. Có thể thấy rằng ô (4,5) không phải là ô lợi thế sau khi xem xét tất cả các khả năng của lộ trình.

Sample 2

Do chỉ có một quái vật trên bản đồ, chỉ cần xuất phát từ bất kì ô nào đi tới được lối thoát hiểm là Aaron có thể thoát ra.