Description

Mzc’s family is very rich (just kidding). He has $n$ male servants (those who did the first installment already know). He gathered them together, and they decided to play hide-and-seek. Now mzc is going to search for his male servants. Let’s help out!

Since there are not many male servants, and mzc is very good at finding people, each time he only needs to find one male servant.

Input Format

The first line contains two integers $n$ and $m$, indicating there are $n$ rows and $m$ columns where the male servants can hide.

Then follow $n$ lines with $m$ columns forming a matrix: m denotes mzc, d denotes a male servant, # denotes an impassable cell, and . denotes an empty cell.

Output Format

A single line. If there is a solution: output one integer $sum$, which is the minimal number of moves to find a male servant.

If there is no solution: output No Way!.

5 6
.#..#.
....#.
d.....
#####.
m.....

12

Hint

$3 \leq m,n \leq 2000$.

Because mzc is in a great hurry, he can only wait for 1 s.

Translated by ChatGPT 5