P9117 [Spring Test 2023] Coloring Game

One day, when Xiao D was browsing Moments, he saw a video of a game. The game is called Coloring Game. In the video, the game screen is a grid with $n$ rows and $m$ columns. At the beginning, every cell is white (represented by the number $0$). There is a colored brush on the left side of each row and above each column. After the player clicks a brush, it will paint the entire row (or entire column) to its right (or below) into the same color. **The original colors of the cells in that row (or column) will all be overwritten by the new color.** The situation shown in the figure below can be obtained by first painting the first column red, and then painting the first row blue. If we now choose to paint the third column green, then all cells inside the green boxes in the figure will become green.  Xiao D wants to use his own program to play the game in the video. During programming, he encountered some difficulties in implementing the coloring logic, so he asked you for help and hopes you can finish the code for the coloring logic part. First, Xiao D will give you the number of rows and columns of the grid $n, m$, and then give $q$ operations. Each operation is represented by three integers $opt_i, x_i, c_i$: - If $opt_i = 0$, this operation paints row $x_i$ into color $c_i$. - If $opt_i = 1$, this operation paints column $x_i$ into color $c_i$. After all coloring operations are finished, you need to output the color at every position in the grid.

**This problem contains multiple test cases.** The first line contains a positive integer $T$, indicating the number of test cases. Then there are $T$ test cases. Each test case is in the following format: The first line contains three integers $n, m, q$, representing the number of rows and columns of the coloring board, and the number of coloring operations Xiao D performs. The next $q$ lines each contain three integers $opt_i, x_i, c_i$, representing one operation.

For each test case, output $n$ lines, each containing $m$ integers separated by single spaces. The $j$-th integer in the $i$-th line indicates the color of the cell at row $i$ and column $j$ after all coloring is completed.

**[Sample 1 Explanation]** Note that when a cell is not painted, its color is white, represented by the number $0$. **[Sample 2]** See paint/paint2.in and paint/paint2.ans in the contestant directory. **[Constraints]** For all data, it is guaranteed that: - $1 \leq T \leq 10$, $1 \leq n, m \leq 10^5$, $0 \leq q \leq 10^5$, $0 \leq c_i \leq 10^9$. - If $opt_i = 0$, then $1 \leq x_i \leq n$; if $opt_i = 1$, then $1 \leq x_i \leq m$. - In a single test, the sum of $n \cdot m$ over all test cases does not exceed $10^6$, and the sum of $q$ does not exceed $10^6$. |Test Point|$n \le$|$m \le$|$q \le$|Property A|Property B| |:-:|:-:|:-:|:-:|:-:|:-:| |1|$1$|$1$|$0$|√|√| |2|$1$|$1$|$1$|√|√| |3|$1$|$10$|$20$|√|√| |4|$1$|$10^5$|$10^5$|×|√| |5|$1$|$10^5$|$10^5$|×|√| |6|$1$|$10^5$|$10^5$|×|×| |7|$10$|$10$|$20$|√|√| |8|$50$|$50$|$100$|√|√| |9|$50$|$50$|$100$|√|×| |10|$1000$|$1000$|$2000$|×|√| |11|$1000$|$1000$|$2000$|×|×| |12|$1000$|$1000$|$2000$|×|×| |13|$1000$|$1000$|$10^5$|×|×| |14|$1000$|$1000$|$10^5$|×|×| |15|$10^5$|$10^5$|$10^5$|√|√| |16|$10^5$|$10^5$|$10^5$|√|√| |17|$10^5$|$10^5$|$10^5$|√|×| |18|$10^5$|$10^5$|$10^5$|√|×| |19|$10^5$|$10^5$|$10^5$|×|×| |20|$10^5$|$10^5$|$10^5$|×|×| Special Property A: It is guaranteed that, over all test cases in a test point, the sum of $q \cdot \max(n, m)$ does not exceed $10^7$. Special Property B: It is guaranteed that $opt_i = 1$. **[Reminder]** There are thousands of lines of data; clearing the first one is the most important. If you do not clear for multiple test cases, you will get zero points, and tears will fall in two lines. Translated by ChatGPT 5