Determine the validity of a sequence of triominos plays.

Fig. 1: Triominos board layout. N1 is the location for the first play. Grey triangles are considered "upward" and white triangles are considered "downward". |

Fig. 2: Board after seven legal plays. Note that all pieces have adjacent edges and matching values on vertices. The turn of the play is written as 'a', 'b', 'c', ..., 'g' on the center of the piece. |

The game of triominos is played on a board of infinite extent which follows the pattern shown in figure 1. There are 76 triangular play pieces with a digit on each vertex. The digits are in the range 0 through 5 with possible repetition on a given game piece. The 76 pieces represent all possible vertex labels up to a rotation of the piece.

Some example pieces, reading the vertex values clockwise would be "000", "010" and "025". Note, however, that "250" and "502" are simply rotations of the single piece "025". This means that "250" and "502" cannot both be played in the same game: they are the same piece.

Play proceeds as follows: The first piece is drawn at random and placed on the board at location "N1." After this, play proceeds in turns. Each player places a piece so that:

(1) The piece has at least one edge adjacent to the edge of another piece already on the board.

(2) The piece matches all vertex values of adjacent vertices.

The point of this problem is, given a sequence of plays, you are to determine if they represent valid plays of the game in three respects:

(1) The placement of pieces follows the above rules.

(2) No piece is used more than once

(3) No space is occupied more than once.

The input file will contain one or more sequences of plays. Each sequence of plays will be separated by a single blank line. Each particular play is written in the form:

`PIECE` is the listing of the digits of the
vertices of the piece written in clockwise order. The first vertex
written is the top-most vertex for an "upward" triangle, and the
bottom-most vertex for a "downward" triangle.

For example, an input file representing the plays given in figure 2, followed by the same pieces with plays 'c' and 'd' transposed is:

column 1 1234567890 line 1:N1 403[EOL] 2:S1 230[EOL] 3:N1E1 044[EOL] 4:N1E2 430[EOL] 5:N1E3 341[EOL] 6:S1E2 203[EOL] 7:S1E1 022[EOL] 8:[EOL] 9:N1 403[EOL] 10:S1 230[EOL] 11:N1E2 430[EOL] 12:N1E1 044[EOL] 13:N1E3 341[EOL] 14:S1E2 203[EOL] 15:S1E1 022[EOL] :[EOF]

Other than the standard leader and trailer, the output file simply has the word "valid" or "invalid" on separate lines for each play sequence in the input file.

The correct output corresponding to the example input file would be:

column 111111111122222222223 123456789012345678901234567890 line 1:Program 6 by team 0[EOL] 2:valid[EOL] 3:invalid[EOL] 4:End of program 6 by team 0[EOL] :[EOF]