Dust Cleaning Bombs

Your room is divided into an $n\times m$ grid of tiles. Each tile at row $i$ and column $j$ initially contains a dust amount of $a_{i,j}$.

You have $k$ cleaning bombs. The $i$-th bomb is used on the tile at $(x_i, y_i)$ with power $p_i$. When a bomb is used, it reduces the dust on the tiles in layers as follows:

• The tile at $(x_i,y_i)$ has its dust reduced by $p_i^2$.
• The tiles in the first surrounding layer (all tiles with Chebyshev distance $1$ from $(x_i,y_i)$) have their dust reduced by $(p_i-1)^2$.
• The tiles in the second surrounding layer (Chebyshev distance $2$) have their dust reduced by $(p_i-2)^2$.
• \(\cdots\)
• The tiles in the $(p_i-1)$-th surrounding layer (Chebyshev distance $p_i-1$) have their dust reduced by $1$.

If a tile's dust is less than the reduction amount at any bomb explosion, its dust becomes $0$. Note that if a tile is affected by multiple bombs, the reductions are applied sequentially and the dust never drops below $0$.

Output the final dust amount on each tile after all $k$ bomb operations.

inputFormat

The first line contains three integers $n$, $m$, and $k$ — the number of rows, columns, and bombs, respectively.

The next $n$ lines each contain $m$ integers, where the $j$-th integer in the $i$-th line is $a_{i,j}$, the initial dust on that tile.

The following $k$ lines each contain three integers $x_i$, $y_i$, and $p_i$, representing the row, column, and power of the $i$-th bomb. All indices are 1-indexed.

outputFormat

Output $n$ lines, each containing $m$ integers. The $j$-th integer in the $i$-th line should be the final dust amount on the corresponding tile after all bomb operations.

sample

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

4 4 4
4 1 4
4 4 4