激光直线探测 II

题目描述

升级版激光会被镜子折射。给定 $n \times m$ 的平面：# 为障碍，0 为空地，R 为顺时针 $90^\circ$ 反射镜，L 为逆时针 $90^\circ$ 反射镜。激光从坐标 $(x,y)$ 出发，初始朝向用整数 $d$ 表示（$0$ 上、$1$ 右、$2$ 下、$3$ 左）。激光每次前进一步，若走到障碍或越界则停止；若遇到镜子，则方向随之变化后继续走；经过的空地与镜子位置都算被照亮。请输出照亮后的平面。

输入格式

第一行输入两个整数 $n,m$。

接下来 $n$ 行，每行 $m$ 个字符，仅包含 #、0、R、L。

最后一行输入三个整数 $x,y,d$，表示起点与初始方向。行列从 $1$ 开始计数，保证起点不是障碍。

输出格式

输出 $n$ 行：障碍仍为 #，被照亮的空地与镜子用 * 表示，未照亮的空地与镜子保持原字符。

输入输出样例 #1

输入 #1

4 6
00#0R0
0L0000
00#0#0
000000
1 1 1

输出 #1

**#0R0
0*0000
00#0#0
000000

数据范围

对于 $100\%$ 的数据，$1 \le n,m \le 100$，起点不为障碍。EOF