{"problem":{"name":"高效清理","description":{"content":"真寻的房间太大了，但是作为家里蹲，她又懒得打扫，于是美波里发明了一款清理炸弹给真寻使用。 真寻的房间由 $n$ 行 $m$ 列的方砖组成，第 $i$ 行第 $j$ 列的方砖上的灰尘数量为 $a_{i,j}$。 真寻将会使用 $k$ 次清理炸弹，第 $i$ 次她会在第 $x_i$ 行第 $y_i$ 列的方砖上使用能量值为 $p_i$ 的清理炸弹，这将会使 $(x_i,y_i)$ 的灰尘数量减少 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10266"},"statements":[{"statement_type":"Markdown","content":"真寻的房间太大了，但是作为家里蹲，她又懒得打扫，于是美波里发明了一款清理炸弹给真寻使用。\n\n真寻的房间由 $n$ 行 $m$ 列的方砖组成，第 $i$ 行第 $j$ 列的方砖上的灰尘数量为 $a_{i,j}$。\n\n真寻将会使用 $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$。\n\n当然，灰尘数量不能为负数，所以若某次操作前，某块方砖上的灰尘数量小于它将要减少的灰尘数量，那么它的灰尘数量将变为 $0$。\n\n请你输出真寻使用完 $k$ 次清理炸弹后，每块方砖上的灰尘数量。\n\n## Input\n\n第一行三个整数 $n,m,k$，分别表示方砖行数、列数及操作次数；\n\n接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 列的整数表示 $a_{i,j}$，描述每一块方砖上的灰尘数量；\n\n接下来 $k$ 行，第 $i$ 行三个整数 $x_i,y_i,p_i$，描述一次操作。\n\n## Output\n\n共 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 列的整数表示方砖 $(i,j)$ 上最终的灰尘数量。\n\n[samples]\n\n## Background\n\n清理炸弹设计理念图：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/mjfmevu2.png)\n\n## Note\n\n**样例** $\\mathbf{1}$ **解释**\n\n第一次操作在方砖 $(2,4)$ 上使用能量值为 $2$ 的“清理炸弹”，使 $(2,4)$ 的灰尘数量减少 $4$，$(1,3),(1,4),(1,5),(2,3),(2,5),(3,3),(3,4),(3,5)$ 的灰尘数量减少 $1$；\n\n第二次操作在方砖 $(3,3)$ 上使用能量值为 $2$ 的“清理炸弹”，使 $(3,3)$ 的灰尘数量减少 $4$，$(2,2),(2,3),(2,4),(3,2),(3,4),(4,2),(4,3),(4,4)$ 的灰尘数量减少 $1$。\n\n**数据范围**\n\n对于所有数据，$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$。\n\n本题共 $11$ 个数据点，**采用捆绑测试**，子任务及数据点分配如下：\n\n| 子任务编号 | 数据点编号 | 特殊性质 | 分值 |\n| :-: | :-: | :-: | :-: |\n| $0$ | $1\\sim 4$ | $n,m,k\\leq 300$ | $10$ |\n| $1$ | $5$ | $p_i\\leq 3$ | $10$ |\n| $2$ | $6\\sim 7$ | $k\\leq 10^3$ | $20$ |\n| $3$ | $8\\sim 9$ | $n,m\\leq 300$ | $20$ |\n| $4$ | $10\\sim 11$ | 无特殊限制 | $40$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10266","tags":["前缀和","差分"],"sample_group":[["4 5 2\n7 5 4 6 5\n2 4 7 9 5\n6 4 5 3 5\n1 2 3 0 7\n2 4 2\n3 3 2","7 5 3 5 4\n2 3 5 4 4\n6 3 0 1 4\n1 1 2 0 7"],["6 7 3\n6 4 7 8 4 6 1\n4 5 4 6 7 5 9\n1 4 3 0 7 1 3\n4 6 0 7 9 0 0\n1 2 3 4 4 5 8\n4 7 6 8 7 4 9\n5 5 3\n2 3 4\n3 6 2","2 0 0 0 0 5 1 \n0 0 0 0 2 3 8 \n0 0 0 0 1 0 1 \n0 2 0 0 0 0 0 \n0 1 1 0 0 0 7 \n4 7 5 4 3 0 8 "]],"created_at":"2026-03-03 11:09:25"}}