2618. 游戏

最近 Pollux 迷恋上了八数码游戏，相信大家对这个游戏并不陌生，小时候应该都玩过这个游戏吧。规则很简单，假如上图为原始状态，那么移动上图中的空格一步后的状态可以分别表示为下图的四个状态：

( Hint：上图分别为原图执行 up，right，down，left 后的最终状态)

在玩了很久之后，Pollux 逐渐发现这个游戏没有什么挑战。所以自己新发明了一种玩法，这种玩法需要两个人，所以 Pollux 便拉上 Castor 一起玩，规则如下 (假如 Pollux 为玩游戏的一方)：

1、Pollux 先记住把数码的初始状态，然后蒙上眼睛。

2、Castor 给出 N 个移动步骤，每一步分别为 up，right，down，left 四个中的一个，Pollux 在脑袋中模拟出移动后的状态，并记住。

3、N 步以后 Pollux 说出数码的最终状态。

是不是很简单呢？现在 Pollux 决定推广这种玩法，鉴于这种游戏是锻炼记忆力的游戏，所以 Pollux 还在 YY 以后这个游戏会流行起来，所以事先请你帮忙写一个程序模拟这个过程。