One day, Little D saw a video of a game while scrolling through his social media feed.

The game is called "Coloring Game." The game interface in the video is an $n \times m$ grid. Initially, 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. When a player clicks on a brush, it paints the entire row (or column) to its right (or below it) with a specific color. The original colors of the cells in that row (or column) are overwritten by the newly painted color.

The situation shown in the figure below can be obtained by first painting the first column red, then painting the first row blue. If we then choose to paint the third column green, all cells within the green box in the figure will turn green.

Figure 1: Coloring Example

Little D wants to use a program he wrote to play the game from the video. During the programming process, Little D encountered some difficulties in implementing the coloring logic, so he turned to you for help. He hopes you can help him complete the code for the coloring logic.

First, Little D will give you the number of rows $n$ and columns $m$ of the grid, followed by $q$ operations. Each operation is represented by three integers $opt_i, x_i, c_i$:

• If $opt_i = 0$, this operation paints the $x_i$-th row with color $c_i$.
• If $opt_i = 1$, this operation paints the $x_i$-th column with color $c_i$.

After all coloring operations are finished, you need to output the color of each position in the grid.

Input

The input is read from the file paint.in.

This problem contains multiple test cases.

The first line contains a positive integer $T$, representing the number of test cases.

For each test case, the format is as follows:

The first line contains three integers $n, m, q$, representing the number of rows, the number of columns, and the number of coloring operations performed by Little D, respectively.

The next $q$ lines each contain three integers $opt_i, x_i, c_i$, representing an operation.

Output

The output is written to the file paint.out.

For each test case, output $n$ lines, each containing $m$ integers separated by single spaces.

The $j$-th integer in the $i$-th line represents the color of the cell at the $i$-th row and $j$-th column after all coloring operations are completed.

Examples

Input 1

2
5 5 9
1 5 1
0 4 0
1 4 1
0 3 0
1 3 1
0 2 0
1 2 1
0 1 0
1 1 1
3 3 3
0 1 2
0 3 1
1 1 3

Output 1

1 0 0 0 0
1 1 0 0 0
1 1 1 0 0
1 1 1 1 0
1 1 1 1 1
3 2 2
3 0 0
3 1 1

Note

Note that when a cell has not been painted, its color is white, represented by the number $0$.

Input 2

See paint/paint2.in in the contestant directory.

Output 2

See paint/paint2.ans in the contestant directory.

Constraints

For all data, it is guaranteed that: $1 \le T \le 10$, $1 \le n, m \le 10^5$, $0 \le q \le 10^5$, $0 \le c_i \le 10^9$. If $opt_i = 0$, then $1 \le x_i \le n$; if $opt_i = 1$, then $1 \le x_i \le m$. * The sum of $n \cdot m$ over all data in a single test point does not exceed $10^6$, and the sum of $q$ does not exceed $10^6$.

Special Property A: The sum of $q \cdot \max(n, m)$ over all test points does not exceed $10^7$. Special Property B: $opt_i = 1$ is guaranteed.

Note

There are countless data points, so clearing memory is the first priority. If you don't clear memory for multiple test cases, you will get a score of zero.