cho.shWooden Blocks
No attempts yetTime limit1sMemory limit128 MBProblem
This is a game where you join 8 kinds of wooden pieces in a single horizontal row to form a rectangle. Every piece has a left edge and a right edge, and each edge has one of the following five shapes.
- flat: a plain, flat edge with nothing on it
- square-out: a square-shaped bump that sticks out
- square-in: a square-shaped notch cut in
- round-out: a rounded bump that sticks out
- round-in: a rounded notch cut in
Two pieces interlock only when the right edge of the left piece and the left edge of the right piece form an out/in pair of the same shape. That is, square-out fits only square-in, and round-out fits only round-in.
The left and right edges of the 8 kinds of pieces are as follows.
| Piece | Left edge | Right edge |
|---|---|---|
| 1 | flat | square-in |
| 2 | square-in | flat |
| 3 | square-in | square-in |
| 4 | square-out | square-out |
| 5 | square-out | round-in |
| 6 | round-in | square-out |
| 7 | round-in | round-in |
| 8 | round-out | round-out |
A correct arrangement must satisfy all of the following conditions.
- The leftmost piece is piece 1, and the rightmost piece is piece 2.
- Every pair of adjacent pieces must interlock.
- In the whole arrangement, the leftmost edge (the left edge of piece 1) and the rightmost edge (the right edge of piece 2) are flat and interlock with nothing.
- When the above conditions hold, every piece 1 always has a matching piece 2, and every piece 5 always has a matching piece 6.
Sehui is building this game as an app. Write a program that decides whether the pieces a user has arranged form a correct arrangement satisfying the conditions above.
Input
The input consists of several test cases, one per line. Each line lists the piece numbers (from 1 to 8) in left-to-right order with no spaces between them. Each test case has at least 1 piece, and the number of pieces does not exceed 10,000.
The last line of the input contains a single 0, which marks the end of the input.
Output
For each test case, print the test case number (starting from 1), followed by VALID if the given arrangement is correct or NOT if it is not. The output format is number. result, with a period and one space after the number.