烟花

题目描述

湖南人不语，只是一味的放着烟花...

在响彻整个除夕夜的烟花燃放之后，湖南成为了全国空气质量最差的省份。作为湖南气象局的监测员，你需要统计湖南每个区域的空气污染质量。

为了简化题意，我们假设湖南是一个长度和宽度均为 $n$ 的网格图，每个方格代表一个区域。我们定义每种烟花都有一个烟花等级 $P$，对于等级为 $P$ 的烟花，他会污染以自身为中心的边长为 $2P-1$ 的正方形周边区域，污染程度从中心向边际逐渐递减，假设烟花燃放区域记为第 $1$ 层，则第 $i$ 层周边区域受到的污染为 $(P-i+1)^2$。更加具体的描述可以参照下方的图例：

我们假设燃放中心的坐标为 $(e,5)$，以下是一个等级为 $5$ 的烟花所造成的影响：

现在，你得到了一份关于各个区域燃放烟花的统计报告，报告上共有 $m$ 条记录。你的任务是，在所有烟花燃放后，统计出各个区域的污染程度并输出。

输入格式

输入包含 $m + 1$ 行： 第一行包含两个整数 $n,m$，表示网格图的宽度和烟花燃放的记录。 接下来 $m$ 行，每行三个整数 $X,Y,P$，表示以坐标 $(X,Y)$ 为中心燃放了一个等级为 $P$ 的烟花。

为了降低题目难度，我们约定：

• 每一个烟花的污染区域都一定位于网格内，即保证 $\min({X-P+1,Y-P+1}) \ge 1$ 且 $\max({X+P-1,Y+P-1}) \le n$。

数据范围：

对于 $20\%$ 的数据，保证 $m \le 20$。 对于 $30\%$ 的数据，保证 $m \le 2000$。 对于所有数据，保证： $1 \le n \le 1000$ $1 \le m \le 10^6$

输出格式

输出一个大小为 $n \times n$ 的矩阵，表示最后各个区域的污染程度。

样例 #1

样例输入 #1

11 1
6 6 6

样例输出 #1

1 1 1 1 1 1 1 1 1 1 1 
1 4 4 4 4 4 4 4 4 4 1 
1 4 9 9 9 9 9 9 9 4 1 
1 4 9 16 16 16 16 16 9 4 1 
1 4 9 16 25 25 25 16 9 4 1 
1 4 9 16 25 36 25 16 9 4 1 
1 4 9 16 25 25 25 16 9 4 1 
1 4 9 16 16 16 16 16 9 4 1 
1 4 9 9 9 9 9 9 9 4 1 
1 4 4 4 4 4 4 4 4 4 1 
1 1 1 1 1 1 1 1 1 1 1