キネシスは黒い魔法使いを討伐するためにチューチューアイランドを探索中、腹を空かせたムトに出くわした。ムトのために毎日食事を与えていたシミヤは、食事に文句を言っているムトのために特大ピザを作るべく、キネシスに助けを求めた。体が大きいムトは黒い魔法使いの元へ向かう道を塞いでいるため、キネシスは仕方なくシミヤの頼みを聞き入れることにした。
ムトが望む特大ピザは $N \times N$ の格子状であり、ピザの左上のマスは $1$ 行 $1$ 列、右下のマスは $N$ 行 $N$ 列である。シミヤが渡したレシピにはピザに載せるべきミートボールの配置が描かれており、キネシスはレシピ通りにミートボールをトッピングしなければならない。最初、ピザの $R$ 行 $C$ 列にはシミヤが先にトッピングしたミートボールが一つ置かれている。ミートボールの形は格子のマスと完全に一致し、一つのマスに二つ以上のミートボールを入れることはできない。
$N=5, R=3, C=2$ の時のピザの状態と、ピザの外から念動力を使用できる位置
ピザを踏むと食べられなくなってしまうため、キネシスはピザの外から念動力を使用してピザを完成させなければならない。念動力を $1$ 回使用する手順は以下の通りである。
- 念動力を使用する位置を決める。可能な位置はピザの上側、下側、左側、右側のいずれかである。念動力はキネシスが位置する場所から始まり、上側なら行が増加する方向へ、下側なら行が減少する方向へ、左側なら列が増加する方向へ、右側なら列が減少する方向へ使用する。
- 念動力を使用する行または列の番号を決める。念動力は行または列と平行に使用しなければならず、二つ以上の行または列にまたがって使用することはできない。
- 念動力を使用する。使用できる念動力には二種類ある。
- 押し込み (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$ が $1$ 以上ならば、二行目から $M$ 行にわたり、キネシスが実行した行動を一行ずつ出力する。各行には念動力を使用した位置（上側: 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