棋盘上只剩下了国王。尽管孤独,他并没有灰心,因为他有事关国家的大事。比如说,他要去t广场进行正式拜访。由于国王不习惯浪费时间,因此他希望以最少的步数从当前位置 s 到达 t 的平方。帮助他做到这一点。
在一次移动中,国王可以到达与国王当前所在的方格具有公共边或公共顶点的方格(通常他可以移动到 8 个不同的方格)。
输入
第一行包含方格 s 的棋盘坐标,第二行包含方格 t 的棋盘坐标。
棋盘坐标由两个字符组成,第一个是小写拉丁字母(从a到h),第二个是从1到8的数字。
输出
在第一行打印 n — 国王的最小移动次数。然后在 n 行中打印动作本身。每个动作都用 8 种之一来描述:L、R、U、D、LU、LD、RU 或 RD。
L、R、U、D分别代表左、右、上、下移动(如图),2个字母组合代表对角移动。如果答案不唯一,请打印其中任何一个。
示例
输入 #1
a8 h1
输出 #1
7 RD RD RD RD RD RD RD