Nuclear Fusion Energy in a Hexagonal Control Center

The nuclear control center can be regarded as a hexagonal array of modules. Each module stores a non‐negative integer representing its nuclear fusion energy. The modules are arranged in a hexagon and are uniquely identified by a triplet of integers (x, y, z) according to the following rule:

• The center has coordinate (0,0,0).
• If a module lies on one of the three axes (which are rays emanating from the origin at mutual angles of \(120^\circ\)), its coordinate is simply the distance (in steps) from the origin along that axis.
• For a module not lying on an axis, the plane is divided into three regions. In each region the module is assigned a coordinate of the form (a, b, 0) (or a cyclic permutation) where a and b are the numbers of steps required along the two bordering axes.

Any module in the control center (i.e. with distance from the origin not exceeding \(n\)) can be uniquely labeled by such a triplet. The hexagonal distance between two modules is defined as the minimum number of modules (including both endpoints) that one must pass through when traveling from one module to the other along adjacent modules. It can be shown that if a module is given the label (x, y, z), then by defining its axial coordinates as \[ q=x-y,\quad r=y-z, \] the hexagonal distance between two modules with labels (x₁, y₁, z₁) and (x₂, y₂, z₂) is \[ d=\frac{|q_1-q_2|+|r_1-r_2|+|q_1+r_1-q_2-r_2|}{2}, \] where \(q_i=x_i-y_i\) and \(r_i=y_i-z_i\) for \(i=1,2\).

The control center consists of all modules whose hexagonal distance from the origin does not exceed \(n\). Initially, every module’s energy is 0. Then, \(m\) operations are performed. An operation is given in the format

[ \verb!x y z r k! ]

which means that the module at coordinate \((x,y,z)\) is activated. This activation causes the nuclear fusion energy of every module in the control center whose hexagonal distance from \((x,y,z)\) is at most \(r\) to increase by \(k\). It is guaranteed that the activated coordinate is within the control center.

Your task is to compute the final energy stored in every module after all \(m\) operations have been executed. In the output, list the energy values of all modules (sorted first by their hexagonal distance from the origin in ascending order and then in lexicographical order of \(x, y, z\)) on one line, separated by a single space.

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(0\le n\le \text{small}\), \(m\ge 1\)), indicating that the control center contains all modules with hexagonal distance \(\le n\) from the origin, and that \(m\) operations will be performed.

Each of the next \(m\) lines contains five integers: \(x\), \(y\), \(z\), \(r\) and \(k\). It is guaranteed that the coordinate \((x,y,z)\) is a valid module in the control center and that \(r\ge 0\), \(k\ge 0\).

outputFormat

Output a single line containing the final energy values of all modules in the control center (sorted first by increasing hexagonal distance from the origin and then lexicographically by \(x, y, z\)). The energy values should be separated by a single space.

sample

1 1
0 0 0 1 5

5 5 5 5 5 5 5