Background

To obtain energy by using nuclear fusion, Moriya Shrine built a huge nuclear fusion control center in the Former Hell. The control center is shaped like a double-layer "Bagua furnace", and it tightly controls the precise operation of nuclear fusion through various circuits. Okuu, who has gained the power of Yatagarasu, will ignite sacred fire at the center of the nuclear reactor.

However, the regular octagonal "Bagua furnace" is not convenient for expansion and maintenance. To implement circuits more easily, the kappa plans to modularize and refit the nuclear control center to make the furnace easier to maintain. Specifically, the kappa plans to design the control center as a huge structure composed of many regular hexagons.

Okuu, endowed with divine power, can activate some modules one by one, and the activated modules will quickly affect other modules within a certain range. Energy is produced through the connections between modules.

But because Okuu is absent-minded, after activating modules many times, it can no longer remember the amount of fusion energy in each module. Can you help it?

Problem 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