Inherit the Spheres#3202
In the year , an expedition team landing on a planet found strange objects created by an ancient species living on that planet. These are transparent boxes containing opaque solid spheres (Figure 1). There are also many lithographs that appear to contain the positions and radii of these spheres.
Figure 1. A strange object
Initially, their purpose was unknown, but Professor Zambendorf discovered that the cross section formed by a horizontal plane plays an important role. For example, the cross section of an object changes as in Figure 2 when the plane is slid from bottom to top.
Figure 2. Cross sections at different positions
He eventually found that some information is expressed by the transitions in the number of connected figures in the cross section, where each connected figure is a union of discs that intersect or touch each other, and each disc is a cross section of a corresponding solid sphere. For example, in Figure 2, whose geometry is described in the first sample dataset later, the number of connected figures changes as , , , , , , , , , at z = 0.0000, , , , , , , , and , respectively. By assigning for an increment and for a decrement, these transitions can be represented as an -bit binary number .
To support further analysis, write a program to identify the transitions as the horizontal plane is slid from bottom (z = 0) to top (z = 36000).
The input consists of a series of datasets. Each dataset begins with a line containing a positive integer, which indicates the number of spheres in the dataset. It is followed by lines describing the centers and radii of the spheres. Each of the lines contains four positive integers X_i, Y_i, Z_i, and R_i (i = 1, \ldots, N), representing the center and radius of the -th sphere, respectively.
You may assume that 1 \leq N \leq 100, 1 \leq R_i \leq 2000, 0 < X_i - R_i < X_i + R_i < 4000, 0 < Y_i - R_i < Y_i + R_i < 16000, and 0 < Z_i - R_i < Z_i + R_i < 36000. Each solid sphere is defined as the set of all points (x, y, z) satisfying (x - X_i)^2 + (y - Y_i)^2 + (z - Z_i)^2 \leq R_i^2.
A sphere may contain other spheres. No two spheres are mutually tangent. Each Z_i \pm R_i and the minimum or maximum coordinate of a circle formed by the intersection of any two spheres differ from each other by at least .
The end of the input is indicated by a line with a single zero.
For each dataset, your program should output two lines. The first line should contain an integer indicating the number of transitions. The second line should contain an -bit binary number that expresses the transitions in the number of connected figures, as described above.
Example 1