U419510 飞镖

**时间限制：** 3.0 秒 **空间限制：** 512 MB

小 R 在一个 $n\times m$ 的网格中玩飞镖游戏，其中的每个格子可以用二维坐标 $(x,y)$ 指定（其中 $1\le x\le n,~1\le y\le m$），X 轴以向下为递增正方向，而 Y 轴以向右为递增正方向。网格中每个格子上都可以有至多一个**标记**，初始时所有各自均没有**标记**。 小 R 会依次投掷 $q$ 枚飞镖，每一枚飞镖由三个参数 $x,y,t$ 指定，其中 $(x,y)$ 表示其投掷位置，$t$ 为飞镖类型，为 `+` , `x` , `*` 三者之一，具体说明如下 : 对于所有类型的飞镖，都会在投掷向 $(x,y)$ 位置写入一个对应**标记**（如 `+` 型飞镖会在 $(x,y)$ 位置写入 `+` ） 。如果此位置原本已有**标记**，则会将其覆盖。 对于 `+` 类型飞镖，投掷时会向投掷位置的上、下、左、右的四个方向各发射一只小飞镖。这些小飞镖会沿着各自的方向以每秒 $1$ 格的速度一直飞行，直到**其中之一**碰撞到了某个已有的**标记**或者超出网格边界。当碰撞或出界发生时，所有的小飞镖会同时停止飞行。对于发生碰撞的小飞镖，会将其所在位置的**标记**清除。对于未发生碰撞也未出界的小飞镖，会将其所在位置**标记**为 `+` 。 对于 `x` 类型飞镖，投掷时会向投掷位置的左上、左下、右上、右下的四个方向各发射一只小飞镖，速度为每秒 $\sqrt 2$ 格。其余规则同上，但对于未发生碰撞也未出界的小飞镖，会将其所在位置**标记**为 `x` 。 对于 `*` 类型飞镖，投掷时会向投掷位置的上、下、左、右、左上、左下、右上、右下的八个方向各发射一只小飞镖。上下左右方向的速度为每秒 $1$ 格，而斜线方向的速度为每秒 $\sqrt 2$ 格。其余规则同上，但对于未发生碰撞也未出界的小飞镖，会将其所在位置**标记**为 `*` 。 下面将举例说明 : 例如 $n=5,m=6$ ，初始时棋盘为空，我们用 `.` 表示一个空位置。 ```plain ...... ...... ...... ...... ...... ``` 假设向 $(2,2)$ 投掷一枚 `+` 类型的飞镖，则会先在 $(2,2)$ 位置写入 `+` : ```plain ...... .+.... ...... ...... ...... ``` 然后，会向上、下、左、右四个方向各发射一只小飞镖，它们会以每秒 $1$ 格的速度飞行。向上、向左的两只小飞镖会在 $2$ 秒后出界，而此时向下、向右的两只小飞镖会停止飞行并将其所在位置**标记**为 `+` : ```plain ...... .+.+.. ...... .+.... ...... ``` 假设在此基础上，向 $(3,3)$ 投掷一枚 `x` 类型的飞镖，则会先在 $(3,3)$ 位置写入 `x` : ```plain ...... .+.+.. ..x... .+.... ...... ``` 然后，会向左上、左下、右上、右下四个方向各发射一只小飞镖，它们会以每秒 $\sqrt 2$ 格的速度飞行。向左上、左下、右上的三只小飞镖会在 $1$ 秒后碰撞到已有的标记，而此时向右下的一只小飞镖会停止飞行并将其所在位置标记为 `x` : ```plain ...... ...... ..x... ...x.. ...... ``` 假设在此基础上，向位置 $(5,4)$ 投掷一枚 `*` 类型的飞镖，则会先在 $(5,4)$ 位置写入 `*` : ```plain ...... ...... ..x... ...x.. ...*.. ``` 然后，会向上、下、左、右、左上、左下、右上、右下八个方向各发射一只小飞镖，它们会以每秒 $1$ 格或 $\sqrt 2$ 格的速度飞行。向上的小飞镖会在 $1$ 秒后碰撞到已有的标记，与此同时向下、左下、右下的三只小飞镖会出界，其余方向的小飞镖会停止移动，最终棋盘状态如下 : ```plain ...... ...... ..x... ..*.*. ..***. ``` 假设在此基础上，向位置 $(3,3)$ 投掷一枚 `x` 类型的飞镖，则最终状态如下（注意覆盖了该位置的原有标记） : ```plain x...x. ...... ..x... ..*.*. x.**.. ``` 本题目将会给出 $n,m,q$ 和 $q$ 个飞镖的信息，你需要对于投掷的每个飞镖回答 : - 该飞镖是否覆盖了投掷位置 $(x,y)$ 的原有标记？如果覆盖了，原有的标记是什么？ - 该飞镖产生的小飞镖飞行了多少秒的时间？ - 产生的每个小飞镖的最终状态是什么？（碰撞到了标记/出界/未碰撞也未出界）

无

无

### 子任务 本题共 $25$ 个测试点，每个测试点 $4$ 分。对于所有的数据，$1\le n,m,q \le 10^5$ ，飞镖的位置都是均匀随机生成的。 | 测试点编号 | $n,m,q\le $ | 特殊性质 | | :----: | :--: | :--: | | $1\sim 3$ | $10^3$ | 所有的飞镖均为 `+` 类型 | | $4\sim 6$ | $10^3$ | 所有的飞镖均为 `x` 类型 | | $7\sim 9$ | $10^3$ | 所有的飞镖均为 `*` 类型 | | $10\sim 11$ | $10^3$ | 无 | | $12\sim 15$ | $10^5$ | 所有的飞镖均为 `+` 类型 | | $16\sim 19$ | $10^5$ | 所有的飞镖均为 `x` 类型 | | $20\sim 23$ | $10^5$ | 所有的飞镖均为 `*` 类型 | | $24\sim 25$ | $10^5$ | 无 |