Description

The nuclear control center can be viewed as a hexagonal array made up of several regular hexagonal modules. Each module in the array can store fusion energy (a non-negative integer). The left figure is a schematic diagram of a control center.

We label each module in the control center in the following way.

Extend three rays from the center of the array as three axes, and the angle between every two axes is $120\degree$. These three axes divide the plane into three parts. Each module can be described by a triple $(x,y,z)$ as its coordinate, meaning the place reached after starting from the origin and walking several steps in the $x,y,z$ directions as shown. To avoid multiple coordinates representing the same module, we make the following rules: the origin has coordinate $(0,0,0)$; for a module whose center lies on an axis, its coordinate is the distance walked from the origin along that axis; for all other cases, we divide the plane into three regions (the red, blue, and green regions in the second figure), and the coordinate of a module is the distances that need to be walked along the two axes on its two sides, respectively. For example, module $P$ has coordinate $(2,4,0)$. It is easy to see that each coordinate corresponds to exactly one module, and each module corresponds to exactly one coordinate.

Also define that the distance between two modules is the minimum number of modules that must be passed through (including the start and end modules) to go from one module to the other. In the first figure, the distance from each module in the red part to its center is at most $3$, the distance from each module in the green part to its center is at most $3$, and the distance from each module in the blue part to its center is at most $2$.

The nuclear control center can be regarded as the array consisting of all modules whose distance to the origin is at most $n$. Now Okuu will perform the following operation $m$ times:

• $\colorbox{f0f0f0}{\verb!x y z r k!}$: Activate the module with coordinate $(x,y,z)$. This increases the fusion energy of all modules in the control center whose distance to it is at most $r$ by $k$. It is guaranteed that $(x,y,z)$ is inside the control center.

Now you need to output the fusion energy value in every module after all $m$ operations are finished.

Input Format

• The first line contains two positive integers $n,m$, representing the size of the control center and the number of operations.
• The next $m$ lines each contain five integers $x_i,y_i,z_i,r_i,k_i$, meaning to increase the fusion energy of all modules whose distance to $(x_i,y_i,z_i)$ is at most $r$ by $k_i$.

Output Format

• Output one line with several integers. In the order “from left to right, from top to bottom”, output the fusion energy value in each module. Separate every two values with a space.

The red arrows in the figure below show the order “from left to right, from top to bottom”.

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

Sample $2$ is provided in the attachments $\textbf{\textit{nuclear2.in/nuclear2.ans}}$.
Sample $3$ is provided in the attachments $\textbf{\textit{nuclear3.in/nuclear3.ans}}$. It satisfies special property $\text{A}$ (see below).
Sample $4$ is provided in the attachments $\textbf{\textit{nuclear4.in/nuclear4.ans}}$. It satisfies special property $\text{B}$ (see below).
Sample $5$ is provided in the attachments $\textbf{\textit{nuclear5.in/nuclear5.ans}}$.

Explanation for Sample 1

As shown in the figure (the fusion energy values of all modules without numbers marked are $0$):

Output each value in the order “from left to right, from top to bottom”, and you can get the answer.

Constraints and Notes

This problem has $20$ test points, and each test point is worth $5$ points. The final score is the sum of the scores of all test points.

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \textbf{Task} & \bm{n\le } & \bm{m\le} & \textbf{Special Properties} \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}$$

Special Property $\textbf{A}$: For the $i$-th operation, the distance from the activated module to any module on the boundary of the control center is not less than $r_i$.
Special Property $\textbf{B}$: For the $i$-th operation, the activated module is always $(0,0,0)$.

For all data, it is guaranteed that $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$. Each activated module is inside the control center.

Translated by ChatGPT 5