Description

核控制中心可以看作由若干个正六边形模块组成的六边形阵列。阵列当中每个模块都可以储存核融合能量（一个非负整数）。左图就是一个核控制中心示意图。

我们使用如下方式对控制中心中每个模块进行标号。

以阵列中心为原点延伸出三根射线作为三根轴，每两根轴之间的夹角为 $120\degree$。这三根轴将平面划分为了三个部分。每个模块都可以使用一个三元组 $(x,y,z)$ 描述它的坐标，表示从原点开始按如图所示的 $x,y,z$ 方向各走若干步之后到达的地方。为了防止出现多个坐标表示同一个模块的情况，做出如下规定：原点的坐标为 $(0,0,0)$；对于中心在坐标轴上的模块，它的坐标就是从原点向所在轴走过的距离；对于其他情况，我们将平面划分为了三个区域（如第二张图的红蓝绿三个区域），一个模块的坐标就是沿着它两侧的轴分别需要走的距离。例如模块 $P$ 的坐标为 $(2,4,0)$。容易发现，每个坐标唯一对应一个模块，一个模块唯一对应一个坐标。

同时定义，两个模块的距离为从一个模块到另一个模块需要经过模块（包括起点和终点）的最少个数。在第一张图中，红色部分的模块到其中心距离均不超过 $3$，绿色部分的模块到其中心距离均不超过 $3$，而蓝色部分的模块到其中心距离均不超过 $2$。

核控制中心可以视为到达原点距离不超过 $n$ 的模块组成的阵列。现在阿空会执行以下操作 $m$ 次：

• $\colorbox{f0f0f0}{\verb!x y z r k!}$ ：激活坐标为 $(x,y,z)$ 的模块。它会使控制中心中到它距离不超过 $r$ 的所有的模块的核融合能量增加 $k$。保证 $(x,y,z)$ 在控制中心当中。

现在需要求出，执行完 $m$ 个操作后，每个模块里核融合能量值。

Input Format

• 第一行共两个正整数 $n,m$，分别表示控制中心的大小、操作个数。
• 接下来 $m$ 行，每行有五个整数 $x_i,y_i,z_i,r_i,k_i$，表示将距离 $(x_i,y_i,z_i)$ 不超过 $r$ 的所有模块的核融合能量增加 $k_i$。

Output Format

• 共一行，若干个整数。按照从左往右从上往下的顺序，依次输出每个模块当中核融合能量值。每两个值之间使用空格隔开。

下图当中的红色箭头展示了「从左往右从上往下」的顺序。

4 3
0 1 1 3 4
3 0 3 3 3
1 0 0 2 2

4 4 4 0 4 4 4 4 3 4 4 4 4 7 3 0 4 4 6 9 3 3 0 4 6 6 5 3 0 0 2 2 3 0 0 0 0

Hint

样例 $2$ 见下发的附件 $\textbf{\textit{nuclear2.in/nuclear2.ans}}$。
样例 $3$ 见下发的附件 $\textbf{\textit{nuclear3.in/nuclear3.ans}}$。满足特殊性质 $\text{A}$（见下文）。
样例 $4$ 见下发的附件 $\textbf{\textit{nuclear4.in/nuclear4.ans}}$。满足特殊性质 $\text{B}$（见下文）。
样例 $5$ 见下发的附件 $\textbf{\textit{nuclear5.in/nuclear5.ans}}$。

样例 1 解释

如图所示（所有未标出数字的模块的核融合能量值均为 $0$）：

按照从左往右、从上往下的顺序依次输出每个数值，即可得到答案。

数据范围及约定

本题共有 $20$ 个测试点，每个测试点 $5$ 分。最终分数为所有测试点分数之和。

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \textbf{Task} & \bm{n\le } & \bm{m\le} & \textbf{特殊性质} \cr\hline 1\sim 3 & 10 & 10 & \text{A} \cr\hline 4\sim 7 & 100 & 300 & - \cr\hline 8\sim 10 & 800 & 3\times 10^5 & \text{B} \cr\hline 11\sim 14 & 800 & 3\times 10^5 & \text{A} \cr\hline 15\sim 20 & 800 & 3\times 10^5 & - \cr\hline \end{array}$$

特殊性质 $\textbf{A}$：保证对于第 $i$ 次操作，被激活的模块到控制中心边缘上的模块的距离不小于 $r_i$。
特殊性质 $\textbf{B}$：保证对于第 $i$ 次操作，被激活的模块均为 $(0,0,0)$。

对于全部数据，保证 $n\le 800$，$m\le 3\times 10^5$，$1\le k_i\le 5\times 10^3$，$1\le r_i\le 10^9$。每次激活的模块都在控制中心里。