T310723 企鹅走迷宫

元元在玩一个两只企鹅走迷宫的复古小游戏。游戏在两个 $20×20$ 大小的棋盘中进行，左右相邻，其中有一些砖块阻挡前进。 企鹅一步只能向上下左右四个方向走一格，如果它的前进方向上有砖块，则会原地不动。玩家可以向四个方向移动这两只企鹅，但这两只企鹅的移动方式是镜像的，具体表现为： `L`：左边的企鹅向左走，右边的企鹅向右走。 `R`：左边的企鹅向右走，右边的企鹅向左走。 `U`：同时向上移动。 `D`：同时向下移动。 注：一次操作可以仅让一只企鹅发生移动，另一只企鹅受阻碍而原地不动。 左边的企鹅从 $(20,20)$ 开始，想要移动到 $(1,20)$。右边的企鹅从 $(20,1)$ 开始时，想要移动到 $(1,1)$，当两只企鹅都到达目的地时，游戏结束。 找到赢得游戏的最少操作次数（保证总算是存在一种赢法，且企鹅的初始位置不存在砖块），如果存在多种赢得游戏的最短操作序列，则输出字典序最小的(`D`$

输入包含 $21$ 行。 第一行一个整数 $x$，为$1$或$2$，表示测试数据的类型。 如果 $x=1$，则只需要输出最小步数。 如果 $x=2$，则需要输出步数和操作序列。 接下来的 $20$ 行，每行有 $41$ 个字符，表示两个 $20×20 $ 的棋盘，中间以空格作为分隔。 以 `.` 表示空地，`#` 表示砖块。

输出包含 $22$ 行。 第一行输出赢得游戏所须的最小步数。 第二行包含所需的操作序列。（如果数据类型 $x=1$ 则无此行） 接下来 $20$ 行输出整个地图，并用 `A` 代替企鹅，以表示企鹅的行动路线（详见样例）。

**数据范围** 对于 $30\%$ 的数据，$x=1$。 对于另外 $10\%$ 的数据，地图中没有障碍。 对于另外 $10\%$ 的数据，只存在一条合法路径。 对于剩余 $50\%$ 的数据，$x=2$ 且没有额外限制。