题目描述

在一个$\red{3×3}$的网格中，$\red{1\sim 8}$这$\red{8}$个数字和一个$\red{“X”}$恰好不重不漏地分布在这$\red{3×3}$的网格中。

例如：

$\red{1~ 2~ 3}$

$\red{X~ 4~ 6}$

$\red{7~ 5~ 8}$

在游戏过程中，可以把$\red{“X”}$与其上、下、左、右四个方向之一的数字交换（如果存在）。

我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

$\red{1~ 2~ 3}$

$\red{4~ 5~ 6}$

$\red{7~ 8~ X}$

例如，示例中图形就可以通过让$\red{“X”}$先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下：

$\red{1~ 2~ 3 ~~~ 1 ~2~ 3~~~ 1~ 2~ 3 ~~~ 1~ 2 ~3}$

$\red{X~ 4~ 6~~~ 4~ X ~6~~~ 4 ~5~ 6 ~~~4 ~5~ 6}$

$\red{7~ 5~ 8~~~ 7 ~5 ~8~~~ 7~ X~ 8~~~ 7~ 8~ X}$

把$\red{“X”}$与上下左右方向数字交换的行动记录为$\red{“u”、“d”、“l”、“r”}$。

现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

输入格式

输入占一行，将$\red{3×3}$的初始网格描绘出来。

例如，如果初始网格如下所示：

$\red{1 ~2~ 3}$

$\red{x ~4 ~6}$

$\red{7 ~5 ~8}$

则输入为：$\red{1 ~2~ 3~ x~ 4~ 6~ 7~ 5~ 8}$

输出格式

输出占一行，包含一个字符串，表示得到正确排列的完整行动记录。如果答案不唯一，输出任意一种合法方案即可。

如果不存在解决方案，则输出”unsolvable”。

样例

输入样例

2  3  4  1  5  x  7  6  8

输出样例

ullddrurdllurdruldr