Being Solarly Systematic

Professor Braino Mars studies how solar systems form, and he runs every simulation by hand. He has asked you to automate one of them.

The simulation models how small planetoids collide over time to form larger planets. The space is divided into an $n_x \times n_y \times n_z$ grid of cubes, and each cube holds at most one planetoid. Every planetoid has a mass $m$, an initial location $(x, y, z)$, and a velocity $(v_x, v_y, v_z)$ giving the number of cubes it travels through in each dimension per second. For example, a planetoid that starts at $(1, 3, 2)$ with velocity $(3, -1, 2)$ is at $(4, 2, 4)$ after one second and at $(7, 1, 6)$ after two seconds.

Paths wrap around in every dimension. If that planetoid lives in an $8 \times 8 \times 8$ space, its next two locations are $(2, 0, 0)$ and $(5, 7, 2)$. Cube indices start at 0.

When two or more planetoids share a cube, they form one larger planetoid. Its mass is the sum of the colliding masses. Each component of its velocity is the sum of that component over the colliding planetoids, divided by the number that collided, truncated toward zero. A planetoid of mass 12 with velocity $(5, 3, -2)$ that collides with one of mass 10 and velocity $(8, -6, 1)$ gives mass 22 and velocity $(6, -1, 0)$.

Collisions are considered only at integer time steps. Once no more collisions can happen, the remaining planetoids count as planets.

The first line has four positive integers $n$, $n_x$, $n_y$, $n_z$. Here $n \le 100$ is the number of planetoids, and $n_x$, $n_y$, $n_z$ are the dimensions of the space, each at most 1000.

Each of the next $n$ lines has the form $m\ x\ y\ z\ v_x\ v_y\ v_z$ and gives the mass, location, and velocity of one planetoid at time $t = 0$, where $1 \le m \le 100$, $0 \le x < n_x$, $0 \le y < n_y$, $0 \le z < n_z$, and $-1000 \le v_x, v_y, v_z \le 1000$. No two planetoids start in the same location.

Print the number of planets $p$ that remain once no more collisions can occur. Then print $p$ lines, one per planet, in the form Pi: m x y z vx vy vz. Here Pi is the identifier with the index $i$ appended, so the first line starts with P0: and $i$ runs from $0$ to $p-1$. The rest of the line is the mass, location, and velocity of that planet.

Report locations and velocities at the time the last collision occurred. If no collision occurs, report them at time $t = 0$.

Order the planets from largest mass to smallest. Break ties by the lexicographic order of the location $(x, y, z)$, smallest $x$ first.