Fold-up Patterns

Fold-up patterns for solids such as cubes or octahedrons appear in many geometry books, but without actually folding one it is hard to tell whether the construction really works. In this problem we study a special class of such patterns.

You are given a fold-up pattern made of unit squares in the plane, together with a description of which edges to fold and in which direction. Decide whether folding it produces the closed surface of a three-dimensional solid, and if it does, find the volume of that solid.

More precisely, the pattern is a connected set of unit squares in the plane. For every edge that joins two connected squares you are told whether to fold forward, fold backward (always by a right angle), or not fold at all along that edge. If an edge between two adjacent squares is not listed in the input, the squares are not connected there and may be pulled apart while folding. Connected edges must always be folded exactly as described.

For our purposes a closed surface is one in which every square separates the inside from the outside. After folding, the squares lie on a three-dimensional unit grid, and each square separates one cell (a cube of side length one) on the inside from one cell on the outside. For every cell it must be clear whether it is inside or outside.

Note that even a pattern whose interior is not connected can still be a closed surface.

Two distinct squares may not occupy exactly the same position in space, although they may (and, for a closed surface, will) touch along edges and at vertices. Make sure the pattern does not pass through itself along connected edges. Apart from that, do not worry about the physical folding process, for example which edges are folded first or whether part of the structure is in the way of the rest.

The input consists of several scenarios.

Each scenario begins with a line containing two integers $n$ and $e$: the number of squares $n$ ($1 \le n \le 200$) and the number of edges $e$ ($0 \le e \le 300$). Squares are labelled $0$ to $n-1$. Each of the next $e$ lines describes one edge with four integers $s_1\ s_2\ p\ f$:

• $s_1$ and $s_2$ (with $0 \le s_1 < s_2 < n$): the two squares joined by the edge.
• $p$: the position of square $s_2$ relative to square $s_1$. $p = 0, 1, 2, 3$ means $s_2$ is above, to the left, below, or to the right of $s_1$, respectively.
• $f$: how to fold along the edge. $f = 0, 1, 2$ means do not fold, fold forward, or fold backward, respectively.

You may assume the pattern is connected and can be drawn in the plane without overlap.

The input ends with a line containing two zeros in place of $n$ and $e$. Do not process that line.

For each scenario print Test case #k:, where k is the scenario number (starting from 1). On the same line print either not a closed surface if the pattern does not form a closed surface, or closed surface, volume=V, where V is the volume as an integer, if it does.