You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

清理炸弹设计理念图：

题目描述

真寻的房间太大了，但是作为家里蹲，她又懒得打扫，于是美波里发明了一款清理炸弹给真寻使用。

真寻的房间由 $n$ 行 $m$ 列的方砖组成，第 $i$ 行第 $j$ 列的方砖上的灰尘数量为 $a_{i,j}$。

真寻将会使用 $k$ 次清理炸弹，第 $i$ 次她会在第 $x_i$ 行第 $y_i$ 列的方砖上使用能量值为 $p_i$ 的清理炸弹，这将会使 $(x_i,y_i)$ 的灰尘数量减少 ${p_i}^2$，$(x_i,y_i)$ 外围第一圈的方砖上的灰尘数量减少 $(p_i-1)^2$，外围第二圈的方砖上的灰尘数量减少 $(p_i-2)^2$ $\cdots$ 外围第 $(p_i-1)$ 圈的方砖上的灰尘数量减少 $1$。

当然，灰尘数量不能为负数，所以若某次操作前，某块方砖上的灰尘数量小于它将要减少的灰尘数量，那么它的灰尘数量将变为 $0$。

请你输出真寻使用完 $k$ 次清理炸弹后，每块方砖上的灰尘数量。

输入格式

第一行三个整数 $n,m,k$，分别表示方砖行数、列数及操作次数；

接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 列的整数表示 $a_{i,j}$，描述每一块方砖上的灰尘数量；

接下来 $k$ 行，第 $i$ 行三个整数 $x_i,y_i,p_i$，描述一次操作。

输出格式

共 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 列的整数表示方砖 $(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 

提示

样例 $\mathbf{1}$ 解释

第一次操作在方砖 $(2,4)$ 上使用能量值为 $2$ 的“清理炸弹”，使 $(2,4)$ 的灰尘数量减少 $4$，$(1,3),(1,4),(1,5),(2,3),(2,5),(3,3),(3,4),(3,5)$ 的灰尘数量减少 $1$；

第二次操作在方砖 $(3,3)$ 上使用能量值为 $2$ 的“清理炸弹”，使 $(3,3)$ 的灰尘数量减少 $4$，$(2,2),(2,3),(2,4),(3,2),(3,4),(4,2),(4,3),(4,4)$ 的灰尘数量减少 $1$。

数据范围

对于所有数据，$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$。

本题共 $11$ 个数据点，采用捆绑测试，子任务及数据点分配如下：

子任务编号	数据点编号	特殊性质	分值
$0$	$1\sim 4$	$n,m,k\leq 300$	$10$
$1$	$5$	$p_i\leq 3$
$2$	$6\sim 7$	$k\leq 10^3$	$20$
$3$	$8\sim 9$	$n,m\leq 300$
$4$	$10\sim 11$	无特殊限制	$40$