問題文

$H$ 行 $W$ 列に並べられた動く床の上に何匹かのスライムがいます。 上から $i$ 行目、左から $j$ 列目の動く床を $(i,j)$ と表します。 動く床はそれぞれ状態A, Bの2つの状態をもちます。また、動く床はいずれの状態においても上下左右のいずれかの方向に動いています。 $(i,j)$ が状態A, Bのときに動く方向はそれぞれ文字 $A_{i,j}, B_{i,j}$ によって表されます。 $A_{i,j}$ の意味は次のとおりです。

• $A_{i,j}$ が U のとき、$(i,j)$ は上向き、すなわち $(i-1, j)$ の方向に動いている。
• $A_{i,j}$ が D のとき、$(i,j)$ は下向き、すなわち $(i+1, j)$ の方向に動いている。
• $A_{i,j}$ が L のとき、$(i,j)$ は左向き、すなわち $(i, j-1)$ の方向に動いている。
• $A_{i,j}$ が R のとき、$(i,j)$ は右向き、すなわち $(i, j+1)$ の方向に動いている。

なお、$B_{i,j}$ も同様です。また、どの床も床のない方向には動いていないことが保証されます。

ここで、スイッチが搭載された動く床がちょうど $1$ つだけ存在します。スイッチが搭載された動く床は $(i_s, j_s)$ で与えられます。 スライムが $(i_s, j_s)$ に到達すると、その瞬間にスイッチが作動し、以下の変化が生じます。

• スイッチの作動が奇数回目 $(1回目, 3回目, \cdots)$ ならば、$(i,j)$ が動く方向は $A_{i,j}$ から $B_{i,j}$ に切り替わる。
• スイッチの作動が偶数回目 $(2回目, 4回目, \cdots)$ ならば、$(i,j)$ が動く方向は $B_{i,j}$ から $A_{i,j}$ に切り替わる。

現在、$(i,j)$ にスライムがいるかどうかが $S_{i,j}$ によって与えられます。 $S_{i,j}$ は $(i,j)$ にスライムがいるなら #、いないなら . です。 ただし、スイッチが搭載された動く床 $(i_s, j_s)$ にはスライムがいないことが保証されます。

$1$ 秒経過する毎に各スライムはそのときにいる床が動く方向に移動します。 なお、$2$ 匹以上のスライムが同じ床に移動した場合、それらのスライムは合体して $1$ 匹のスライムになります。

現在から $t$ 秒後のスライムの配置を出力してください。

制約

• $H, W, t, i_s, j_s$ は正整数
• $1 \leq H \times W < 20$
• $1 \leq t \leq 10^{18}$
• $1 \leq i_s \leq H$
• $1 \leq j_s \leq W$
• $A_{i,j}, B_{i,j}$ は U, D, L, R のいずれかである
• $A_{1,j} \neq$ U, $B_{1,j} \neq$ U
• $A_{H,j} \neq$ D, $B_{H,j} \neq$ D
• $A_{i,1} \neq$ L, $B_{i,1} \neq$ L
• $A_{i,W} \neq$ R, $B_{i,W} \neq$ R
• $S_{i,j}$ は #, . のいずれかである

入力

入力は以下の形式で標準入力から与えられます。

出力

$t$ 秒後、$(i,j)$ にスライムがいるかどうかを表す $T_{i,j}$ を以下の形式で出力してください。 $T_{i,j}$ は $t$ 秒後、$(i,j)$ にスライムがいるなら #、いないなら . です。

入出力例

3 3 10 3 3
RRD
URD
ULL
DLL
DRU
RRU
#..
...
...

...
...
#..

初め $(1, 1)$ にいるスライムは $4$ 秒だけかけて $(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3)$ と移動します。$(3, 3)$ にはスイッチがあり、スイッチが作動することで動く床の状態が変化します。 その後、スライムは $6$ 秒だけかけて $(3, 3) \rightarrow (2, 3) \rightarrow (1, 3) \rightarrow (1, 2) \rightarrow (1, 1) \rightarrow (2, 1) \rightarrow (3, 1)$ と移動します。よって、$10$ 秒後には $(3, 1)$ にいます。

2 3 10 2 2
RDL
RUL
RRD
ULL
#.#
#..

..#
#..

初め $(1, 1), (1, 3)$ にいる $2$ 匹のスライムは $1$ 秒後に $(1, 2)$ で合体します。

4 2 1000000000000000000 1 1
RD
UL
RD
UL
RL
UD
UU
UL
..
.#
#.
##

#.
..
.#
..

入力値 $t$ が32bit整数型に収まらないこともあります。