时间限制： 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$，初始时棋盘为空，我们用 . 表示一个空位置。

......
......
......
......
......

假设向 $(2,2)$ 投掷一枚 + 类型的飞镖，则会先在 $(2,2)$ 位置写入 +：

......
.+....
......
......
......

然后，会向上、下、左、右四个方向各发射一只小飞镖，它们会以每秒 $1$ 格的速度飞行。向上、向左的两只小飞镖会在 $2$ 秒后出界，而此时向下、向右的两只小飞镖会停止飞行并将其所在位置标记为 +：

......
.+.+..
......
.+....
......

假设在此基础上，向 $(3,3)$ 投掷一枚 x 类型的飞镖，则会先在 $(3,3)$ 位置写入 x：

......
.+.+..
..x...
.+....
......

然后，会向左上、左下、右上、右下四个方向各发射一只小飞镖，它们会以每秒 $\sqrt 2$ 格的速度飞行。向左上、左下、右上的三只小飞镖会在 $1$ 秒后碰撞到已有的标记，而此时向右下的一只小飞镖会停止飞行并将其所在位置标记为 x：

......
......
..x...
...x..
......

假设在此基础上，向位置 $(5,4)$ 投掷一枚 * 类型的飞镖，则会先在 $(5,4)$ 位置写入 *：

......
......
..x...
...x..
...*..

然后，会向上、下、左、右、左上、左下、右上、右下八个方向各发射一只小飞镖，它们会以每秒 $1$ 格或 $\sqrt 2$ 格的速度飞行。向上的小飞镖会在 $1$ 秒后碰撞到已有的标记，与此同时向下、左下、右下的三只小飞镖会出界，其余方向的小飞镖会停止移动，最终棋盘状态如下：

......
......
..x...
..*.*.
..***.

假设在此基础上，向位置 $(3,3)$ 投掷一枚 x 类型的飞镖，则最终状态如下（注意覆盖了该位置的原有标记）：

x...x.
......
..x...
..*.*.
x.**..

本题目将会给出 $n,m,q$ 和 $q$ 个飞镖的信息，你需要对于投掷的每个飞镖回答：

• 该飞镖是否覆盖了投掷位置 $(x,y)$ 的原有标记？如果覆盖了，原有的标记是什么？
• 该飞镖产生的小飞镖飞行了多少秒的时间？
• 产生的每个小飞镖的最终状态是什么？（碰撞到了标记/出界/未碰撞也未出界）

输入格式

从标准输入读入数据。

第一行输入三个整数 $n,m,q$，以空格分隔。

接下来 $q$ 行，每行输入三个元素 $x,y,t$，以空格分隔，表示一枚飞镖的信息。

输出格式

输出到标准输出。

输出 $q$ 行，每行输出三个元素，以空格分隔，表示一枚飞镖的信息：

• 如果该飞镖覆盖了投掷位置 $(x,y)$ 的原有标记，则输出原有的标记字符，否则输出 .；
• 输出该飞镖产生的小飞镖飞行了多少秒时间；
• 输出产生的每个小飞镖的最终状态，为 4 个或 8 个字符，+ 型飞镖按照上、下、左、右的顺序输出，x 型飞镖按照左上、左下、右上、右下的顺序输出， * 型飞镖按照上、下、左、右、左上、左下、右上、右下的顺序输出，如果该小飞镖碰撞到了标记则输出标记字符，如果该小飞镖出界则输出 o，如果该小飞镖未碰撞也未出界则输出 .。

5 6 4
2 2 +
3 3 x
5 4 *
3 3 x

. 2 o.o.
. 1 +++.
. 1 xo...o.o
x 2 ...*

子任务

子任务

本题共 $25$ 个测试点，每个测试点 $4$ 分。对于所有的数据，$1\le n,m,q \le 10^5$，飞镖的位置都是均匀随机生成的。