Bloxorz

Bloxorz is an interesting game and someone may have played it before. The rule of this game is simple.
This game is played on a platform constructed of many square grids. You have a cuboid whose size is 2×1×1. On the platform there is a 1×1 hole and it‘s your destination. What you have to do is move the cuboids to the hole. During the game you must keep the cuboid on the platform, if any part of cuboid is off the platform, you lose the game.
When this game starts, the cuboid stays on the platform. The way to move the cuboid is not sliding but rolling. You can move it in any of the four directions. If you want to move it right, the surfaces next to the original bottom in that direction will be the new bottom. In the following three images, the cuboid moves right twice.
Pic-1

　　　　

Input contains multiple test cases. Each test case starts with two integers N and M (0<N, M < 20), which stand for number of rows and columns of the platform. Then there comes N lines, describe the platform with ‘#’ for empty cell, ‘^’ for square grid, ‘X’ for the position of cuboid (There maybe two ‘X’, but data guarantee that these two ‘X’s belong to the same cuboid and only one cuboid exists.).
Then there comes several lines which stand for order list. Each line only contains uppercase characters and blank. In the list, ‘L’ means moving left, ‘R’ means moving right, ‘U’ means moving up and ‘D’ means moving down. If you meet a ‘Q’, print the whole station of platform. Each case ends with a line a line entitled “END”.
ANY MOVE COULD CAUSE YOU TO LOSE THE GAME, YOU SHOULD JUST IGNORE IT.

Print a blank after each situation.

5 6
^^^^^^
^X^^^^
^^^^^^
#^^^^^
###^^^
RQ
RQ
END

^^^^^^
^^XX^^
^^^^^^
#^^^^^
###^^^

^^^^^^
^^^^X^
^^^^^^
#^^^^^
###^^^

CTW

2009浙江大学计算机研考复试（机试部分）——全真模拟