Yi Kai has overslept and realized that he has very little time left to attend a very important event! Having recently moved, he takes out a map to navigate through his new neighbourhood to reach his destination. The map shows that the neighbourhood is arranged in a grid of size by , with a
. indicating a walkable path which takes 1 minute to walk across, and an
X indicating a building. He takes out his marker, looks around his surroundings, and marks his current position with an
s on the map. Then, he finds his destination, and marks an
e on it. He looks at the map again, but the number of possible routes to his destination overwhelms him! Help Yi Kai find out how much time he will need to reach his destination if he uses the shortest possible route!
(Inspired by Yi Kai oversleeping before previous NOI trainings)
The first line will contain two integers, , and .
The next lines will contain characters each, one of
A single integer, the minimum time he requires to reach his destination in minutes, or if it is not possible and he has to call for a helicopter.
Sample Input 1
4 4 s... .... .... ...e
Sample Output 1
Sample Input 2
3 4 XXXe .... sXXX
Sample Output 2