← 返回题目列表

Codeforces · 631/B

B. 打印检查

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

Kris 在一家大公司“Blake Technologies”工作。作为公司最优秀的工程师,他被指派开发一台能够打印水平和垂直条带的打印机。第一个原型已经建成,克里斯想要对其进行测试。他希望你实现检查打印结果的程序。

打印机使用尺寸为 n × m 的矩形纸张。将该列表视为由 n 行和 m 列组成的表。行从上到下用 1 到 n 的整数编号,列从左到右用 1 到 m 的整数编号。最初,所有单元格都涂成颜色 0。

您的程序必须支持两种操作:

1. 将 ri 行中的所有单元格涂成颜色 ai;
2. 将 ci 列中的所有单元格涂成颜色 ai。

如果在某些操作 i 中有一个单元格已被绘制,则该单元格的颜色也会更改为 ai。

你的程序必须在 k 操作后打印结果表。

输入

输入的第一行包含三个整数 n、m 和 k (1 ≤ n, m ≤ 5000, n·m ≤ 100 000, 1 ≤ k ≤ 100 000) – 分别是纸张的尺寸和操作的数量。

接下来的 k 行中的每一行都包含一个查询的描述:

- 1 ri ai (1 ≤ ri ≤ n, 1 ≤ ai ≤ 109),表示第ri行被涂成颜色ai;
- 2 ci ai (1 ≤ ci ≤ m, 1 ≤ ai ≤ 109),表示列 ci 被涂成颜色 ai。

输出

打印 n 行,每行包含 m 个整数 - 应用所有操作后的结果表。

示例

输入 #1

3 3 3
1 1 3
2 2 1
1 2 2

输出 #1

3 1 3
2 2 2
0 1 0

输入 #2

5 3 5
1 1 1
1 3 1
1 5 1
2 1 1
2 3 1

输出 #2

1 1 1
1 0 1
1 1 1
1 0 1
1 1 1

注意

下图逐步显示了第一个示例的所有三个操作。相应步骤上绘制的单元格标记为灰色。