Background

A design concept diagram of the cleaning bomb:

Problem Description

Mahiro's room is too large, but as a shut-in, she is too lazy to clean it, so Mihari invented a cleaning bomb for Mahiro to use.

Mahiro's room consists of tiles arranged in $n$ rows and $m$ columns. The amount of dust on the tile in row $i$ and column $j$ is $a_{i,j}$.

Mahiro will use the cleaning bomb $k$ times. In the $i$-th use, she uses a cleaning bomb with energy value $p_i$ on the tile at row $x_i$, column $y_i$. This decreases the dust on $(x_i,y_i)$ by ${p_i}^2$, decreases the dust on the tiles in the first outer ring around $(x_i,y_i)$ by $(p_i-1)^2$, decreases the dust on the tiles in the second outer ring by $(p_i-2)^2$, $\cdots$, and decreases the dust on the tiles in the $(p_i-1)$-th outer ring by $1$.

Of course, the dust amount cannot be negative, so if before an operation, the dust on a tile is smaller than the amount it should be decreased by, then its dust amount becomes $0$.

Please output the dust amount on each tile after Mahiro finishes using the cleaning bomb $k$ times.

Input Format

The first line contains three integers $n,m,k$, representing the number of tile rows, tile columns, and the number of operations.

Next, there are $n$ lines, each containing $m$ integers. The integer in row $i$ and column $j$ is $a_{i,j}$, describing the dust amount on each tile.

Next, there are $k$ lines. The $i$-th line contains three integers $x_i,y_i,p_i$, describing one operation.

Output Format

Output $n$ lines, each containing $m$ integers. The integer in row $i$ and column $j$ represents the final dust amount on tile $(i,j)$.

4 5 2
7 5 4 6 5
2 4 7 9 5
6 4 5 3 5
1 2 3 0 7
2 4 2
3 3 2

7 5 3 5 4
2 3 5 4 4
6 3 0 1 4
1 1 2 0 7

6 7 3
6 4 7 8 4 6 1
4 5 4 6 7 5 9
1 4 3 0 7 1 3
4 6 0 7 9 0 0
1 2 3 4 4 5 8
4 7 6 8 7 4 9
5 5 3
2 3 4
3 6 2

2 0 0 0 0 5 1 
0 0 0 0 2 3 8 
0 0 0 0 1 0 1 
0 2 0 0 0 0 0 
0 1 1 0 0 0 7 
4 7 5 4 3 0 8 

Hint

Sample $\mathbf{1}$ Explanation

In the first operation, a “cleaning bomb” with energy value $2$ is used on tile $(2,4)$, which decreases the dust on $(2,4)$ by $4$, and decreases the dust on $(1,3),(1,4),(1,5),(2,3),(2,5),(3,3),(3,4),(3,5)$ by $1$.

In the second operation, a “cleaning bomb” with energy value $2$ is used on tile $(3,3)$, which decreases the dust on $(3,3)$ by $4$, and decreases the dust on $(2,2),(2,3),(2,4),(3,2),(3,4),(4,2),(4,3),(4,4)$ by $1$.

Constraints

For all testdata, $1\leq n,m,p_i\leq 10^3$, $1\leq k\leq 10^6$, $0\leq a_{i,j}\leq 10^{12}$, $1\leq x_i\leq n$, $1\leq y_i\leq m$.

This problem has $11$ test points and uses bundled tests. The subtasks and test point allocation are as follows:

Translated by ChatGPT 5