Problem Statement

Consider filling the cells of a sheet of grid paper with $H$ cells vertically and $W$ cells horizontally using 2 colors of ink.

The cell in the $R$-th row from the top and the $C$-th column from the left is denoted by $(R,C)$. The top-left cell is $(1,1)$ and the bottom-right cell is $(H,W)$.
Cell $(R,C)$ is initially painted in color $A_{R,C}$.

For a cell $(R,C)$ and a cell $(R^\prime,C^\prime)$ adjacent to it, when the 2 cells have the same color, we say that "$(R,C)$ and $(R^\prime,C^\prime)$ are connected".
Also, when $(R,C)$ and $(R^\prime,C^\prime)$ are connected and $(R^\prime,C^\prime)$ and $(R^{\prime\prime},C^{\prime\prime})$ are connected, we say that $(R,C)$ and $(R^{\prime\prime},C^{\prime\prime})$ are connected as well.
Here, "adjacent" refers to the case where the Manhattan distance between $(R,C)$ and $(R^\prime,C^\prime)$ is $1$, that is, where $(R^\prime,C^\prime)$ is one of $(R+1,C), (R-1,C), (R,C+1), (R,C-1)$.

You are given $Q$ queries of the form "fill all cells connected to cell $(R,C)$ with color $X$".
Output the color of each cell of the grid paper after all $Q$ fills have been performed.

In short, this is the "fill" tool of a paint program.

Input

$H$ $W$
$A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,W}$
$\vdots$
$A_{H,1}$ $A_{H,2}$ $\dots$ $A_{H,W}$
$Q$
$R_1$ $C_1$ $X_1$
$\vdots$
$R_Q$ $C_Q$ $X_Q$

All input values are integers and satisfy the following constraints.
$1 \leq H,W \leq 200$
$1 \leq Q \leq 5 \times 10^4$
$0 \leq A_{R,C}, X_i \leq 1$
$1 \leq R_i \leq H$
$1 \leq C_i \leq W$

Output

$A^\prime_{1,1}$ $A^\prime_{1,2}$ $\dots$ $A^\prime_{1,W}$
$\vdots$
$A^\prime_{H,1}$ $A^\prime_{H,2}$ $\dots$ $A^\prime_{H,W}$

Output the color $A^\prime_{R,C}$ of each cell after the fills.

Sample

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

0 1 0
1 1 1
0 1 0

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

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

0 0 1 0
1 1 * 1
0 1 * *
1 1 1 1

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

0 0 * 0
* * * *
0 * * *
* * * *

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

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

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

5 3
1 0 1
0 0 1
1 1 0
1 0 1
1 0 1
3
1 1 0
4 3 1
5 3 0

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