题目描述

学校的公告墙是一块 $H$ 行 $W$ 列的格子板，初始时每个格子上都写着大写字母 A。用 $(i, j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子。

宣传委员依次贴了 $Q$ 张海报。第 $i$ 张海报 $(1 \le i \le Q)$ 的贴法是：把左上角为 $(1,1)$、右下角为 $(R_i, C_i)$ 的整个矩形区域内的所有格子，全部覆盖成大写字母 $X_i$。后贴的海报会盖住先贴的。

请输出所有海报贴完后，公告墙上每个格子显示的字母。

注意：所有海报的左上角都固定在 $(1,1)$，只有右下角位置不同。

输入格式

第一行三个整数 $H, W, Q$。

接下来 $Q$ 行，第 $i$ 行两个整数和一个大写字母 $R_i, C_i, X_i$，表示第 $i$ 张海报。

输出格式

输出 $H$ 行，第 $i$ 行是一个长度为 $W$ 的字符串，其第 $j$ 个字符表示最终 $(i,j)$ 上显示的字母。

样例 1 输入

2 3 3
2 2 B
1 3 C
2 1 D

样例 1 输出

DCC
DBA

样例 1 解释

初始公告墙每格都是 A：

AAA
AAA

• 第 $1$ 张海报 2 2 B：把 $(1,1)$ 到 $(2,2)$ 涂成 B，墙面变成 BBA / BBA。
• 第 $2$ 张海报 1 3 C：把 $(1,1)$ 到 $(1,3)$ 涂成 C，墙面变成 CCC / BBA。
• 第 $3$ 张海报 2 1 D：把 $(1,1)$ 到 $(2,1)$ 涂成 D，墙面变成 DCC / DBA。

每个格子最终显示的，是覆盖过它的海报中最后一张的字母。 右下角 $(2,3)$ 从头到尾没被任何海报盖到，所以还是初始的 A。

样例 2 输入

1 7 7
1 7 E
1 6 C
1 5 N
1 4 A
1 3 V
1 2 D
1 1 A

样例 2 输出

ADVANCE

样例 2 解释

只有一行，且每张海报覆盖的前缀一次比一次短。第 $j$ 个位置最终留下的，是最后一次覆盖到它的那张海报的字母：

位置	最后覆盖它的海报	字母
$1$	第 $7$ 张 1 1 A	A
$2$	第 $6$ 张 1 2 D	D
$3$	第 $5$ 张 1 3 V	V
$4$	第 $4$ 张 1 4 A	A
$5$	第 $3$ 张 1 5 N	N
$6$	第 $2$ 张 1 6 C	C
$7$	第 $1$ 张 1 7 E	E

样例 3 输入

3 4 2
3 4 Z
3 4 Y

样例 3 输出

YYYY
YYYY
YYYY

样例 3 解释

两张海报覆盖范围完全相同，后贴的 Y 把 Z 整个盖住，所以整面墙都是 Y。

这个样例提醒：同一区域可能被反复覆盖。若逐张海报真的去涂，重复覆盖会让总涂格数远超 $H\times W$。

数据范围与提示

对于所有测试数据，保证 $1 \le H$，$1 \le W$，$H \times W \le 10^6$，$1 \le Q \le 2\times10^5$，$1 \le R_i \le H$，$1 \le C_i \le W$，$X_i$ 是大写英文字母，所有输入的数值均为整数。

测试点编号	$H \times W$ 的范围	$Q$ 的范围	特殊性质
$1 \sim 3$	$\le 10^4$	$\le 1000$	无
$4 \sim 5$	$\le 10^6$	$\le 2\times10^5$	$H = 1$（只有一行）
$6$			所有 $(R_i, C_i)$ 完全相同
$7 \sim 8$	$\le 10^5$		矩形接近满格
$9 \sim 10$	$\le 10^6$		无

注意：$H$ 与 $W$ 各自都没有单独的上界，只保证 $H \times W \le 10^6$（例如可能出现 $H = 10^6, W = 1$）。