Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
86 - ZOJ Monthly, January 2010 - E
Never End

Time Limit: 2 Seconds      Memory Limit: 32768 KB

"Never End" is a flash game. Here, we consider a simplified version of it. A world is represented by a board of N by M, where each grid may be empty or a block. The world is surrounded by blocks with one empty grid being the exit. The player can use the following four operations to escape from the world (get to the exit).

  • Step Left one grid.
  • Step Right one grid.
  • Rotate Left the world.
  • Rotate Right the world.

However, the player can not get into the blocks. After one operation, the player will fall off until he reaches a block or gets to the exit. Refer to the figure for a more intuitive understanding of the four operations.

Input

There are no more than 50 cases. Each case begins with a line with two integers N (3 <= N <= 500) and M (3 <= M <= 500), the height and width of the world respectively. The next N lines describe the world. Each of the N lines contains exactly M characters. A '#' denotes a block. The 'E' denotes the exit, which is guaranteed to be at one edge of the world excluding the corners. The '|' represents the player. You can assume that the player stands on a block at first.

Process to the end of the file.

Output

For each case, print a line with the minimal number of operations that the player can escape from the world. If it is impossible for the player to escape, print "Can not escape!" instead.

Sample Input

9 9
#########
# #     #
# # ### #
# #  #  #
E ## #  #
# #  ####
#   ##  #
#   |   #
#########
7 7
#######
###|  #
####  #
E     #
####  #
###   #
#######

Sample Output

4
Can not escape!

Author: GAO, Yuan
Source: ZOJ Monthly, January 2010
Submit    Status