Fold-up patterns for solids like cubes or octahedrons can be found in many books, but without actually folding them it is hard to tell whether they will really work. We will restrict our attention to a special class of patterns. Given a fold-up pattern built from unit squares in the plane, together with a description along what edges it should be folded in what direction, decide whether it will result in a closed surface of a solid in three dimensions. If it does, find the volume of the solid. More precisely, the pattern consists of a connected set of unit squares in the plane. For any edge between connected sides you are told whether to fold forward, back, or not at all along that edge, always at right angles. If an edge of two adjacent squares in the pattern is not mentioned in the input, you may assume that the squares are not connected and can be ripped apart when folding. However, connected edges must always be folded according to the description. For our purposes a closed surface is one so that every square in the pattern separates the inside from the outside. When folded, the squares of the pattern lie on a rectangular, 3-dimensional grid, and each separates a cell (cubes of side length one unit) on the inside from one on the outside. For every cell it must be clear whether it is inside or outside. The following sketch illustrates this rule in two dimensions (the “insides” are shaded). Note that according to our definition the second pattern in the sketch at the top of the page is a closed surface, although it rather looks like two separate cubes attached along an edge.
2/2 Two different squares must not occupy exactly the same position in space, though they may (and should for a closed surface) touch at edges and vertices. Make sure that the pattern does not interpen- etrate itself through connected edges. Apart from that, do not worry about the process of folding, e.g. what edges are folded first or whether part of the structure is in the way for the rest. Input The first line of the input specifies the number of scenarios. For each scenario, the first line provides the number 1 ≤ n ≤ 1000 of squares in the pattern and the number 0 ≤ e ≤ 4000 of edges. Squares are labelled by the integers 0 to (n − 1). The following e lines describe one edge each using the following four numbers: • The two numbers s1 and s2 (with 0 ≤ s1 < s2 < n) of the squares that are joined by the edge. • The position p of the square s2 with respect to the square s1 in the pattern. Here p = 0, 1, 2, or 3 mean above, to the left, below, or to the right, respectively (see sketch). • The number f = 0,1,2 tells you to fold along the edge either not at all, or forward, or back, respectively. It is guaranteed that the folded pattern fits in a cube with a side length of 40. You can also assume that the pattern is connected and can be drawn in the plane without overlapping. Output For each scenario print a line containing either “Not a closed surface” if the pattern does not form a closed surface or “Closed surface, volume=” and the volume as an integer if it does. Sample Input 2 65 0221 1231 2331 2421 4520 12 11 0321 1521 2331 3431 4532 5631 6731 7831 8932 3 10 2 1 5 11 2 1 Sample Output Not a closed surface Closed surface, volume=2