Problem Description

Zhenxun's room is too large, but as a homebody, she is too lazy to clean it. Therefore, Minami invented a cleaning bomb for Zhenxun to use.

Zhenxun's room consists of \( n \) rows and \( m \) columns of square tiles, where the amount of dust on the tile at the \( i \)-th row and \( j \)-th column is \( a_{i,j} \).

Zhenxun will use the cleaning bomb \( k \) times. During the \( i \)-th use, she will place a cleaning bomb with energy value \( p_i \) on the tile at the \( x_i \)-th row and \( y_i \)-th column. This will reduce the dust amount on tile \( (x_i, y_i) \) by \( p_i^2 \), the tiles in the first outer ring by \( (p_i-1)^2 \), the tiles in the second outer ring by \( (p_i-2)^2 \), and so on, until the tiles in the \( (p_i-1) \)-th outer ring by \( 1 \).

Of course, the dust amount cannot be negative. Therefore, if the dust amount on a tile before an operation is less than the amount it is supposed to reduce, it will become \( 0 \).

Please output the final dust amount on each tile after Zhenxun uses the cleaning bomb \( k \) times.

Input Format

The first line contains three integers \( n \), \( m \), and \( k \), representing the number of rows, columns, and the number of operations, respectively.

The next \( n \) lines, each containing \( m \) integers, describe the dust amount \( a_{i,j} \) on each tile.

The next \( k \) lines, each containing three integers \( x_i \), \( y_i \), and \( p_i \), describe an operation.

Output Format

Output \( n \) lines, each containing \( m \) integers, where the integer at the \( i \)-th row and \( j \)-th column represents the final dust amount on tile \( (i, j) \).

Sample Input and Output

Input Sample #1

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

Output Sample #1

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

Input Sample #2

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

Output Sample #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 

Notes/Hints

Sample 1 Explanation

The first operation uses a cleaning bomb with energy value \( 2 \) on tile \( (2, 4) \), reducing the dust amount on \( (2, 4) \) by \( 4 \) and on the surrounding tiles \( (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 3), (3, 4), (3, 5) \) by \( 1 \).

The second operation uses a cleaning bomb with energy value \( 2 \) on tile \( (3, 3) \), reducing the dust amount on \( (3, 3) \) by \( 4 \) and on the surrounding tiles \( (2, 2), (2, 3), (2, 4), (3, 2), (3, 4), (4, 2), (4, 3), (4, 4) \) by \( 1 \).

Data Range

For all data, \( 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 consists of \( 11 \) data points, bundled testing, with subtasks and data point distribution as follows:

见题面 Input 部分

见题面 Output 部分