src/edu/berkeley/qfat/voxel/MarchingCubes.java

   1 package edu.berkeley.qfat.voxel;
   2 import edu.berkeley.qfat.*;
   3 import edu.berkeley.qfat.geom.*;
   4
   5 /////////////////////////////////////////////////////////////////////////////////////
   6 // Derived from:                                                                   //
   7 // http://local.wasp.uwa.edu.au/~pbourke/geometry/polygonise/marchingsource.cpp    //
   8 // (which is public domain)                                                        //
   9 /////////////////////////////////////////////////////////////////////////////////////
  10 //
  11 // Marching Cubes Example Program
  12 // by Cory Bloyd (corysama@yahoo.com)
  13 //
  14 // A simple, portable and complete implementation of the Marching Cubes
  15 // and Marching Tetrahedrons algorithms in a single source file.
  16 // There are many ways that this code could be made faster, but the
  17 // intent is for the code to be easy to understand.
  18 //
  19 // For a description of the algorithm go to
  20 // http://astronomy.swin.edu.au/pbourke/modelling/polygonise/
  21 //
  22 // This code is public domain.
  23 //
  24 //////////////////////////////////////////////////////////////////////////////////////
  25
  26 public class MarchingCubes {
  27
  28     private static class GLvector {
  29         public double fX;
  30         public double fY;
  31         public double fZ;
  32         public String toString() {
  33             return "("+fX+","+fY+","+fZ+")";
  34         }
  35     };
  36
  37     /** march iterates over the entire dataset, calling vMarchCube on each cube */
  38     public static void march(SampledField sampledField, double threshold, int iDataSetSize, double fStepSize, Mesh mesh) {
  39         int iX, iY, iZ;
  40         int initialTriangles = mesh.numTriangles();
  41         for(iX = 0; iX < iDataSetSize; iX++) {
  42             System.out.print("\r");
  43             for(int i=0; i<78; i++) System.out.print(' ');
  44             System.out.print("\r");
  45             System.out.print(Math.ceil((iX/((double)iDataSetSize))*100) + "% marched, " +
  46                              (mesh.numTriangles()-initialTriangles) + " triangles");
  47             for(iY = 0; iY < iDataSetSize; iY++)
  48                 for(iZ = 0; iZ < iDataSetSize; iZ++)
  49                     march(sampledField, mesh, threshold, iX*fStepSize, iY*fStepSize, iZ*fStepSize, fStepSize);
  50         }
  51         System.out.print("\r");
  52         for(int i=0; i<78; i++) System.out.print(' ');
  53         System.out.print("\r");
  54         System.out.println("done marching.");
  55     }
  56
  57     /** performs the Marching Cubes algorithm on a single cube */
  58     static void march(SampledField sampledField, Mesh mesh, double threshold, double fX, double fY, double fZ, double fScale) {
  59         int iCorner, iVertex, iVertexTest, iEdge, iTriangle, iFlagIndex, iEdgeFlags;
  60         double fOffset;
  61         GLvector sColor;
  62         double afCubeValue[] = new double[8];
  63         GLvector asEdgeVertex[] = new GLvector[12];
  64         GLvector asEdgeNorm[] = new GLvector[12];
  65
  66         for(int i=0; i<asEdgeVertex.length; i++) asEdgeVertex[i] = new GLvector();
  67         for(int i=0; i<asEdgeNorm.length; i++) asEdgeNorm[i] = new GLvector();
  68
  69         // Make a local copy of the values at the cube's corners
  70         for(iVertex = 0; iVertex < 8; iVertex++)
  71             afCubeValue[iVertex] = sampledField.getSample(new Point(fX + a2fVertexOffset[iVertex][0]*fScale,
  72                                                                     fY + a2fVertexOffset[iVertex][1]*fScale,
  73                                                                     fZ + a2fVertexOffset[iVertex][2]*fScale));
  74
  75         // Find which vertices are inside of the surface and which are outside
  76         iFlagIndex = 0;
  77         for(iVertexTest = 0; iVertexTest < 8; iVertexTest++)
  78             if (afCubeValue[iVertexTest] >= threshold)
  79                 iFlagIndex |= 1<<iVertexTest;
  80
  81         // Find which edges are intersected by the surface
  82         iEdgeFlags = aiCubeEdgeFlags[iFlagIndex];
  83
  84         // If the cube is entirely inside or outside of the surface, then there will be no intersections
  85         if (iEdgeFlags == 0) return;
  86
  87         // Find the point of intersection of the surface with each edge
  88         // Then find the normal to the surface at those points
  89         for(iEdge = 0; iEdge < 12; iEdge++) {
  90             // If there is an intersection on this edge
  91             if ((iEdgeFlags & (1<<iEdge))==0) continue;
  92             fOffset = fGetOffset(afCubeValue[ a2iEdgeConnection[iEdge][0] ],
  93                                  afCubeValue[ a2iEdgeConnection[iEdge][1] ],
  94                                  threshold,
  95                                  fScale * 0.1);
  96
  97             asEdgeVertex[iEdge].fX = fX + (a2fVertexOffset[ a2iEdgeConnection[iEdge][0] ][0]  +  fOffset * a2fEdgeDirection[iEdge][0]) * fScale;
  98             asEdgeVertex[iEdge].fY = fY + (a2fVertexOffset[ a2iEdgeConnection[iEdge][0] ][1]  +  fOffset * a2fEdgeDirection[iEdge][1]) * fScale;
  99             asEdgeVertex[iEdge].fZ = fZ + (a2fVertexOffset[ a2iEdgeConnection[iEdge][0] ][2]  +  fOffset * a2fEdgeDirection[iEdge][2]) * fScale;
 100
 101             vGetNormal(sampledField, asEdgeNorm[iEdge], asEdgeVertex[iEdge].fX, asEdgeVertex[iEdge].fY, asEdgeVertex[iEdge].fZ);
 102         }
 103
 104         // Draw the triangles that were found.  There can be up to five per cube
 105         for(iTriangle = 0; iTriangle < 5; iTriangle++) {
 106             if(a2iTriangleConnectionTable[iFlagIndex][3*iTriangle] < 0)
 107                 break;
 108
 109             Point[] points = new Point[3];
 110             Vec norm = new Vec(0,0,0);
 111             for(iCorner = 0; iCorner < 3; iCorner++) {
 112                 iVertex = a2iTriangleConnectionTable[iFlagIndex][3*iTriangle+iCorner];
 113                 points[iCorner] = new Point(asEdgeVertex[iVertex].fX, asEdgeVertex[iVertex].fY, asEdgeVertex[iVertex].fZ);
 114
 115                 // questionable, but we do it anyways
 116                 norm = norm.plus(new Vec(asEdgeNorm[iVertex].fX,   asEdgeNorm[iVertex].fY,   asEdgeNorm[iVertex].fZ));
 117             }
 118
 119             // Eliminate triangles with "length-zero" sides.
 120             // Unfortunately this puts holes in the mesh.
 121             if (points[0].equals(points[1]) ||
 122                 points[0].equals(points[2]) ||
 123                 points[1].equals(points[2]))
 124                 continue;
 125
 126             mesh.newT(points[0], points[1], points[2], norm.norm().times(-1));
 127         }
 128     }
 129
 130     /**
 131      *  vGetNormal() finds the gradient of the scalar field at a point
 132      *  This gradient can be used as a very accurate vertx normal for
 133      *  lighting calculations
 134      */
 135     static void vGetNormal(SampledField sampledField, GLvector rfNormal, double fX, double fY, double fZ) {
 136         rfNormal.fX =
 137             sampledField.getSample(new Point(fX-0.01, fY, fZ)) -
 138             sampledField.getSample(new Point(fX+0.01, fY, fZ));
 139         rfNormal.fY =
 140             sampledField.getSample(new Point(fX, fY-0.01, fZ)) -
 141             sampledField.getSample(new Point(fX, fY+0.01, fZ));
 142         rfNormal.fZ =
 143             sampledField.getSample(new Point(fX, fY, fZ-0.01)) -
 144             sampledField.getSample(new Point(fX, fY, fZ+0.01));
 145         vNormalizeVector(rfNormal, rfNormal);
 146     }
 147
 148     static void vNormalizeVector(GLvector rfVectorResult, GLvector rfVectorSource) {
 149         double fOldLength;
 150         double fScale;
 151
 152         fOldLength = Math.sqrt( (rfVectorSource.fX * rfVectorSource.fX) +
 153                                 (rfVectorSource.fY * rfVectorSource.fY) +
 154                                 (rfVectorSource.fZ * rfVectorSource.fZ) );
 155
 156         if(fOldLength == 0.0) {
 157             rfVectorResult.fX = rfVectorSource.fX;
 158             rfVectorResult.fY = rfVectorSource.fY;
 159             rfVectorResult.fZ = rfVectorSource.fZ;
 160         } else {
 161             fScale = 1.0/fOldLength;
 162             rfVectorResult.fX = rfVectorSource.fX*fScale;
 163             rfVectorResult.fY = rfVectorSource.fY*fScale;
 164             rfVectorResult.fZ = rfVectorSource.fZ*fScale;
 165         }
 166     }
 167
 168     // fGetOffset finds the approximate point of intersection of the surface
 169     // between two points with the values fValue1 and fValue2
 170     static double fGetOffset(double fValue1, double fValue2, double fValueDesired, double EPSILON) {
 171         double fDelta = fValue2 - fValue1;
 172         if(fDelta == 0.0) return 0.5;
 173
 174         // the following two lines are a hack; they "snap" the
 175         // estimate to one grid point or the other if the distance is
 176         // less than some EPSILON.  This ensures that the resulting
 177         // mesh is watertight and meets the requirements of Mesh.java
 178         if (Math.abs(fValueDesired-fValue1) < EPSILON) return 0;
 179         if (Math.abs(fValueDesired-fValue2) < EPSILON) return 1;
 180
 181         return (fValueDesired - fValue1)/fDelta;
 182     }
 183
 184     ////////////////////////////////////////////////////////////////////////////////////////
 185     // Tables //////////////////////////////////////////////////////////////////////////////
 186
 187     // These tables are used so that everything can be done in little
 188     // loops that you can look at all at once rather than in pages and
 189     // pages of unrolled code.
 190
 191     // a2fVertexOffset lists the positions, relative to vertex0, of
 192     // each of the 8 vertices of a cube
 193     static final double a2fVertexOffset[][] = {
 194         {0.0, 0.0, 0.0},{1.0, 0.0, 0.0},{1.0, 1.0, 0.0},{0.0, 1.0, 0.0},
 195         {0.0, 0.0, 1.0},{1.0, 0.0, 1.0},{1.0, 1.0, 1.0},{0.0, 1.0, 1.0}
 196     };
 197
 198     //a2iEdgeConnection lists the index of the endpoint vertices for each of the 12 edges of the cube
 199     static final int a2iEdgeConnection[][] = {
 200         {0,1}, {1,2}, {2,3}, {3,0},
 201         {4,5}, {5,6}, {6,7}, {7,4},
 202         {0,4}, {1,5}, {2,6}, {3,7}
 203     };
 204
 205     //a2fEdgeDirection lists the direction vector (vertex1-vertex0) for each edge in the cube
 206     static final double a2fEdgeDirection[][] = {
 207         {1.0, 0.0, 0.0},{0.0, 1.0, 0.0},{-1.0, 0.0, 0.0},{0.0, -1.0, 0.0},
 208         {1.0, 0.0, 0.0},{0.0, 1.0, 0.0},{-1.0, 0.0, 0.0},{0.0, -1.0, 0.0},
 209         {0.0, 0.0, 1.0},{0.0, 0.0, 1.0},{ 0.0, 0.0, 1.0},{0.0,  0.0, 1.0}
 210     };
 211
 212     // a2iTetrahedronEdgeConnection lists the index of the endpoint
 213     // vertices for each of the 6 edges of the tetrahedron
 214     static final int a2iTetrahedronEdgeConnection[][] = {
 215         {0,1},  {1,2},  {2,0},  {0,3},  {1,3},  {2,3}
 216     };
 217
 218     // a2iTetrahedronEdgeConnection lists the index of verticies from a cube
 219     // that made up each of the six tetrahedrons within the cube
 220     static final int a2iTetrahedronsInACube[][] = {
 221         {0,5,1,6},
 222         {0,1,2,6},
 223         {0,2,3,6},
 224         {0,3,7,6},
 225         {0,7,4,6},
 226         {0,4,5,6},
 227     };
 228
 229
 230     // For any edge, if one vertex is inside of the surface and the
 231     //  other is outside of the surface then the edge intersects the
 232     //  surface For each of the 4 vertices of the tetrahedron can be
 233     //  two possible states : either inside or outside of the surface
 234     //  For any tetrahedron the are 2^4=16 possible sets of vertex
 235     //  states This table lists the edges intersected by the surface
 236     //  for all 16 possible vertex states There are 6 edges.  For each
 237     //  entry in the table, if edge #n is intersected, then bit #n is
 238     //  set to 1
 239
 240     static int aiTetrahedronEdgeFlags[] = {
 241         0x00, 0x0d, 0x13, 0x1e, 0x26, 0x2b, 0x35, 0x38,
 242         0x38, 0x35, 0x2b, 0x26, 0x1e, 0x13, 0x0d, 0x00,
 243     };
 244
 245
 246     // For each of the possible vertex states listed in
 247     // aiTetrahedronEdgeFlags there is a specific triangulation of the
 248     // edge intersection points.  a2iTetrahedronTriangles lists all of
 249     // them in the form of 0-2 edge triples with the list terminated
 250     // by the invalid value -1.
 251     //
 252     // I generated this table by hand
 253
 254     static int a2iTetrahedronTriangles[][] = {
 255         {-1, -1, -1, -1, -1, -1, -1},
 256         { 0,  3,  2, -1, -1, -1, -1},
 257         { 0,  1,  4, -1, -1, -1, -1},
 258         { 1,  4,  2,  2,  4,  3, -1},
 259
 260         { 1,  2,  5, -1, -1, -1, -1},
 261         { 0,  3,  5,  0,  5,  1, -1},
 262         { 0,  2,  5,  0,  5,  4, -1},
 263         { 5,  4,  3, -1, -1, -1, -1},
 264
 265         { 3,  4,  5, -1, -1, -1, -1},
 266         { 4,  5,  0,  5,  2,  0, -1},
 267         { 1,  5,  0,  5,  3,  0, -1},
 268         { 5,  2,  1, -1, -1, -1, -1},
 269
 270         { 3,  4,  2,  2,  4,  1, -1},
 271         { 4,  1,  0, -1, -1, -1, -1},
 272         { 2,  3,  0, -1, -1, -1, -1},
 273         {-1, -1, -1, -1, -1, -1, -1},
 274     };
 275
 276     // For any edge, if one vertex is inside of the surface and the
 277     //  other is outside of the surface then the edge intersects the
 278     //  surface For each of the 8 vertices of the cube can be two
 279     //  possible states : either inside or outside of the surface For
 280     //  any cube the are 2^8=256 possible sets of vertex states This
 281     //  table lists the edges intersected by the surface for all 256
 282     //  possible vertex states There are 12 edges.  For each entry in
 283     //  the table, if edge #n is intersected, then bit #n is set to 1
 284
 285     static final int aiCubeEdgeFlags[] = {
 286         0x000, 0x109, 0x203, 0x30a, 0x406, 0x50f, 0x605, 0x70c,
 287         0x80c, 0x905, 0xa0f, 0xb06, 0xc0a, 0xd03, 0xe09, 0xf00,
 288         0x190, 0x099, 0x393, 0x29a, 0x596, 0x49f, 0x795, 0x69c,
 289         0x99c, 0x895, 0xb9f, 0xa96, 0xd9a, 0xc93, 0xf99, 0xe90,
 290         0x230, 0x339, 0x033, 0x13a, 0x636, 0x73f, 0x435, 0x53c,
 291         0xa3c, 0xb35, 0x83f, 0x936, 0xe3a, 0xf33, 0xc39, 0xd30,
 292         0x3a0, 0x2a9, 0x1a3, 0x0aa, 0x7a6, 0x6af, 0x5a5, 0x4ac,
 293         0xbac, 0xaa5, 0x9af, 0x8a6, 0xfaa, 0xea3, 0xda9, 0xca0,
 294         0x460, 0x569, 0x663, 0x76a, 0x066, 0x16f, 0x265, 0x36c,
 295         0xc6c, 0xd65, 0xe6f, 0xf66, 0x86a, 0x963, 0xa69, 0xb60,
 296         0x5f0, 0x4f9, 0x7f3, 0x6fa, 0x1f6, 0x0ff, 0x3f5, 0x2fc,
 297         0xdfc, 0xcf5, 0xfff, 0xef6, 0x9fa, 0x8f3, 0xbf9, 0xaf0,
 298         0x650, 0x759, 0x453, 0x55a, 0x256, 0x35f, 0x055, 0x15c,
 299         0xe5c, 0xf55, 0xc5f, 0xd56, 0xa5a, 0xb53, 0x859, 0x950,
 300         0x7c0, 0x6c9, 0x5c3, 0x4ca, 0x3c6, 0x2cf, 0x1c5, 0x0cc,
 301         0xfcc, 0xec5, 0xdcf, 0xcc6, 0xbca, 0xac3, 0x9c9, 0x8c0,
 302         0x8c0, 0x9c9, 0xac3, 0xbca, 0xcc6, 0xdcf, 0xec5, 0xfcc,
 303         0x0cc, 0x1c5, 0x2cf, 0x3c6, 0x4ca, 0x5c3, 0x6c9, 0x7c0,
 304         0x950, 0x859, 0xb53, 0xa5a, 0xd56, 0xc5f, 0xf55, 0xe5c,
 305         0x15c, 0x055, 0x35f, 0x256, 0x55a, 0x453, 0x759, 0x650,
 306         0xaf0, 0xbf9, 0x8f3, 0x9fa, 0xef6, 0xfff, 0xcf5, 0xdfc,
 307         0x2fc, 0x3f5, 0x0ff, 0x1f6, 0x6fa, 0x7f3, 0x4f9, 0x5f0,
 308         0xb60, 0xa69, 0x963, 0x86a, 0xf66, 0xe6f, 0xd65, 0xc6c,
 309         0x36c, 0x265, 0x16f, 0x066, 0x76a, 0x663, 0x569, 0x460,
 310         0xca0, 0xda9, 0xea3, 0xfaa, 0x8a6, 0x9af, 0xaa5, 0xbac,
 311         0x4ac, 0x5a5, 0x6af, 0x7a6, 0x0aa, 0x1a3, 0x2a9, 0x3a0,
 312         0xd30, 0xc39, 0xf33, 0xe3a, 0x936, 0x83f, 0xb35, 0xa3c,
 313         0x53c, 0x435, 0x73f, 0x636, 0x13a, 0x033, 0x339, 0x230,
 314         0xe90, 0xf99, 0xc93, 0xd9a, 0xa96, 0xb9f, 0x895, 0x99c,
 315         0x69c, 0x795, 0x49f, 0x596, 0x29a, 0x393, 0x099, 0x190,
 316         0xf00, 0xe09, 0xd03, 0xc0a, 0xb06, 0xa0f, 0x905, 0x80c,
 317         0x70c, 0x605, 0x50f, 0x406, 0x30a, 0x203, 0x109, 0x000
 318     };
 319
 320     //  For each of the possible vertex states listed in
 321     //  aiCubeEdgeFlags there is a specific triangulation of the edge
 322     //  intersection points.  a2iTriangleConnectionTable lists all of
 323     //  them in the form of 0-5 edge triples with the list terminated
 324     //  by the invalid value -1.  For example:
 325     //  a2iTriangleConnectionTable[3] list the 2 triangles formed when
 326     //  corner[0] and corner[1] are inside of the surface, but the
 327     //  rest of the cube is not.
 328     //
 329     //  I found this table in an example program someone wrote long
 330     //  ago.  It was probably generated by hand
 331
 332     static final int a2iTriangleConnectionTable[][] = {
 333         {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 334         {0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 335         {0, 1, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 336         {1, 8, 3, 9, 8, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 337         {1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 338         {0, 8, 3, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 339         {9, 2, 10, 0, 2, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 340         {2, 8, 3, 2, 10, 8, 10, 9, 8, -1, -1, -1, -1, -1, -1, -1},
 341         {3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 342         {0, 11, 2, 8, 11, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 343         {1, 9, 0, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 344         {1, 11, 2, 1, 9, 11, 9, 8, 11, -1, -1, -1, -1, -1, -1, -1},
 345         {3, 10, 1, 11, 10, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 346         {0, 10, 1, 0, 8, 10, 8, 11, 10, -1, -1, -1, -1, -1, -1, -1},
 347         {3, 9, 0, 3, 11, 9, 11, 10, 9, -1, -1, -1, -1, -1, -1, -1},
 348         {9, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 349         {4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 350         {4, 3, 0, 7, 3, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 351         {0, 1, 9, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 352         {4, 1, 9, 4, 7, 1, 7, 3, 1, -1, -1, -1, -1, -1, -1, -1},
 353         {1, 2, 10, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 354         {3, 4, 7, 3, 0, 4, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1},
 355         {9, 2, 10, 9, 0, 2, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1},
 356         {2, 10, 9, 2, 9, 7, 2, 7, 3, 7, 9, 4, -1, -1, -1, -1},
 357         {8, 4, 7, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 358         {11, 4, 7, 11, 2, 4, 2, 0, 4, -1, -1, -1, -1, -1, -1, -1},
 359         {9, 0, 1, 8, 4, 7, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1},
 360         {4, 7, 11, 9, 4, 11, 9, 11, 2, 9, 2, 1, -1, -1, -1, -1},
 361         {3, 10, 1, 3, 11, 10, 7, 8, 4, -1, -1, -1, -1, -1, -1, -1},
 362         {1, 11, 10, 1, 4, 11, 1, 0, 4, 7, 11, 4, -1, -1, -1, -1},
 363         {4, 7, 8, 9, 0, 11, 9, 11, 10, 11, 0, 3, -1, -1, -1, -1},
 364         {4, 7, 11, 4, 11, 9, 9, 11, 10, -1, -1, -1, -1, -1, -1, -1},
 365         {9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 366         {9, 5, 4, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 367         {0, 5, 4, 1, 5, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 368         {8, 5, 4, 8, 3, 5, 3, 1, 5, -1, -1, -1, -1, -1, -1, -1},
 369         {1, 2, 10, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 370         {3, 0, 8, 1, 2, 10, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1},
 371         {5, 2, 10, 5, 4, 2, 4, 0, 2, -1, -1, -1, -1, -1, -1, -1},
 372         {2, 10, 5, 3, 2, 5, 3, 5, 4, 3, 4, 8, -1, -1, -1, -1},
 373         {9, 5, 4, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 374         {0, 11, 2, 0, 8, 11, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1},
 375         {0, 5, 4, 0, 1, 5, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1},
 376         {2, 1, 5, 2, 5, 8, 2, 8, 11, 4, 8, 5, -1, -1, -1, -1},
 377         {10, 3, 11, 10, 1, 3, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1},
 378         {4, 9, 5, 0, 8, 1, 8, 10, 1, 8, 11, 10, -1, -1, -1, -1},
 379         {5, 4, 0, 5, 0, 11, 5, 11, 10, 11, 0, 3, -1, -1, -1, -1},
 380         {5, 4, 8, 5, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1},
 381         {9, 7, 8, 5, 7, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 382         {9, 3, 0, 9, 5, 3, 5, 7, 3, -1, -1, -1, -1, -1, -1, -1},
 383         {0, 7, 8, 0, 1, 7, 1, 5, 7, -1, -1, -1, -1, -1, -1, -1},
 384         {1, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 385         {9, 7, 8, 9, 5, 7, 10, 1, 2, -1, -1, -1, -1, -1, -1, -1},
 386         {10, 1, 2, 9, 5, 0, 5, 3, 0, 5, 7, 3, -1, -1, -1, -1},
 387         {8, 0, 2, 8, 2, 5, 8, 5, 7, 10, 5, 2, -1, -1, -1, -1},
 388         {2, 10, 5, 2, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1},
 389         {7, 9, 5, 7, 8, 9, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1},
 390         {9, 5, 7, 9, 7, 2, 9, 2, 0, 2, 7, 11, -1, -1, -1, -1},
 391         {2, 3, 11, 0, 1, 8, 1, 7, 8, 1, 5, 7, -1, -1, -1, -1},
 392         {11, 2, 1, 11, 1, 7, 7, 1, 5, -1, -1, -1, -1, -1, -1, -1},
 393         {9, 5, 8, 8, 5, 7, 10, 1, 3, 10, 3, 11, -1, -1, -1, -1},
 394         {5, 7, 0, 5, 0, 9, 7, 11, 0, 1, 0, 10, 11, 10, 0, -1},
 395         {11, 10, 0, 11, 0, 3, 10, 5, 0, 8, 0, 7, 5, 7, 0, -1},
 396         {11, 10, 5, 7, 11, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 397         {10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 398         {0, 8, 3, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 399         {9, 0, 1, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 400         {1, 8, 3, 1, 9, 8, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1},
 401         {1, 6, 5, 2, 6, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 402         {1, 6, 5, 1, 2, 6, 3, 0, 8, -1, -1, -1, -1, -1, -1, -1},
 403         {9, 6, 5, 9, 0, 6, 0, 2, 6, -1, -1, -1, -1, -1, -1, -1},
 404         {5, 9, 8, 5, 8, 2, 5, 2, 6, 3, 2, 8, -1, -1, -1, -1},
 405         {2, 3, 11, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 406         {11, 0, 8, 11, 2, 0, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1},
 407         {0, 1, 9, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1},
 408         {5, 10, 6, 1, 9, 2, 9, 11, 2, 9, 8, 11, -1, -1, -1, -1},
 409         {6, 3, 11, 6, 5, 3, 5, 1, 3, -1, -1, -1, -1, -1, -1, -1},
 410         {0, 8, 11, 0, 11, 5, 0, 5, 1, 5, 11, 6, -1, -1, -1, -1},
 411         {3, 11, 6, 0, 3, 6, 0, 6, 5, 0, 5, 9, -1, -1, -1, -1},
 412         {6, 5, 9, 6, 9, 11, 11, 9, 8, -1, -1, -1, -1, -1, -1, -1},
 413         {5, 10, 6, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 414         {4, 3, 0, 4, 7, 3, 6, 5, 10, -1, -1, -1, -1, -1, -1, -1},
 415         {1, 9, 0, 5, 10, 6, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1},
 416         {10, 6, 5, 1, 9, 7, 1, 7, 3, 7, 9, 4, -1, -1, -1, -1},
 417         {6, 1, 2, 6, 5, 1, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1},
 418         {1, 2, 5, 5, 2, 6, 3, 0, 4, 3, 4, 7, -1, -1, -1, -1},
 419         {8, 4, 7, 9, 0, 5, 0, 6, 5, 0, 2, 6, -1, -1, -1, -1},
 420         {7, 3, 9, 7, 9, 4, 3, 2, 9, 5, 9, 6, 2, 6, 9, -1},
 421         {3, 11, 2, 7, 8, 4, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1},
 422         {5, 10, 6, 4, 7, 2, 4, 2, 0, 2, 7, 11, -1, -1, -1, -1},
 423         {0, 1, 9, 4, 7, 8, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1},
 424         {9, 2, 1, 9, 11, 2, 9, 4, 11, 7, 11, 4, 5, 10, 6, -1},
 425         {8, 4, 7, 3, 11, 5, 3, 5, 1, 5, 11, 6, -1, -1, -1, -1},
 426         {5, 1, 11, 5, 11, 6, 1, 0, 11, 7, 11, 4, 0, 4, 11, -1},
 427         {0, 5, 9, 0, 6, 5, 0, 3, 6, 11, 6, 3, 8, 4, 7, -1},
 428         {6, 5, 9, 6, 9, 11, 4, 7, 9, 7, 11, 9, -1, -1, -1, -1},
 429         {10, 4, 9, 6, 4, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 430         {4, 10, 6, 4, 9, 10, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1},
 431         {10, 0, 1, 10, 6, 0, 6, 4, 0, -1, -1, -1, -1, -1, -1, -1},
 432         {8, 3, 1, 8, 1, 6, 8, 6, 4, 6, 1, 10, -1, -1, -1, -1},
 433         {1, 4, 9, 1, 2, 4, 2, 6, 4, -1, -1, -1, -1, -1, -1, -1},
 434         {3, 0, 8, 1, 2, 9, 2, 4, 9, 2, 6, 4, -1, -1, -1, -1},
 435         {0, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 436         {8, 3, 2, 8, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1},
 437         {10, 4, 9, 10, 6, 4, 11, 2, 3, -1, -1, -1, -1, -1, -1, -1},
 438         {0, 8, 2, 2, 8, 11, 4, 9, 10, 4, 10, 6, -1, -1, -1, -1},
 439         {3, 11, 2, 0, 1, 6, 0, 6, 4, 6, 1, 10, -1, -1, -1, -1},
 440         {6, 4, 1, 6, 1, 10, 4, 8, 1, 2, 1, 11, 8, 11, 1, -1},
 441         {9, 6, 4, 9, 3, 6, 9, 1, 3, 11, 6, 3, -1, -1, -1, -1},
 442         {8, 11, 1, 8, 1, 0, 11, 6, 1, 9, 1, 4, 6, 4, 1, -1},
 443         {3, 11, 6, 3, 6, 0, 0, 6, 4, -1, -1, -1, -1, -1, -1, -1},
 444         {6, 4, 8, 11, 6, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 445         {7, 10, 6, 7, 8, 10, 8, 9, 10, -1, -1, -1, -1, -1, -1, -1},
 446         {0, 7, 3, 0, 10, 7, 0, 9, 10, 6, 7, 10, -1, -1, -1, -1},
 447         {10, 6, 7, 1, 10, 7, 1, 7, 8, 1, 8, 0, -1, -1, -1, -1},
 448         {10, 6, 7, 10, 7, 1, 1, 7, 3, -1, -1, -1, -1, -1, -1, -1},
 449         {1, 2, 6, 1, 6, 8, 1, 8, 9, 8, 6, 7, -1, -1, -1, -1},
 450         {2, 6, 9, 2, 9, 1, 6, 7, 9, 0, 9, 3, 7, 3, 9, -1},
 451         {7, 8, 0, 7, 0, 6, 6, 0, 2, -1, -1, -1, -1, -1, -1, -1},
 452         {7, 3, 2, 6, 7, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 453         {2, 3, 11, 10, 6, 8, 10, 8, 9, 8, 6, 7, -1, -1, -1, -1},
 454         {2, 0, 7, 2, 7, 11, 0, 9, 7, 6, 7, 10, 9, 10, 7, -1},
 455         {1, 8, 0, 1, 7, 8, 1, 10, 7, 6, 7, 10, 2, 3, 11, -1},
 456         {11, 2, 1, 11, 1, 7, 10, 6, 1, 6, 7, 1, -1, -1, -1, -1},
 457         {8, 9, 6, 8, 6, 7, 9, 1, 6, 11, 6, 3, 1, 3, 6, -1},
 458         {0, 9, 1, 11, 6, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 459         {7, 8, 0, 7, 0, 6, 3, 11, 0, 11, 6, 0, -1, -1, -1, -1},
 460         {7, 11, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 461         {7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 462         {3, 0, 8, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 463         {0, 1, 9, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 464         {8, 1, 9, 8, 3, 1, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1},
 465         {10, 1, 2, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 466         {1, 2, 10, 3, 0, 8, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1},
 467         {2, 9, 0, 2, 10, 9, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1},
 468         {6, 11, 7, 2, 10, 3, 10, 8, 3, 10, 9, 8, -1, -1, -1, -1},
 469         {7, 2, 3, 6, 2, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 470         {7, 0, 8, 7, 6, 0, 6, 2, 0, -1, -1, -1, -1, -1, -1, -1},
 471         {2, 7, 6, 2, 3, 7, 0, 1, 9, -1, -1, -1, -1, -1, -1, -1},
 472         {1, 6, 2, 1, 8, 6, 1, 9, 8, 8, 7, 6, -1, -1, -1, -1},
 473         {10, 7, 6, 10, 1, 7, 1, 3, 7, -1, -1, -1, -1, -1, -1, -1},
 474         {10, 7, 6, 1, 7, 10, 1, 8, 7, 1, 0, 8, -1, -1, -1, -1},
 475         {0, 3, 7, 0, 7, 10, 0, 10, 9, 6, 10, 7, -1, -1, -1, -1},
 476         {7, 6, 10, 7, 10, 8, 8, 10, 9, -1, -1, -1, -1, -1, -1, -1},
 477         {6, 8, 4, 11, 8, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 478         {3, 6, 11, 3, 0, 6, 0, 4, 6, -1, -1, -1, -1, -1, -1, -1},
 479         {8, 6, 11, 8, 4, 6, 9, 0, 1, -1, -1, -1, -1, -1, -1, -1},
 480         {9, 4, 6, 9, 6, 3, 9, 3, 1, 11, 3, 6, -1, -1, -1, -1},
 481         {6, 8, 4, 6, 11, 8, 2, 10, 1, -1, -1, -1, -1, -1, -1, -1},
 482         {1, 2, 10, 3, 0, 11, 0, 6, 11, 0, 4, 6, -1, -1, -1, -1},
 483         {4, 11, 8, 4, 6, 11, 0, 2, 9, 2, 10, 9, -1, -1, -1, -1},
 484         {10, 9, 3, 10, 3, 2, 9, 4, 3, 11, 3, 6, 4, 6, 3, -1},
 485         {8, 2, 3, 8, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1},
 486         {0, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 487         {1, 9, 0, 2, 3, 4, 2, 4, 6, 4, 3, 8, -1, -1, -1, -1},
 488         {1, 9, 4, 1, 4, 2, 2, 4, 6, -1, -1, -1, -1, -1, -1, -1},
 489         {8, 1, 3, 8, 6, 1, 8, 4, 6, 6, 10, 1, -1, -1, -1, -1},
 490         {10, 1, 0, 10, 0, 6, 6, 0, 4, -1, -1, -1, -1, -1, -1, -1},
 491         {4, 6, 3, 4, 3, 8, 6, 10, 3, 0, 3, 9, 10, 9, 3, -1},
 492         {10, 9, 4, 6, 10, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 493         {4, 9, 5, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 494         {0, 8, 3, 4, 9, 5, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1},
 495         {5, 0, 1, 5, 4, 0, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1},
 496         {11, 7, 6, 8, 3, 4, 3, 5, 4, 3, 1, 5, -1, -1, -1, -1},
 497         {9, 5, 4, 10, 1, 2, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1},
 498         {6, 11, 7, 1, 2, 10, 0, 8, 3, 4, 9, 5, -1, -1, -1, -1},
 499         {7, 6, 11, 5, 4, 10, 4, 2, 10, 4, 0, 2, -1, -1, -1, -1},
 500         {3, 4, 8, 3, 5, 4, 3, 2, 5, 10, 5, 2, 11, 7, 6, -1},
 501         {7, 2, 3, 7, 6, 2, 5, 4, 9, -1, -1, -1, -1, -1, -1, -1},
 502         {9, 5, 4, 0, 8, 6, 0, 6, 2, 6, 8, 7, -1, -1, -1, -1},
 503         {3, 6, 2, 3, 7, 6, 1, 5, 0, 5, 4, 0, -1, -1, -1, -1},
 504         {6, 2, 8, 6, 8, 7, 2, 1, 8, 4, 8, 5, 1, 5, 8, -1},
 505         {9, 5, 4, 10, 1, 6, 1, 7, 6, 1, 3, 7, -1, -1, -1, -1},
 506         {1, 6, 10, 1, 7, 6, 1, 0, 7, 8, 7, 0, 9, 5, 4, -1},
 507         {4, 0, 10, 4, 10, 5, 0, 3, 10, 6, 10, 7, 3, 7, 10, -1},
 508         {7, 6, 10, 7, 10, 8, 5, 4, 10, 4, 8, 10, -1, -1, -1, -1},
 509         {6, 9, 5, 6, 11, 9, 11, 8, 9, -1, -1, -1, -1, -1, -1, -1},
 510         {3, 6, 11, 0, 6, 3, 0, 5, 6, 0, 9, 5, -1, -1, -1, -1},
 511         {0, 11, 8, 0, 5, 11, 0, 1, 5, 5, 6, 11, -1, -1, -1, -1},
 512         {6, 11, 3, 6, 3, 5, 5, 3, 1, -1, -1, -1, -1, -1, -1, -1},
 513         {1, 2, 10, 9, 5, 11, 9, 11, 8, 11, 5, 6, -1, -1, -1, -1},
 514         {0, 11, 3, 0, 6, 11, 0, 9, 6, 5, 6, 9, 1, 2, 10, -1},
 515         {11, 8, 5, 11, 5, 6, 8, 0, 5, 10, 5, 2, 0, 2, 5, -1},
 516         {6, 11, 3, 6, 3, 5, 2, 10, 3, 10, 5, 3, -1, -1, -1, -1},
 517         {5, 8, 9, 5, 2, 8, 5, 6, 2, 3, 8, 2, -1, -1, -1, -1},
 518         {9, 5, 6, 9, 6, 0, 0, 6, 2, -1, -1, -1, -1, -1, -1, -1},
 519         {1, 5, 8, 1, 8, 0, 5, 6, 8, 3, 8, 2, 6, 2, 8, -1},
 520         {1, 5, 6, 2, 1, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 521         {1, 3, 6, 1, 6, 10, 3, 8, 6, 5, 6, 9, 8, 9, 6, -1},
 522         {10, 1, 0, 10, 0, 6, 9, 5, 0, 5, 6, 0, -1, -1, -1, -1},
 523         {0, 3, 8, 5, 6, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 524         {10, 5, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 525         {11, 5, 10, 7, 5, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 526         {11, 5, 10, 11, 7, 5, 8, 3, 0, -1, -1, -1, -1, -1, -1, -1},
 527         {5, 11, 7, 5, 10, 11, 1, 9, 0, -1, -1, -1, -1, -1, -1, -1},
 528         {10, 7, 5, 10, 11, 7, 9, 8, 1, 8, 3, 1, -1, -1, -1, -1},
 529         {11, 1, 2, 11, 7, 1, 7, 5, 1, -1, -1, -1, -1, -1, -1, -1},
 530         {0, 8, 3, 1, 2, 7, 1, 7, 5, 7, 2, 11, -1, -1, -1, -1},
 531         {9, 7, 5, 9, 2, 7, 9, 0, 2, 2, 11, 7, -1, -1, -1, -1},
 532         {7, 5, 2, 7, 2, 11, 5, 9, 2, 3, 2, 8, 9, 8, 2, -1},
 533         {2, 5, 10, 2, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1},
 534         {8, 2, 0, 8, 5, 2, 8, 7, 5, 10, 2, 5, -1, -1, -1, -1},
 535         {9, 0, 1, 5, 10, 3, 5, 3, 7, 3, 10, 2, -1, -1, -1, -1},
 536         {9, 8, 2, 9, 2, 1, 8, 7, 2, 10, 2, 5, 7, 5, 2, -1},
 537         {1, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 538         {0, 8, 7, 0, 7, 1, 1, 7, 5, -1, -1, -1, -1, -1, -1, -1},
 539         {9, 0, 3, 9, 3, 5, 5, 3, 7, -1, -1, -1, -1, -1, -1, -1},
 540         {9, 8, 7, 5, 9, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 541         {5, 8, 4, 5, 10, 8, 10, 11, 8, -1, -1, -1, -1, -1, -1, -1},
 542         {5, 0, 4, 5, 11, 0, 5, 10, 11, 11, 3, 0, -1, -1, -1, -1},
 543         {0, 1, 9, 8, 4, 10, 8, 10, 11, 10, 4, 5, -1, -1, -1, -1},
 544         {10, 11, 4, 10, 4, 5, 11, 3, 4, 9, 4, 1, 3, 1, 4, -1},
 545         {2, 5, 1, 2, 8, 5, 2, 11, 8, 4, 5, 8, -1, -1, -1, -1},
 546         {0, 4, 11, 0, 11, 3, 4, 5, 11, 2, 11, 1, 5, 1, 11, -1},
 547         {0, 2, 5, 0, 5, 9, 2, 11, 5, 4, 5, 8, 11, 8, 5, -1},
 548         {9, 4, 5, 2, 11, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 549         {2, 5, 10, 3, 5, 2, 3, 4, 5, 3, 8, 4, -1, -1, -1, -1},
 550         {5, 10, 2, 5, 2, 4, 4, 2, 0, -1, -1, -1, -1, -1, -1, -1},
 551         {3, 10, 2, 3, 5, 10, 3, 8, 5, 4, 5, 8, 0, 1, 9, -1},
 552         {5, 10, 2, 5, 2, 4, 1, 9, 2, 9, 4, 2, -1, -1, -1, -1},
 553         {8, 4, 5, 8, 5, 3, 3, 5, 1, -1, -1, -1, -1, -1, -1, -1},
 554         {0, 4, 5, 1, 0, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 555         {8, 4, 5, 8, 5, 3, 9, 0, 5, 0, 3, 5, -1, -1, -1, -1},
 556         {9, 4, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 557         {4, 11, 7, 4, 9, 11, 9, 10, 11, -1, -1, -1, -1, -1, -1, -1},
 558         {0, 8, 3, 4, 9, 7, 9, 11, 7, 9, 10, 11, -1, -1, -1, -1},
 559         {1, 10, 11, 1, 11, 4, 1, 4, 0, 7, 4, 11, -1, -1, -1, -1},
 560         {3, 1, 4, 3, 4, 8, 1, 10, 4, 7, 4, 11, 10, 11, 4, -1},
 561         {4, 11, 7, 9, 11, 4, 9, 2, 11, 9, 1, 2, -1, -1, -1, -1},
 562         {9, 7, 4, 9, 11, 7, 9, 1, 11, 2, 11, 1, 0, 8, 3, -1},
 563         {11, 7, 4, 11, 4, 2, 2, 4, 0, -1, -1, -1, -1, -1, -1, -1},
 564         {11, 7, 4, 11, 4, 2, 8, 3, 4, 3, 2, 4, -1, -1, -1, -1},
 565         {2, 9, 10, 2, 7, 9, 2, 3, 7, 7, 4, 9, -1, -1, -1, -1},
 566         {9, 10, 7, 9, 7, 4, 10, 2, 7, 8, 7, 0, 2, 0, 7, -1},
 567         {3, 7, 10, 3, 10, 2, 7, 4, 10, 1, 10, 0, 4, 0, 10, -1},
 568         {1, 10, 2, 8, 7, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 569         {4, 9, 1, 4, 1, 7, 7, 1, 3, -1, -1, -1, -1, -1, -1, -1},
 570         {4, 9, 1, 4, 1, 7, 0, 8, 1, 8, 7, 1, -1, -1, -1, -1},
 571         {4, 0, 3, 7, 4, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 572         {4, 8, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 573         {9, 10, 8, 10, 11, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 574         {3, 0, 9, 3, 9, 11, 11, 9, 10, -1, -1, -1, -1, -1, -1, -1},
 575         {0, 1, 10, 0, 10, 8, 8, 10, 11, -1, -1, -1, -1, -1, -1, -1},
 576         {3, 1, 10, 11, 3, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 577         {1, 2, 11, 1, 11, 9, 9, 11, 8, -1, -1, -1, -1, -1, -1, -1},
 578         {3, 0, 9, 3, 9, 11, 1, 2, 9, 2, 11, 9, -1, -1, -1, -1},
 579         {0, 2, 11, 8, 0, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 580         {3, 2, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 581         {2, 3, 8, 2, 8, 10, 10, 8, 9, -1, -1, -1, -1, -1, -1, -1},
 582         {9, 10, 2, 0, 9, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 583         {2, 3, 8, 2, 8, 10, 0, 1, 8, 1, 10, 8, -1, -1, -1, -1},
 584         {1, 10, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 585         {1, 3, 8, 9, 1, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 586         {0, 9, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 587         {0, 3, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
 588         {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
 589     };
 590
 591 }