1654.Treasure House

Time Limit: 1000 MS    Memory Limit: 32768 KB
Total Submission(s): 116    Accepted Submission(s): 36


Occasionally, WWY finds a treasure map with size of .

This map consists of only two characters: '$' and ‘#’.

'$': An empty cells(WWY can walk on it).

'#': A cell full of rock(WWY cannot walk on it).

WWY now is in coordinates (top left corner) and the treasure house is in coordinates (lower right corner).

Every second, WWY can chose one direction from and fly one step towards it.


Can you help WWY find the path to the treasure house with the minimum seconds?


The first line of input is an integer and an integer .

lines follwed, each line has characters .


The output has two lines.

The first line prints the minimum seconds to arrive the treasure house.

The second line prints several characters for representing . If there are many paths with the same minimum seconds, please print the path with maximum dictionary.

It is guarantees that there must have a path for arriving the treasure house.

Sample Input

3 4

Sample Output



Arriving from to , the minimum seconds is .

The paths with the minimum seconds are and , and is the maximum dictionary path with the minimum seconds.