Adjacent Edges

Triangle adjacency is a problem that arises in computer graphics. Modelling packages often output a 3D model as a list of triangles. For example, the tetrahedron in the sketch below has 4 triangular faces. Each triangle is described by listing the positions of its three corners, given in clockwise order as seen by an observer standing just outside the solid. The exact file format is described in the Input section below.

This representation is fine for many purposes, but some graphics algorithms need to know which triangles are adjacent — that is, which triangles share an edge. Your task is to work this out for the given models. Computing the adjacent triangles also lets us verify that every edge of every triangle is matched by exactly one edge of another triangle, which is a way to check that a model forms a fully enclosed shell with no gaps or holes.

Any face in a model can have up to three adjacent triangles, sharing one edge with each. In a well-formed model every edge occurs in exactly two triangles, and the two endpoints of a shared edge appear in the opposite order as you travel clockwise around each of the two triangles.

Consider a triangle whose corners are $V_0$, $V_1$, $V_2$, in the order given in the input. Its three edges are $V_0V_1$, $V_1V_2$ and $V_2V_0$. Let $V_3$ be the remaining corner of the triangle that shares edge $V_0V_1$, let $V_4$ be the remaining corner of the triangle that shares edge $V_1V_2$, and let $V_5$ be the remaining corner of the triangle that shares edge $V_2V_0$. For each triangle you output $V_0, V_1, V_2, V_3, V_4, V_5$. If a triangle has no neighbour along one of these edges, output an uppercase X in place of that vertex number.

The input contains several 3D models. For each model, the first line is a single integer $T$ ($1 \le T \le 400000$), the number of triangles in the model. Then $3T$ lines follow — three lines per triangle — each giving the $x$, $y$, $z$ coordinates of one vertex, separated by a comma and a space. The three vertices of every triangle are listed in clockwise order.

The coordinates may be floating-point values, including some written in exponent form, so do not assume they are integers. It is guaranteed that different occurrences of the same vertex are written as identical strings, and that any two distinct vertices differ when represented as single-precision (32-bit) floats. All coordinates lie in the range $-2$ to $2$ inclusive.

The input ends with a line containing a single 0 in place of $T$.

Within each model, number the distinct vertices in the order they first appear in that model's input, starting from $0$ (then $1$, $2$, $3$, and so on). The output uses these vertex numbers rather than the coordinate values, and the numbering restarts from $0$ for every model.

Print the models in the order they are read. Separate two consecutive models with a single blank line; do not print a blank line before the first model or after the last one. For each model, print one line per triangle ($T$ lines in total), in the same order the triangles were read.

Each triangle line has the form

i: V0 V1 V2 V3 V4 V5

where $i$ is the triangle's number ($0, 1, 2, \dots$) followed by a colon and a space. $V_0, V_1, V_2$ are the triangle's own vertex numbers in input order, and $V_3, V_4, V_5$ are the remaining vertices of the triangles adjacent along edges $V_0V_1$, $V_1V_2$ and $V_2V_0$ respectively. A missing neighbour is printed as an uppercase X. All values on a line are separated by single spaces.