凱內西斯在探索啾啾島以討伐黑魔法師的過程中,遇見了飢餓的慕托。為了慕托每天準備餐點的西米亞,請求凱內西斯幫忙製作一個大披薩,以安撫鬧脾氣的慕托。由於體型巨大的慕托擋住了前往黑魔法師所在地的路,凱內西斯只好答應西米亞的請求。
慕托想要的巨大披薩是一個 $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