E. 昨日方舟
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

《昨日方舟》是一款塔防类游戏。在游戏中，我们要通过部署角色来抵御怪物的入侵。在这款游戏中，有一名角色名字为"今"，他的能力为能够在地图上部署小蛇，小蛇在某些条件下可以与其他小蛇合体，成为大蛇，大蛇不能再与其他小蛇或大蛇合成。

现在有一个大小为 $$$n$$$ 行 $$$m$$$ 列的地图，自上往下分别为第 $$$1$$$ 行……第 $$$n$$$ 行，自左往右为第 $$$1$$$ 列……第 $$$m$$$ 列。格子分为可部署格和不可部署格。小蛇只能部署在可部署格上，并且小蛇在部署时，会有一个确定的朝向。

大蛇的合成规则如下：

  1. 若当前部署的小蛇所面向的相邻格子中存在另一条小蛇，则当前部署的小蛇消失，面向的小蛇变成大蛇，朝向不变（与原来的小蛇一致）。
  2. 若 1 中情况不满足，但存在已经部署的其他小蛇面向当前部署的格子，且与当前部署的格子相邻，那么这些小蛇中最后一条部署的小蛇消失，当前部署的小蛇变成大蛇，朝向与当前部署小蛇一致。
现在给定 $$$n \times m$$$ 的地图的每个格子的可部署情况，以及无限只待部署的小蛇，初始状态下地图中不存在小蛇与大蛇，并且按照时间顺序给定 $$$k$$$ 次尝试部署小蛇的位置和朝向（可能尝试部署在其他小蛇、大蛇和不可部署位置上，此时视作部署失败，不会发生任何事），请输出最后地图上的小蛇与大蛇的存在情况。
Input

输入第 $$$1$$$ 行包含 $$$3$$$ 个用空格分隔的正整数 $$$n, m, k$$$ ，代表地图的大小与尝试部署的次数。$$$(1 \leq n,m \leq 10^3,\ 1 \leq k \leq 2\times 10 ^ 5 $$$)

接下来 $$$n$$$ 行每行有 $$$m$$$ 个用空格分隔的整数，第 $$$i$$$ 行第 $$$j$$$ 个整数代表了地图中第 $$$i$$$ 行第 $$$j$$$ 列格子的可部署情况，$$$0$$$ 代表不可部署格，$$$1$$$ 代表可部署格子。

最后 $$$k$$$ 行，每行包含 $$$2$$$ 个整数 $$$x,\ y$$$ 与一个字符 $$$c$$$ ，第 $$$i$$$ 行表示按照时间顺序，第 $$$i$$$ 次尝试部署的小蛇位置为第 $$$x$$$ 行第 $$$y$$$ 列，且朝向为 $$$c$$$ 。 ($$$1 \leq x \leq n,\ 1 \leq y \leq m,\ c \in $$${'u','d','l','r'}，$$$u, d, l, r$$$ 分别代表朝向为上、下、左、右)。

Output

输出 $$$n$$$ 行，每行包含 $$$m$$$ 个字符，第 $$$i$$$ 行第 $$$j$$$ 列的字符 $$$c$$$ 代表最终地图上第 $$$i$$$ 行第 $$$j$$$ 列格子的状态。'X' 表示该格为不可部署区域，'O' 表示该格为可部署区域，但不存在小蛇与大蛇部署在该格，'u', 'd', 'l', 'r' 表示该格部署了小蛇，并且朝向为上、下、左、右，'U', 'D', 'L', 'R' 表示该格部署了大蛇，且朝向为上、下、左、右。

Examples
Input
2 2 4
1 1
1 1
1 1 r
1 2 l
2 1 l
2 2 r
Output
RO
lr
Input
3 9 12
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1
1 2 d
2 1 r
3 2 u
2 2 r
1 5 d
2 4 r
3 5 u
2 5 d
1 8 d
2 7 r
3 8 u
2 8 r
Output
OdOOdOOdO
rROrOOrXO
OOOOUOOuO