题目描述

15 数字拼图游戏已经有超过 100 年的历史了；即使你不知道它叫这个名字，你也肯定见过它。它由 15 个滑动的方块组成，每个方块上都标有从 1 到 15 的数字，所有方块都被装在一个 4×4 的框架中，其中一个方块缺失。我们称缺失的方块为 'x'，游戏的目标是将方块排列成以下顺序：

 1  2  3  4 

 5  6  7  8 

 9 10 11 12 

13 14 15  x 

唯一合法的操作是将 'x' 与它相邻的方块交换位置。例如，以下一系列移动可以解决一个稍微混乱的拼图：

 1  2  3  4    1  2  3  4    1  2  3  4    1  2  3  4 

 5  6  7  8    5  6  7  8    5  6  7  8    5  6  7  8 

 9  x 10 12    9 10  x 12    9 10 11 12    9 10 11 12 

13 14 11 15   13 14 11 15   13 14  x 15   13 14 15  x 

           r->           d->           r-> 

上一行中的字母表示在每一步中，与 'x' 方块相邻的哪个方块与 'x' 交换位置；合法的值是 'r'、'l'、'u' 和 'd'，分别表示向右、向左、向上和向下。

并不是所有的拼图都能被解决；1870 年，一个名叫萨姆·洛伊德（Sam Loyd）的人因分发了一个无法解决的拼图版本而闻名，这让许多人感到沮丧。事实上，要将一个普通的拼图变成一个无法解决的拼图，你只需要交换两个方块（当然，不包括缺失的 'x' 方块）。

在这个问题中，你需要编写一个程序来解决不太知名的 8 数字拼图游戏，它由一个 3×3 的方块组成。

输入

你会收到一个 8 拼图的初始配置描述。描述只是初始位置的方块列表，行从上到下列出，行内的方块从左到右列出，方块用数字 1 到 8 和 'x' 表示。例如，这个拼图：

 1  2  3 

 x  4  6 

 7  5  8 

可以用以下列表描述：

1 2 3 x 4 6 7 5 8

输出

你将在标准输出中打印出“unsolvable”，如果拼图没有解决方案，或者打印出一个由字母 'r'、'l'、'u' 和 'd' 组成的字符串，描述一系列产生解决方案的移动。字符串不应包含空格，并且从行首开始。

输入数据 1

2 3 4 1 5 x 7 6 8

输出数据 1

ullddrurdllurdruldr

来源

美国中南部 1998