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
注意
下图逐步显示了第一个示例的所有三个操作。相应步骤上绘制的单元格标记为灰色。