Background

这是一道函数交互题。

Description

铃音要过生日了，所以香穗为铃音准备了一个数字华容道作为生日礼物。

可惜的是，铃音并不会玩这个，但是她又不好意思去找香穗亲自教她，所以她找到了你来教她。

你已经是一位成熟的 OIer 了，所以你想要用程序来解决铃音给出的数字华容道盘面。

简单陈述一下数字华容道的规则：

• 盘面信息：

  • 华容道的盘面是 $n\times n$ 的网格，即共 $n$ 行 $n$ 列。
  • 华容道总共有 $(n^2-1)$ 个滑块，分别写有 $1\sim (n^2-1)$ 内的所有正整数，每个滑块占据一个网格。
  • 华容道总共有 $1$ 个空格。

• 移动要求：

  • 每一次移动，你都需要选择与空格相邻的一个滑块，并将该滑块移动到空格处，空格的位置变为该滑块在移动前的位置。

• 游戏目标：

  • 你需要将写有 $(i-1)\times n + j$（此处 $i,j$ 满足 $1\leq i,j\leq n$ 且 $i,j$ 不均为 $n$）的滑块移动至第 $i$ 行第 $j$ 列，同时使得空格在第 $n$ 行第 $n$ 列。

但是，香穗不需要在这里赶时间，你也不必最小化步数。

你需要帮助香穗构造一个完成华容道的步骤全过程，或者告知这个华容道无解。

Format

为了避免大量的输出，本题采用函数交互形式。

Input

评测程序示例按照如下格式读取输入数据。

第一行一个正整数 $n$，表示华容道的大小。

接下来 $n$ 行，每行 $n$ 个非负整数 $A_{i,j}$，描述初始的华容道盘面。

若 $A_{i,j}=0$，则表示该方格初始为空格。

Output

评测程序示例按照如下格式输出答案。

第一行一个字符串 Yes 或 No，分别代表该华容道有解或者无解。

如果华容道有解：

第二行一个非负整数 $k$，表示完成该华容道的所需步数。

第三行一个长度为 $k$ 的仅由字符 UDLR 构成的字符串 $S$，描述完成该华容道的方法。

描述方法为：

• 按照从左到右的顺序，依次执行每一个字符所代表的指令：
  • 若该字符为 U，则表示将空格下方相邻的滑块上移。
  • 若该字符为 D，则表示将空格上方相邻的滑块下移。
  • 若该字符为 L，则表示将空格右边相邻的滑块左移。
  • 若该字符为 R，则表示将空格左边相邻的滑块右移。

Samples

3
1 2 3
5 6 8
4 7 0

Yes
6
DRRULL

3
1 2 3
4 5 6
8 7 0

No

Limitation

对于 $100\%$ 的数据：

• $3\leq n\leq 200$
• $\forall 0\leq x < n^2$，总存在恰好一对整数数对 $(i,j)$ 满足 $1\leq i,j\leq n, A_{i,j} = x$

Detail

【本部分告知函数交互的实现细则】

具体地，你可以通过调用 wisdom.h 来完成此题，参考实现：

#include "wisdom.h"

本地调试时，你可以从附件中下载 wisdom.h 文件并使用，附件中的 wisdom.h 与真实评测使用的 wisdom.h 均可以完成下述函数功能，附件中的 wisdom.h 从标准输入进行输入，并给出你的判断、最后的华容道结果与所操作的步数。

使用附件的 wisdom.h 时，请将 wisdom.h 文件与你的程序放置在同一个目录中。

void Play(int &n,vector<vector<int>>&A)

该函数接受两个参数 $n$ 和 $A$，且 $A$ 是一个 $n\times n$ 的矩阵，下标为 $0\sim n-1$，分别表示华容道的大小与华容道的初始盘面。

当调用该函数时，你的参数将会被初始化为输入数据。

该函数应当恰好被调用一次。

接下来，你可以调用如下函数，用于解决上述问题：

void MoveUp()

该函数不接受参数，表示将空格下方相邻的滑块上移，如果空格在最下方一行则操作无效。

void MoveDown()

该函数不接受参数，表示将空格上方相邻的滑块下移，如果空格在最上方一行则操作无效。

void MoveLeft()

该函数不接受参数，表示将空格右边相邻的滑块左移，如果空格在最右边一列则操作无效。

void MoveRight()

该函数不接受参数，表示将空格左边相邻的滑块右移，如果空格在最左边一列则操作无效。

void Stop()

该函数不接受参数，表示所有操作已经执行完毕，此时该华容道应当已经复原完成，当调用该函数后，程序应当立即停止运行。

void Impossible()

该函数不接受参数，表示你判断这个华容道的初始局面无解，当调用该函数后，程序应当立即停止运行。

在调用 void Stop() 前任何时候调用该函数均被认为是判定为无解，无论此前是否执行过移动操作。