Sokoban (warehouse keeper) is a transport puzzle in which the player pushes boxes around a maze, viewed from above, and tries to put them in designated locations. Only one box may be pushed at a time, and boxes cannot be pulled. The problem of solving Sokoban puzzles has been proven to be NP-hard.

From Wikipedia, the free encyclopedia

Probably, everybody at least once in his life played this famous game. And despite the fact the problem is NP-hard you are required to write a program which solves this puzzle for quite huge mazes; moreover, it is needed to find the best solution to the puzzle. Specifically, from all possible solutions you are to select the one with the smallest number of box pushes. From all such solutions you need the one that minimizes the total number of moves. To simplify your task a bit, only puzzles with one box will be given to your program to solve.

Maze for solving is given in the input file, maze has a size up to 100 x 100 cells. Every line of input file represents one row of the maze, all lines have the same length (and equal to the width of the maze). Space character represents a passable cell, where box and sokoban may stay, and "

#

" character represents an impassable wall. "

@

" character represents sokoban itself, "

"representsacellinwhichtheboxisinitiallylocated, and"."representsacellwheresokobanshouldputthebox.Cellsinwhichsokoban, boxanddestinationcellareinitiallylocatedarepassable.Inputfilewillcontaineveryofthecharacters"@", "" and "

.

" exactly once. Maze will be closed in a sense that sokoban will be unable to leave it.

If there is no solution for the given maze, write to the output file the only message "

Impossible.

". Otherwise write one of the best (in the abovementioned sense) solutions. Each move is represented by one of the four characters: "

u

" means moving up, "

r

" — right, "

d

" — down and "

l

" — left. Use capital letters (i.e. "

U

", "

R

", "

D

" and "

L

") to represent moves when sokoban pushes the box.

ddrruuLulD

sample input	sample output
#### #  ## #@ # #.# # #   # #####

sampleinput

sampleoutput

####
#  ##
#@ #
#.# #
# # #
#####

Impossible.