問題文
行 列に並べられた動く床の上に何匹かのスライムがいます。 上から 行目、左から 列目の動く床を と表します。 動く床はそれぞれ状態A, Bの2つの状態をもちます。また、動く床はいずれの状態においても上下左右のいずれかの方向に動いています。 が状態A, Bのときに動く方向はそれぞれ文字 によって表されます。 の意味は次のとおりです。
- が
Uのとき、 は上向き、すなわち の方向に動いている。 - が
Dのとき、 は下向き、すなわち の方向に動いている。 - が
Lのとき、 は左向き、すなわち の方向に動いている。 - が
Rのとき、 は右向き、すなわち の方向に動いている。
なお、 も同様です。また、どの床も床のない方向には動いていないことが保証されます。
ここで、スイッチが搭載された動く床がちょうど つだけ存在します。スイッチが搭載された動く床は で与えられます。 スライムが に到達すると、その瞬間にスイッチが作動し、以下の変化が生じます。
- スイッチの作動が奇数回目 ならば、 が動く方向は から に切り替わる。
- スイッチの作動が偶数回目 ならば、 が動く方向は から に切り替わる。
現在、 にスライムがいるかどうかが によって与えられます。
は にスライムがいるなら #、いないなら . です。
ただし、スイッチが搭載された動く床 にはスライムがいないことが保証されます。
秒経過する毎に各スライムはそのときにいる床が動く方向に移動します。 なお、 匹以上のスライムが同じ床に移動した場合、それらのスライムは合体して 匹のスライムになります。
現在から 秒後のスライムの配置を出力してください。
制約
- は正整数
- は
U,D,L,Rのいずれかである -
U,U -
D,D -
L,L -
R,R - は
#,.のいずれかである
入力
入力は以下の形式で標準入力から与えられます。
出力
秒後、 にスライムがいるかどうかを表す を以下の形式で出力してください。
は 秒後、 にスライムがいるなら #、いないなら . です。
入出力例
入力例1
3 3 10 3 3 RRD URD ULL DLL DRU RRU #.. ... ...
出力例1
... ... #..
初め にいるスライムは 秒だけかけて と移動します。 にはスイッチがあり、スイッチが作動することで動く床の状態が変化します。 その後、スライムは 秒だけかけて と移動します。よって、 秒後には にいます。
入力例2
2 3 10 2 2 RDL RUL RRD ULL #.# #..
出力例2
..# #..
初め にいる 匹のスライムは 秒後に で合体します。
入力例3
4 2 1000000000000000000 1 1 RD UL RD UL RL UD UU UL .. .# #. ##
出力例3
#. .. .# ..
入力値 が32bit整数型に収まらないこともあります。