B-牛可乐争霸赛_牛客2024年儿童节比赛

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

你和牛可乐是很好的朋友。牛可乐今天要去参加牛客2024年儿童节比赛。因为他想要拿下第一，但是他很蒟蒻，所以他拜托一位出题低手在这里放置了一道专门防止你这种信息学竞赛高手ac的题目。

牛可乐最近在玩迷宫小游戏，给出牛可乐的一些操作，和地图的一些信息请你生成一个地图，使得牛可乐无论怎么样都能获得宝箱，并且不碰到怪物。

1、地图是一个 $n \times n$ 的方格阵，上面有 $m$ 只怪物和一些墙体。墙体和超出格阵的地区都不可达，如果向不可达的区域移动，则实际上会停留原地。

2、牛可乐的操作是一个字符串 $S$ ，仅包含UDLR这四种字符，分别表示牛可乐操纵的角色向上/下/左/右移动一格。

3、牛可乐如果移动到存在怪物的位置，或者怪物移动到他所操控的角色所在的位置，那他便游戏失败了，所以你生成的地图要保证他不失败。

4、字符串的长度 $len(S)$ 代表游戏持续时间，牛可乐每个单位时间都会完成一个操作，直到 $len(S)$ 个单位时间过去，并不是得到宝箱就游戏结束。

5、第 $i$ 个怪物初始在第 $x_i$ 行，第 $y_i$ 列上。每个单位时间会朝着 $d_i$ 方向移动一格，如果该方向是不可达区域，那么怪物该单位时间会停留原地但是会倒转方向。

6、每个单位时间，牛可乐先操作完成，然后才是各个怪物的操作。

7、牛可乐的角色的初始位置是 $(1, 1)$ ，怪物的初始位置不会在牛可乐四周的邻格（不包括斜对角）。

8、其他请看备注

第一行两个正整数  表示地图的大小和怪物的数量。()
第二行一个仅包含 UDLR 四种字符的字符串。()
接下来  行，每行两个正整数和一个字符 。()

输出行列的数字矩阵。
0表示墙体，1表示宝箱，2表示普通的路

示例1

复制

6 1
DDDDDR
3 1 R

复制

刚好和怪物擦肩而过，又撞了一下墙

墙体和宝箱不能和怪物的初始位置重叠
怪兽可以重叠，人和墙体不能重叠
怪物走上宝箱所在的位置时会踩烂宝箱
宝箱最多存在一个