#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

2D Difference Painting - Classic Problems | Repovive

CLS55. 2D Difference Painting

2s256 MB

Start with an $n \times m$ grid of zeros. Apply $q$ rectangle increments, then print the final grid.

Constraints

$1 \le n, m \le 1000$
$1 \le q \le 2 \cdot 10^5$
$1 \le r_1 \le r_2 \le n$
$1 \le c_1 \le c_2 \le m$
$-10^9 \le x \le 10^9$

Input

\begin{array}{l} n \quad m \quad q \\ r_1 \quad c_1 \quad r_2 \quad c_2 \quad x \\ \vdots \end{array}

Output

\begin{array}{cccc} g_{1,1} & g_{1,2} & \cdots & g_{1,m} \\ g_{2,1} & g_{2,2} & \cdots & g_{2,m} \\ \vdots & \vdots & \ddots & \vdots \\ g_{n,1} & g_{n,2} & \cdots & g_{n,m} \end{array}

Samples

Input

3 4 2
1 1 2 3 5
2 2 3 4 -2

Explanation

Applying both rectangle updates leaves the final grid shown by the sample output.

Output

5 5 5 0
5 3 3 -2
0 -2 -2 -2

Input

2 2 1
1 1 2 2 7

Explanation

The single update covers the entire grid, so every cell becomes 7.

Output

7 7
7 7

Input

Explanation

Each cell receives the sum of the updates whose rectangles include it.

Output

4 0 -2
0 1 -1
0 1 -1

Start with an $n \times m$ grid of zeros. Apply $q$ rectangle increments, then print the final grid.

$1 \le n, m \le 1000$
$1 \le q \le 2 \cdot 10^5$
$1 \le r_1 \le r_2 \le n$
$1 \le c_1 \le c_2 \le m$
$-10^9 \le x \le 10^9$

\begin{array}{l} n \quad m \quad q \\ r_1 \quad c_1 \quad r_2 \quad c_2 \quad x \\ \vdots \end{array}

\begin{array}{cccc} g_{1,1} & g_{1,2} & \cdots & g_{1,m} \\ g_{2,1} & g_{2,2} & \cdots & g_{2,m} \\ \vdots & \vdots & \ddots & \vdots \\ g_{n,1} & g_{n,2} & \cdots & g_{n,m} \end{array}