GentleBots

Rainforest Inc. is opening a large automated warehouse in the north of the UK, in a place called Walthamstow.

The worker robots inside move in three dimensions. In one time step a robot either stays where it is or walks one metre along one of the six axis directions, so a robot that travels from $(x_1, y_1, z_1)$ to $(x_2, y_2, z_2)$ with nothing in its way needs $|x_2 - x_1| + |y_2 - y_1| + |z_2 - z_1|$ steps.

The robots are impeccably polite. When two of them meet head on, they settle it without a word and one steps aside so the other can pass.

A robot always stands on integer coordinates. Two robots must never stand on the same coordinates, and two robots must never exchange positions in one time step. All moves of a time step happen at the same instant.

The test run of the warehouse has two robots installed. The controller plans them with one fixed procedure, written out in the output section, and your program has to reproduce that plan exactly.

The first line has six space separated integers $x_0\ y_0\ z_0\ x_1\ y_1\ z_1$. The first three are the start position $(x_0, y_0, z_0)$ of robot 1 and the last three are its end position $(x_1, y_1, z_1)$. The second line gives the six values of robot 2 in the same format. Every coordinate satisfies $-1000 \le x, y, z \le 1000$.

The two robots start at different positions and end at different positions. One robot may start and end at the same position.

Print the plan of the controller. Counting from 0, line $T$ has six space separated integers: the position of robot 1 at time $T$ followed by the position of robot 2 at time $T$. The first line holds the two start positions, the last line holds the two end positions, and between two consecutive lines a robot moves at most one metre.

The controller walks one robot at a time and leaves the other standing. Two definitions come first.

The straight route from $p$ to $q$ is the list of positions that begins at $p$, changes the x coordinate one step at a time until it matches the x coordinate of $q$, then changes the y coordinate the same way, then the z coordinate, and so ends at $q$.

The safe route from $p$ to $q$ around a blocked position $m$, where $m$ equals neither $p$ nor $q$, is fixed like this. If the straight route from $p$ to $q$ does not contain $m$, that route is the safe route. If it does contain $m$, check the six offsets $(1, 0, 0)$, $(-1, 0, 0)$, $(0, 1, 0)$, $(0, -1, 0)$, $(0, 0, 1)$, $(0, 0, -1)$ in this order and take the first offset $s$ for which the straight route from $p + s$ to $q + s$ does not contain $m$. Such an offset always exists. The safe route is then $p$, every position of the straight route from $p + s$ to $q + s$, and $q$, in that order.

Write $a_0$ and $a_1$ for the start and the end of robot 1, and $b_0$ and $b_1$ for those of robot 2. The controller applies the first rule whose condition holds.

1. If $a_1 \ne b_0$, robot 1 walks the safe route from $a_0$ to $a_1$ around $b_0$, then robot 2 walks the safe route from $b_0$ to $b_1$ around $a_1$.
2. Otherwise, if $b_1 \ne a_0$, robot 2 walks the safe route from $b_0$ to $b_1$ around $a_0$, then robot 1 walks the safe route from $a_0$ to $a_1$ around $b_1$.
3. Otherwise robot 2 first steps aside to $c = b_0 + s$, where $s$ is the first offset in the list above with $b_0 + s \ne a_0$. Then robot 1 walks the safe route from $a_0$ to $a_1$ around $c$, and finally robot 2 walks the safe route from $c$ to $b_1$ around $a_1$.

While a robot walks a route, print one line for every position of the route except the first one, and the robot that is not walking repeats its position on those lines. A route of a single position prints no line.