Inherit the Spheres

In the year 2xxx, an expedition team landing on a planet found strange objects made by an ancient species that once lived there. Each object is a transparent box containing opaque solid spheres, and the team also found many lithographs that seem to record the positions and radii of the spheres.

At first the purpose of these objects was unknown, but Professor Zambendorf discovered that the cross section cut by a horizontal plane plays an important role: as the plane slides from the bottom of an object to the top, the cross section changes.

Each cross section is a set of discs, where every disc is the cross section of one solid sphere. Discs that intersect or touch each other merge into a single connected figure. The professor found that information is encoded in how the number of connected figures changes as the plane rises.

For example, in the object described by the first example dataset below, the number of connected figures changes as $0, 1, 2, 1, 2, 3, 2, 1$, and $0$ at $z = 0.0000, 162.0000, 167.0000, 173.0004, 185.0000, 191.9996, 198.0000, 203.0000$, and $205.0000$, respectively. Writing $1$ for each increment and $0$ for each decrement, this sequence of changes is expressed by the $8$-bit binary number $11011000$.

To help further analysis, write a program that determines these transitions as the horizontal plane slides from the bottom ($z = 0$) to the top ($z = 36000$).

The input is a sequence of datasets. Each dataset begins with a line containing a positive integer $N$, the number of spheres. It is followed by $N$ lines, each describing one sphere with four positive integers $X_i, Y_i, Z_i$, and $R_i$ ($i = 1, \dots, N$): the center $(X_i, Y_i, Z_i)$ and the radius $R_i$ of the $i$-th sphere.

You may assume $1 \le N \le 100$, $1 \le R_i \le 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$. The $i$-th solid sphere is the set of all points $(x, y, z)$ with $(x - X_i)^2 + (y - Y_i)^2 + (z - Z_i)^2 \le R_i^2$.

A sphere may contain other spheres. No two spheres are mutually tangent. Every value among the $Z_i \pm R_i$ and the minimum and maximum $z$-coordinates of the circle formed by the intersection of any two spheres differs from every other such value by at least $0.01$.

The end of the input is indicated by a line containing a single zero.

For each dataset, output two lines. The first line contains an integer $M$, the number of changes in the number of connected figures. The second line contains an $M$-bit binary number expressing those changes: a $1$ for each increment and a $0$ for each decrement, in order of increasing $z$.