← 返回题目列表

AtCoder · abc464_e

E. 填充矩形查询

中文机器翻译题面 查看原题

分数: 450 点

问题陈述

有一个 H \times W 网格。最初,每个细胞都有 上面写着 A 。牢房位于 i从顶部算起的第行和 j从左边算起的第列表示为 (i, j).

我们将表演 Q 操作按顺序进行。
在 i-th 操作,用左上角单元格覆盖矩形中的所有单元格 (1, 1) 和右下单元格 (R_i, C_i) 与大写英文字母 X_i.

执行完所有操作后输出网格。

约束

  • 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 是一个大写英文字母。
  • 所有输入数字均为整数。

输入

输入由标准输入按以下格式给出:

H W Q
R_1 C_1 X_1
R_2 C_2 X_2
\vdots
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

操作如图所示进行。


示例输入 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

示例输入 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