题目描述

有一个 $H \times W$ 的网格，初始时每个格子上都写着字母 A。用 $(i, j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子。

接下来按顺序进行 $Q$ 次操作。第 $i$ 次操作是：把左上角为 $(1,1)$、右下角为 $(R_i, C_i)$ 的整个矩形里的所有格子，全部覆盖成大写字母 $X_i$。

请输出所有操作结束后的网格。

输入格式

H W Q
R_1 C_1 X_1
R_2 C_2 X_2
...
R_Q C_Q X_Q

输出格式

输出 $H$ 行，第 $i$ 行是一个长度为 $W$ 的字符串，其第 $j$ 个字符表示操作结束后 $(i, j)$ 上的字母。

输入示例 1

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

输出示例 1

DCC
DBA

示例 1 说明

初始网格是

AAA
AAA

• 第 $1$ 次操作把 $(1,1)$ 到 $(2,2)$ 涂成 B，得到 BBA / BBA；
• 第 $2$ 次操作把 $(1,1)$ 到 $(1,3)$ 涂成 C，得到 CCC / BBA；
• 第 $3$ 次操作把 $(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$ 个位置最终留下的，是最后一次覆盖到它的那个字母。

输入示例 3

10 10 15
8 9 B
6 7 C
5 8 D
10 6 E
8 5 F
3 10 G
7 3 H
4 6 I
3 1 J
10 2 K
3 6 L
3 3 M
2 5 N
9 1 O
1 4 P

输出示例 3

PPPPNLGGGG
ONNNNLGGGG
OMMLLLGGGG
OKIIIIDDBA
OKHFFEDDBA
OKHFFECBBA
OKHFFEBBBA
OKFFFEBBBA
OKEEEEAAAA
KKEEEEAAAA

示例 3 说明

注意第 $9$ 行第 $1$ 列是 O（来自第 $14$ 次操作 9 1 O），而第 $10$ 行第 $1$ 列是 K（第 $14$ 次操作覆盖不到第 $10$ 行，只有第 $10$ 次操作 10 2 K 覆盖到了）。

约束条件

• $1 \le H, W$
• $H \times W \le 10^6$
• $1 \le Q \le 2 \times 10^5$
• $1 \le R_i \le H$
• $1 \le C_i \le W$
• $X_i$ 是大写英文字母
• 所有输入的数值均为整数