菱形加一

题目描述

有一个 $n \times n$ 的正方形网格，初始时每个格子的值都为 $0$。网格的行和列均从 $1$ 开始编号。

接下来有 $m$ 次操作。第 $i$ 次操作给出三个整数 $x_i,y_i,d_i$，表示选择格子 $(x_i,y_i)$ 作为中心，将所有满足

的格子 $(r,c)$ 的值都加 $1$。如果这个菱形区域超出了正方形边界，只对正方形内的格子产生影响。

请输出所有操作结束后，每个格子的最终值。

输入格式

第一行包含两个整数 $n,m$。

接下来 $m$ 行，每行包含三个整数 $x_i,y_i,d_i$，表示一次操作。

输出格式

输出 $n$ 行，每行 $n$ 个整数。第 $r$ 行第 $c$ 个整数表示格子 $(r,c)$ 的最终值。

同一行相邻两个整数之间用一个空格分隔。

样例输入

5 3
3 3 1
1 1 2
5 3 1

样例输出

1 1 1 0 0
1 1 1 0 0
1 1 1 1 0
0 0 2 0 0
0 1 1 1 0

数据范围

$1 \le n \le 1000$，$0 \le m \le 200000$。

$1 \le x_i,y_i \le n$，$0 \le d_i \le 2n$。