Swiss Cheese Slicing Problem

The International Cheese Processing Company has now turned its attention to cutting Swiss cheese—which contains variously sized spherical holes—into slices of equal weight. The uncut cheese is a cube measuring 100 mm on each side. The challenge is to cut it horizontally (parallel to the x-y plane) into s slices (each 100 mm wide and 100 mm high) so that every slice has exactly the same weight, despite the missing parts due to the holes.

By using precise sonar techniques, the locations and sizes of the holes can be determined up to micrometer precision. You may assume that each hole is a perfect sphere. For each hole given by its center coordinates (x, y, z) and radius r, its contribution (i.e. the missing cheese) is subtracted from the cheese volume. When a slice cuts through a hole, only the volume of the part of the sphere lying below the current height is removed. For a sphere with center (x, y, z₀) and radius r, if a horizontal cut is made at height z, the volume removed from the cheese by that hole is:

\(V_{hole}(z)=\begin{cases}0,& z\le z₀-r,\\ \pi\,h^2\Bigl(r-\frac{h}{3}\Bigr),& z₀-r<z<z₀+r,\\ \frac{4}{3}\pi r^3,& z\ge z₀+r,\end{cases}\) where \(h=z-(z₀-r)\).

The volume of the cheese (without holes) up to a height z is simply \(10000\,z\) (since 100×100=10000). Thus, the effective cheese volume up to height z is:

\(f(z)=10000\,z - \sum_{\text{holes}} V_{hole}(z).\)

Your task is to determine the thicknesses of the s slices such that each slice has exactly the same weight. In other words, if the total cheese volume after subtracting all holes is \(T\), each slice must have volume \(V=T/s\). You should compute the z-coordinate boundaries by numerically inverting \(f(z)\) by means of binary search. The thickness of the i-th slice is the difference between the i-th boundary and the previous boundary (with the bottom of the cheese at z=0).

inputFormat

The input begins with an integer s, the number of slices. The next line contains an integer n representing the number of holes. This is followed by n lines, each containing four numbers: x y z r, where (x, y, z) is the center of a spherical hole and r is its radius. All dimensions are in millimeters. The cheese block is a cube of size 100×100×100 mm.

outputFormat

Output s floating point numbers (each with at least 6 decimal places) representing the thickness (in mm) of each slice, in order from bottom to top, separated by a space.

sample

1
0

100.000000