Robotic Surface Collision

Place‐Y Technology Corp. is preparing to launch a new space station consisting of a set of axis–aligned unit cubes. Some faces of the cubes are exposed (i.e. not adjacent to another cube) and serve as surfaces for cleaning robots. Each robot starts at time \(t=0\) at the center of an exposed face of some cube, and is given an initial tangent direction (one of the four directions along the edges of that face) along which it will roll over the station’s surface.

The movement is defined as follows. Suppose a robot is on face \(F\) of a cube with coordinate \(A=(x,y,z)\) and the face is indicated by its outward normal \(n\) (one of \( (1,0,0),\;(-1,0,0),\;(0,1,0),\;(0,-1,0),\;(0,0,1),\;(0,0,-1)\)). It also has a tangent direction \(d\) (which satisfies \(d\cdot n=0\)). At each time unit the robot moves as follows:

\(\textbf{Option 1:}\) If the cube at \(A+d\) does not exist in the station then the robot rolls on the same cube. Its new face becomes the one whose outward normal is exactly \(d\) and its new tangent direction becomes \(-n\).

\(\textbf{Option 2:}\) Otherwise (i.e. if the cube at \(A+d\) exists) the robot rolls onto the adjacent cube located at \(A+n\) (note: since the face on \(A\) is exposed, the cube at \(A+n\) does not exist in the station). In this case, its new face is that on the new cube whose outward normal is \(-d\) and its new tangent becomes \(n\).

A collision is defined to occur at time \(t\ge 1\) if either:

• Two or more robots end up on the interior of the same face (that is, they have identical cube coordinates and face identifiers), or
• Two robots swap their positions in one move (i.e. robot \(i\) moves from state \(X\) to \(Y\) while robot \(j\) moves from \(Y\) to \(X\)).

Given the positions and initial orientations for all robots, determine the time of the earliest collision. If no collision occurs within 10000 moves, output -1.

Note on Input: The space station is given as a collection of unit cubes. A face of a cube is exposed if there is no cube adjacent in the direction of that face's normal.

Movement Summary:

• If A + d is not in the set of cubes, then:
  New cube: A
  New face: the one with normal d (we denote this face by the letter corresponding to d)
  New tangent: -n
• Otherwise:
  New cube: A + n
  New face: the one with normal -d
  New tangent: n

The directions are encoded as follows:

• X+: \((1,0,0)\), X-: \((-1,0,0)\)
• Y+: \((0,1,0)\), Y-: \((0,-1,0)\)
• Z+: \((0,0,1)\), Z-: \((0,0,-1)\)

Each robot input line gives: x y z face tangent where (x,y,z) is the coordinate of the cube the robot is on, face is the exposed face indicator, and tangent is its initial tangent direction. It is guaranteed that the given face is exposed. The simulation begins at \(t=0\) and the first move occurs at \(t=1\).

inputFormat

The first line contains an integer n representing the number of cubes in the station. The next n lines each contain three integers x y z representing the coordinates of a cube.

The next line contains an integer r representing the number of robots. The following r lines each contain:

x y z face tangent

where face and tangent are strings chosen from the set { X+, X-, Y+, Y-, Z+, Z- } as described above. It is guaranteed that each robot starts on an exposed face.

outputFormat

Output a single integer: the time (in moves) at which the first collision occurs; if no collision occurs within 10000 moves, output -1.

sample

1
0 0 0
2
0 0 0 X+ Z+
0 0 0 Y- X+

-1