CF631B.Print Check

Kris works in a large company "Blake Technologies". As a best engineer of the company he was assigned a task to develop a printer that will be able to print horizontal and vertical strips. First prototype is already built and Kris wants to tests it. He wants you to implement the program that checks the result of the printing.

Printer works with a rectangular sheet of paper of size n × m. Consider the list as a table consisting of n rows and m columns. Rows are numbered from top to bottom with integers from 1 to n, while columns are numbered from left to right with integers from 1 to m. Initially, all cells are painted in color 0.

Your program has to support two operations:

1. Paint all cells in row r__i in color a__i;
2. Paint all cells in column c__i in color a__i.

If during some operation i there is a cell that have already been painted, the color of this cell also changes to a__i.

Your program has to print the resulting table after k operation.

Kris 就职于一家大型公司“Blake Technologies”。作为公司最优秀的工程师，他被委派开发一款能够打印水平和垂直条带的打印机。首个原型机已经建成，Kris 希望对其进行测试。他希望你编写一个程序来验证打印结果。

该打印机使用一张大小为 $n \times m$ 的矩形纸张。将这张纸视为一个由 $n$ 行和 $m$ 列组成的表格。行从上到下依次编号为 $1$ 至 $n$，列从左到右依次编号为 $1$ 至 $m$。初始时，所有格子的颜色均为 $0$。

你的程序需支持以下两种操作：

1. 将第 $r_i$ 行的所有格子涂成颜色 $a_i$；
2. 将第 $c_i$ 列的所有格子涂成颜色 $a_i$。

若在某次操作 $i$ 中，某个格子此前已被涂色，则其颜色也更新为 $a_i$。

你的程序需输出经过 $k$ 次操作后的最终表格。

The first line of the input contains three integers n, m and k (1  ≤  n,  m  ≤ 5000, n·m ≤ 100 000, 1 ≤ k ≤ 100 000) — the dimensions of the sheet and the number of operations, respectively.

Each of the next k lines contains the description of exactly one query:

• 1 r__i a__i (1 ≤ r__i ≤ n, 1 ≤ a__i ≤ 109), means that row r__i is painted in color a__i;
• 2 c__i a__i (1 ≤ c__i ≤ m, 1 ≤ a__i ≤ 109), means that column c__i is painted in color a__i.

输入的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n, m \le 5000$，$n \cdot m \le 100\,000$，$1 \le k \le 100\,000$），分别表示纸张的尺寸和操作次数。

接下来的 $k$ 行，每行描述一个查询：

• 1 r_i a_i（$1 \le r_i \le n$，$1 \le a_i \le 10^9$），表示将第 $r_i$ 行涂成颜色 $a_i$；
• 2 c_i a_i（$1 \le c_i \le m$，$1 \le a_i \le 10^9$），表示将第 $c_i$ 列涂成颜色 $a_i$。

Print n lines containing m integers each — the resulting table after all operations are applied.

输出 n 行，每行包含 m 个整数——即所有操作执行完毕后的结果表格。

The figure below shows all three operations for the first sample step by step. The cells that were painted on the corresponding step are marked gray.

下图逐步展示了第一个样例中的全部三种操作。在对应步骤中被涂色的单元格以灰色标记。