Problem B. I am angry

Situation

Provincists' effort is finally wasted. Shun failed to use the love letter generator to get Choi a girl friend. Choi has become more abnormal and aggressive.

A few days ago, Choi invited a tutor, Angel, to meet at a computing laboratory today. Choi's assignment had been graded unexpectedly low. He planned to attack Angel once she arrives.

Angel has just arrived the laboratory. Choi is now taking out his super-heavy-and-dense 12-inch iBook as a weapon, trying to attack her!

No. This time, help Angel. Tell her the shortest action chain to escape to the door (right-top corner of the map). The laboratory is filled with chairs so it is not an easy task.

Angel can move in four directions. Sometimes the seats may be blocking her way out. It is possible for her to pull a seat at one time (without hitting other chairs) to get her way out:

move_up
move_down
move_left
move_right
pull_up
pull_down
pull_left
pull_right

The 8 actions are having the same cost. It does not matter whether Angel is pulling a chair or not. All of the action chains which are as short as the model answer are considered valid.

Input

Please read from the standard input. It is not necessary to use any fopen() or ifstream.

You are given a 15 * 15 map, with the following symbols:

*: Angel's location
#: Unmovable objects (e.g. wall, heavy tables, etc)
$: Movable seats.

The borders of the map are walls.

Output

Please output to the standard output. Don't return any non-zero in the main() or you will be treated as having run-time error.

You have to output the maps at different time, including the given map, and the snapshot that she arrives at the right-top corner. Leave an empty line after each snapshot.

Don't worry about the possibilities that there are more than one shortest action chains. The answer can be manually verified.

Sample Input

###############
######       $#
#           * #
# $ $     $ $ #
######   ######
#             #
# $ $     $ $ #
######   ######
#             #
# $ $     $ $ #
######   ######
#             #
# $ $     $ $ #
######   ######
###############

Sample Output

###############
######       $#
#           * #
# $ $     $ $ #
######   ######
#             #
# $ $     $ $ #
######   ######
#             #
# $ $     $ $ #
######   ######
#             #
# $ $     $ $ #
######   ######
###############

###############
######      *$#
#             #
# $ $     $ $ #
######   ######
#             #
# $ $     $ $ #
######   ######
#             #
# $ $     $ $ #
######   ######
#             #
# $ $     $ $ #
######   ######
###############

###############
######     *$ #
#             #
# $ $     $ $ #
######   ######
#             #
# $ $     $ $ #
######   ######
#             #
# $ $     $ $ #
######   ######
#             #
# $ $     $ $ #
######   ######
###############

###############
######      $ #
#          *  #
# $ $     $ $ #
######   ######
#             #
# $ $     $ $ #
######   ######
#             #
# $ $     $ $ #
######   ######
#             #
# $ $     $ $ #
######   ######
###############

###############
######      $ #
#           * #
# $ $     $ $ #
######   ######
#             #
# $ $     $ $ #
######   ######
#             #
# $ $     $ $ #
######   ######
#             #
# $ $     $ $ #
######   ######
###############

###############
######      $ #
#            *#
# $ $     $ $ #
######   ######
#             #
# $ $     $ $ #
######   ######
#             #
# $ $     $ $ #
######   ######
#             #
# $ $     $ $ #
######   ######
###############

###############
######      $*#
#             #
# $ $     $ $ #
######   ######
#             #
# $ $     $ $ #
######   ######
#             #
# $ $     $ $ #
######   ######
#             #
# $ $     $ $ #
######   ######
###############

Special Note

It is an offense to injure any tutors.