凯内西斯在探索啾啾岛以讨伐黑魔法师的过程中,遇到了饥饿的姆托。一直负责为姆托准备每日餐食的西米亚,为了制作能满足姆托胃口的大型披萨,向凯内西斯寻求帮助。由于体型巨大的姆托挡住了通往黑魔法师的道路,凯内西斯不得不答应西米亚的请求。
姆托想要的巨大披萨是一个 $N \times N$ 的网格,披萨左上角的格子为第 $1$ 行第 $1$ 列,右下角的格子为第 $N$ 行第 $N$ 列。西米亚给出的食谱上画有披萨上肉丸的布局,凯内西斯需要按照食谱放置肉丸。起初,披萨的第 $R$ 行第 $C$ 列已经放置了一颗西米亚预先放好的肉丸。肉丸的形状与网格完全吻合,且一个格子内不能放置超过一颗肉丸。
$N=5, R=3, C=2$ 时披萨的状态以及在披萨外使用念力的位置
由于踩到披萨会导致其无法食用,凯内西斯必须在披萨外使用念力来完成披萨的制作。使用一次念力的过程如下:
- 确定使用念力的位置。可选位置为披萨的上、下、左、右四个方向。念力从凯内西斯所在位置开始,若在上方则向行增加的方向作用,若在下方则向行减小的方向作用,若在左方则向列增加的方向作用,若在右方则向列减小的方向作用。
- 确定使用念力的行号或列号。念力必须与行或列平行使用,且不能同时作用于两行或两列以上。
- 使用念力。念力分为两种:
- 推入 (push):将肉丸推入,并将其放置在撞到的第一颗肉丸的前一个格子中。如果在推入前,念力作用方向的第一个格子已有肉丸,或者因为该方向没有肉丸导致推入的肉丸无法留在披萨内,则该肉丸消失。
- 拉出 (pull):将念力接触到的第一颗肉丸从披萨中取出。如果念力作用方向上没有肉丸,则什么都不会发生。
使用推入 (push) 和拉出 (pull) 念力的示意图
如果按照西米亚的食谱完成了披萨,姆托就会吃得心满意足,并让出通往下一个区域的道路。但由于不知道黑魔法师何时会毁灭世界,凯内西斯不能在制作披萨上浪费时间。
请输出一种在 $2N^2$ 次以内使用念力完成披萨的方法。
第一行给定披萨的大小 $N$。($3 \leq N \leq 50$)
第二行给定西米亚最初放置的肉丸所在的行号 $R$ 和列号 $C$,中间用空格隔开。($1 \leq R, C \leq N$)
接下来 $N$ 行给出西米亚食谱上的肉丸布局。每行给出一个长度为 $N$ 的字符串。食谱第 $i$ 行的第 $j$ 个字符表示第 $i$ 行第 $j$ 列是否有肉丸,. 表示空格,# 表示放置了肉丸的格子。
如果能在 $2N^2$ 次以内使用念力完成披萨,第一行输出凯内西斯使用念力的次数 $M$。注意,$M$ 不需要是最小值。($0 \leq M \leq 2N^2$)
若 $M \geq 1$,则从第二行开始,每行输出一次凯内西斯执行的动作。每行包含使用念力的位置(上方:U,下方:D,左方:L,右方:R)、行号或列号 $X$ ($1 \leq X \leq N$) 以及念力的种类(推入为 push,拉出为 pull),中间用空格隔开。
如果无法在 $2N^2$ 次以内完成披萨,第一行仅输出 -1。
样例
输入格式 1
3 2 2 .#. ##. ...
输出格式 1
2 U 2 push L 2 push
输入格式 2
3 1 2 ... #.# .#.
输出格式 2
6 D 2 push D 2 push L 2 push R 2 push U 2 pull U 2 pull
输入格式 3
4 1 1 .... .... .... ....
输出格式 3
1 L 1 pull