isosurface.cpp

Go to the documentation of this file.

/***************************************************************************
                        isosurface.cpp  -  description
                             -------------------
    begin                : Fri Mar 11 2005
    copyright            : (C) 2005-2006 by Ben Swerts
    email                : bswerts@users.sourceforge.net
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/





// C++ header files
#include <cassert>
#include <iostream>

// Xbrabo header files
#include "isosurface.h"
#include "vector3d.h"


IsoSurface::IsoSurface()
{

}

IsoSurface::~IsoSurface()
{
  clearSurfaces();
}

void IsoSurface::setParameters(const std::vector<double>* values, const Point3D<unsigned int>& pointDimension, const Point3D<float>& pointDelta, const Point3D<float>& pointOrigin)
{
  clearParameters();

  // make a copy of the density values
  densityValues.assign(values->begin(), values->end());
  // assign the other values
  numPoints = pointDimension;
  delta = pointDelta;
  origin = pointOrigin;
}

void IsoSurface::addSurface(const double isoDensity)
{
  isoLevels.push_back(isoDensity);
  calculateSurface(isoDensity);

  // renaming
  vector<Point3D<float> >* singleVerticesList = new vector<Point3D<float> >;
  vector<unsigned int>* singleTriangleIndices = new vector<unsigned int>;
  renameVerticesAndTriangles(singleVerticesList, singleTriangleIndices);
  verticesList.push_back(singleVerticesList);
  triangleIndices.push_back(singleTriangleIndices);

  // normals
  vector<float>* singleNormals = new vector<float>;
  calculateNormals(singleNormals, numSurfaces() - 1);
  normals.push_back(singleNormals);
}

void IsoSurface::changeSurface(const unsigned int surface, const double isoDensity)
{
  if(surface >= numSurfaces())
    return;

  isoLevels[surface] = isoDensity;
  calculateSurface(isoDensity);
  renameVerticesAndTriangles(verticesList[surface], triangleIndices[surface]);
  calculateNormals(normals[surface], surface);
}

bool IsoSurface::densityPresent() const
{
  return densityValues.size() != 0;
}

unsigned int IsoSurface::numSurfaces() const
{
  return isoLevels.size();
}

unsigned int IsoSurface::numTriangles(const unsigned int surface) const
{
  if(surface >= numSurfaces())
    return 0;

  return triangleIndices[surface]->size()/3;
}

unsigned int IsoSurface::numVertices(const unsigned int surface) const
{
  if(surface >= numSurfaces())
    return 0;
 
  return verticesList[surface]->size();
}

void IsoSurface::getTriangle(const unsigned int surface, const unsigned int index, Point3D<float>& point1, Point3D<float>& point2, Point3D<float>& point3, Point3D<float>& normal1, Point3D<float>& normal2, Point3D<float>& normal3) const
{
  if(surface >= numSurfaces() || index >= triangleIndices[surface]->size()/3)
  {
    point1.setValues(0.0, 0.0, 0.0);
    point2.setValues(0.0, 0.0, 0.0);
    point3.setValues(0.0, 0.0, 0.0);
    normal1.setValues(0.0, 0.0, 0.0);
    normal2.setValues(0.0, 0.0, 0.0);
    normal3.setValues(0.0, 0.0, 0.0);
    return;
  }

  unsigned int id1, id2, id3;
  if(isoLevels[surface] < 0.0)
  {
    id1 = triangleIndices[surface]->at(index*3);
    id2 = triangleIndices[surface]->at(index*3 + 1);
    id3 = triangleIndices[surface]->at(index*3 + 2);
  }
  else
  {
    id2 = triangleIndices[surface]->at(index*3);
    id1 = triangleIndices[surface]->at(index*3 + 1);
    id3 = triangleIndices[surface]->at(index*3 + 2);
  }
  point1 = verticesList[surface]->at(id1);
  point2 = verticesList[surface]->at(id2);
  point3 = verticesList[surface]->at(id3);
  point1.add(origin);
  point2.add(origin);
  point3.add(origin);
  if(isoLevels[surface] < 0.0)
  {
    normal1.setValues(-normals[surface]->at(id1*3), -normals[surface]->at(id1*3 + 1), -normals[surface]->at(id1*3 + 2));
    normal2.setValues(-normals[surface]->at(id2*3), -normals[surface]->at(id2*3 + 1), -normals[surface]->at(id2*3 + 2));
    normal3.setValues(-normals[surface]->at(id3*3), -normals[surface]->at(id3*3 + 1), -normals[surface]->at(id3*3 + 2));
  }
  else
  {
    normal1.setValues(normals[surface]->at(id1*3), normals[surface]->at(id1*3 + 1), normals[surface]->at(id1*3 + 2));
    normal2.setValues(normals[surface]->at(id2*3), normals[surface]->at(id2*3 + 1), normals[surface]->at(id2*3 + 2));
    normal3.setValues(normals[surface]->at(id3*3), normals[surface]->at(id3*3 + 1), normals[surface]->at(id3*3 + 2));
  }
}

Point3D<float> IsoSurface::getPoint(const unsigned int surface, const unsigned int index) const
{
  if(surface >= numSurfaces() || index >= verticesList[surface]->size())
    return Point3D<float>(0.0f, 0.0f, 0.0f);
  
  Point3D<float> result = verticesList[surface]->at(index);
  result.add(origin);
  return result;
}

void IsoSurface::clearParameters()
{
  clearSurfaces();
  densityValues.clear();
}

void IsoSurface::clearSurfaces()
{
  for(unsigned int i = 0; i < numSurfaces(); i++)
  {
    delete verticesList[i];
    delete triangleIndices[i];
    delete normals[i];
  }
  isoLevels.clear();
  verticesList.clear();
  triangleIndices.clear();
  normals.clear();
}

void IsoSurface::removeSurface(const unsigned int surface)
{
  if(surface >= numSurfaces())
    return;

  delete verticesList[surface];
  delete triangleIndices[surface];
  delete normals[surface];
  vector< vector<Point3D<float> >* >::iterator itv = verticesList.begin();
  itv += surface;
  verticesList.erase(itv);
  vector< vector<unsigned int>* >::iterator itt = triangleIndices.begin();
  itt += surface;
  triangleIndices.erase(itt);
  vector< vector<float>* >::iterator itn = normals.begin();
  itn += surface;
  normals.erase(itn);
  vector<double>::iterator iti = isoLevels.begin();
  iti += surface;
  isoLevels.erase(iti);
}

Point3D<float> IsoSurface::getOrigin() const
{
  return origin;
}

Point3D<float> IsoSurface::getDelta() const
{
  return delta;
}

Point3D<unsigned int> IsoSurface::getNumPoints() const
{
  return numPoints;
}


void IsoSurface::calculateSurface(const double isoDensity)
{
  currentIsoLevel = isoDensity;
  vertices.clear();
  triangles.clear();

  for(unsigned int z = 0; z < numPoints.z() - 1; z++)
    for(unsigned int y = 0; y < numPoints.y() -1; y++)
            for(unsigned int x = 0; x < numPoints.x() - 1; x++)
      {
        unsigned int tableIndex = 0;
                    if(densityValues[getArrayIndex(x, y, z)] < currentIsoLevel)
                      tableIndex |= 1;
        if(densityValues[getArrayIndex(x, y+1, z)] < currentIsoLevel)
                      tableIndex |= 2;
                    if(densityValues[getArrayIndex(x+1, y+1, z)] < currentIsoLevel)
                      tableIndex |= 4;
                    if(densityValues[getArrayIndex(x+1, y, z)] < currentIsoLevel)
                      tableIndex |= 8;
                    if(densityValues[getArrayIndex(x, y, z+1)] < currentIsoLevel)
                      tableIndex |= 16;
                    if(densityValues[getArrayIndex(x, y+1, z+1)] < currentIsoLevel)
                      tableIndex |= 32;
                    if(densityValues[getArrayIndex(x+1, y+1, z+1)] < currentIsoLevel)
                      tableIndex |= 64;
                    if(densityValues[getArrayIndex(x+1, y, z+1)] < currentIsoLevel)
                      tableIndex |= 128;

                    if(edgeTable[tableIndex] != 0)
                    {
          if(edgeTable[tableIndex] & 8)
              {
            Point3D<float> point = intersection(x, y, z, 3);
                              unsigned int id = getEdgeID(x, y, z, 3);
                              vertices.insert(std::map<unsigned int, Point3D<float> >::value_type(id, point));
                      }
          if(edgeTable[tableIndex] & 1)
                      {
            Point3D<float> point = intersection(x, y, z, 0);
                              unsigned int id = getEdgeID(x, y, z, 0);
                              vertices.insert(std::map<unsigned int, Point3D<float> >::value_type(id, point));
                      }
          if(edgeTable[tableIndex] & 256)
                      {
            Point3D<float> point = intersection(x, y, z, 8);
                              unsigned int id = getEdgeID(x, y, z, 8);
                              vertices.insert(std::map<unsigned int, Point3D<float> >::value_type(id, point));
                      }
                
                      if(x == numPoints.x() - 2)
                      {
            if(edgeTable[tableIndex] & 4)
                              {
              Point3D<float> point = intersection(x, y, z, 2);
                                unsigned int id = getEdgeID(x, y, z, 2);
                                vertices.insert(std::map<unsigned int, Point3D<float> >::value_type(id, point));
                        }
            if(edgeTable[tableIndex] & 2048)
                              {
              Point3D<float> point = intersection(x, y, z, 11);
                                unsigned int id = getEdgeID(x, y, z, 11);
                                vertices.insert(std::map<unsigned int, Point3D<float> >::value_type(id, point));
                              }
                      }
                      if(y == numPoints.y() - 2)
                      {
            if(edgeTable[tableIndex] & 2)
                              {
              Point3D<float> point = intersection(x, y, z, 1);
                                unsigned int id = getEdgeID(x, y, z, 1);
                                vertices.insert(std::map<unsigned int, Point3D<float> >::value_type(id, point));
                        }
            if(edgeTable[tableIndex] & 512)
                              {
              Point3D<float> point = intersection(x, y, z, 9);
                                unsigned int id = getEdgeID(x, y, z, 9);
                                vertices.insert(std::map<unsigned int, Point3D<float> >::value_type(id, point));
                              }
                      }
                      if(z == numPoints.z() - 2)
                      {
            if(edgeTable[tableIndex] & 16)
                              {
              Point3D<float> point = intersection(x, y, z, 4);
                                unsigned int id = getEdgeID(x, y, z, 4);
                                vertices.insert(std::map<unsigned int, Point3D<float> >::value_type(id, point));
                        }
            if(edgeTable[tableIndex] & 128)
                              {
              Point3D<float> point = intersection(x, y, z, 7);
                                unsigned int id = getEdgeID(x, y, z, 7);
                                vertices.insert(std::map<unsigned int, Point3D<float> >::value_type(id, point));
                              }
                      }
          if((x == numPoints.x() - 2) && (y == numPoints.y() - 2))
                      {
            if(edgeTable[tableIndex] & 1024)
                              {
              Point3D<float> point = intersection(x, y, z, 10);
                                unsigned int id = getEdgeID(x, y, z, 10);
                                vertices.insert(std::map<unsigned int, Point3D<float> >::value_type(id, point));
                              }
                      }
          if((x == numPoints.x() - 2) && (z == numPoints.z() - 2))
                      {
            if(edgeTable[tableIndex] & 64)
                              {
              Point3D<float> point = intersection(x, y, z, 6);
                                unsigned int id = getEdgeID(x, y, z, 6);
                                vertices.insert(std::map<unsigned int, Point3D<float> >::value_type(id, point));
                              }
                      }
          if((y == numPoints.y() - 2) && (z == numPoints.z() - 2))
                      {
            if(edgeTable[tableIndex] & 32)
                              {
              Point3D<float> point = intersection(x, y, z, 5);
                                unsigned int id = getEdgeID(x, y, z, 5);
                                vertices.insert(std::map<unsigned int, Point3D<float> >::value_type(id, point));
                              }
                      }

                      for(unsigned int i = 0; triTable[tableIndex][i] != -1; i += 3)
                      {
            Triangle triangle;
                              triangle.pointID[0] = getEdgeID(x, y, z, triTable[tableIndex][i]);
                              triangle.pointID[1] = getEdgeID(x, y, z, triTable[tableIndex][i+1]);
                              triangle.pointID[2] = getEdgeID(x, y, z, triTable[tableIndex][i+2]);
                              triangles.push_back(triangle);
                      }
                    }
            }
}

Point3D<float> IsoSurface::intersection(const unsigned int x, const unsigned int y, const unsigned int z, const unsigned int edge)
{
  unsigned int v1x = x, v1y = y, v1z = z;
  unsigned int v2x = x, v2y = y, v2z = z;

  switch(edge)
  {
    case 0:  v2y += 1;
                         break;
          case 1:  v1y += 1;
                         v2x += 1;
                               v2y += 1;
                               break;
          case 2:  v1x += 1;
                         v1y += 1;
                               v2x += 1;
                   break;
          case 3:  v1x += 1;
                         break;
          case 4:  v1z += 1;
                         v2y += 1;
                               v2z += 1;
                               break;
          case 5:  v1y += 1;
                         v1z += 1;
             v2x += 1;
             v2y += 1;
             v2z += 1;
             break;
          case 6:  v1x += 1;
                   v1y += 1;
             v1z += 1;
             v2x += 1;
             v2z += 1;
             break;
          case 7:  v1x += 1;
                               v1z += 1;
                               v2z += 1;
                               break;
          case 8:  v2z += 1;
                         break;
    case 9:  v1y += 1;
             v2y += 1;
             v2z += 1;
             break;
    case 10: v1x += 1;
             v1y += 1;
             v2x += 1;
             v2y += 1;
             v2z += 1;
             break;
          case 11: v1x += 1;
                         v2x += 1;
                               v2z += 1;
                               break;
  }
  Point3D<float> point1(v1x * delta.x(), v1y * delta.y(), v1z * delta.z());
  Point3D<float> point2(v2x * delta.y(), v2y * delta.y(), v2z * delta.z());

  double var1 = densityValues[getArrayIndex(v1x, v1y, v1z)];
  double var2 = densityValues[getArrayIndex(v2x, v2y, v2z)];
  return interpolate(point1, point2, var1, var2);
}

Point3D<float> IsoSurface::interpolate(const Point3D<float> point1, const Point3D<float> point2, const double var1, const double var2)
{
  const float mu = static_cast<float>((currentIsoLevel - var1)/(var2 - var1));
  const float x = point1.x() + mu*(point2.x() - point1.x());
  const float y = point1.y() + mu*(point2.y() - point1.y());
  const float z = point1.z() + mu*(point2.z() - point1.z());

  return Point3D<float>(x, y, z);
}

unsigned int IsoSurface::getEdgeID(const unsigned int x, const unsigned int y, const unsigned int z, const unsigned int edge)
{
  switch(edge)
  {
    case 0:  return getVertexID(x, y, z) + 1;
    case 1:  return getVertexID(x, y+1, z);
    case 2:  return getVertexID(x+1, y, z) + 1;
    case 3:  return getVertexID(x, y, z);
    case 4:  return getVertexID(x, y, z+1) + 1;
    case 5:  return getVertexID(x, y+1, z+1);
    case 6:  return getVertexID(x+1, y, z+1) + 1;
    case 7:  return getVertexID(x, y, z+1);
    case 8:  return getVertexID(x, y, z) + 2;
    case 9:  return getVertexID(x, y+1, z) + 2;
    case 10: return getVertexID(x+1, y+1, z) + 2;
    case 11: return getVertexID(x+1, y, z) + 2;
    default: return static_cast<unsigned int>(-1); // should be a very large positive number 
  }
}

unsigned int IsoSurface::getVertexID(const unsigned int x, const unsigned int y, const unsigned int z)
{
  return 3*getArrayIndex(x, y, z);
}

void IsoSurface::renameVerticesAndTriangles(vector<Point3D<float> >* singleVerticesList, vector<unsigned int>* singleTriangleIndices)
{
  unsigned int nextID = 0;
  std::map<unsigned int, Point3D<float> >::iterator itVertices = vertices.begin();
  std::vector<Triangle>::iterator itTriangles = triangles.begin();

  while(itVertices != vertices.end())
  {
    (*itVertices).second.setID(nextID++);
          itVertices++;
  }

  while(itTriangles != triangles.end())
  {
    for(unsigned int i = 0; i < 3; i++)
          {
      unsigned int newID = vertices[(*itTriangles).pointID[i]].id();
            (*itTriangles).pointID[i] = newID;
          }
          itTriangles++;
  }

  singleVerticesList->clear();
  singleVerticesList->reserve(vertices.size());
  singleTriangleIndices->clear();
  singleTriangleIndices->reserve(triangles.size()*3);

  // copy the vertices
  itVertices = vertices.begin();
  for(unsigned int i = 0; i < vertices.size(); i++, itVertices++)
    singleVerticesList->push_back((*itVertices).second);
  vertices.clear();
  // copy vertex indices which make triangles
  itTriangles = triangles.begin();
  for(unsigned int i = 0; i < triangles.size(); i++, itTriangles++)
  {
    singleTriangleIndices->push_back((*itTriangles).pointID[0]);
    singleTriangleIndices->push_back((*itTriangles).pointID[1]);
    singleTriangleIndices->push_back((*itTriangles).pointID[2]);
  }
  triangles.clear();
}

void IsoSurface::calculateNormals(vector<float>* singleNormals, const unsigned int surface)
{
  singleNormals->clear();
  singleNormals->reserve(triangleIndices[surface]->size());

  for(unsigned int i = 0; i < triangleIndices[surface]->size(); i++)
    singleNormals->push_back(0.0f);

  for(unsigned int i = 0; i < triangleIndices[surface]->size()/3; i++)
  {
    unsigned int id1 = triangleIndices[surface]->at(i*3);
    unsigned int id2 = triangleIndices[surface]->at(i*3 + 1);
    unsigned int id3 = triangleIndices[surface]->at(i*3 + 2);
          Vector3D<float> vector1(verticesList[surface]->at(id1), verticesList[surface]->at(id2));
          Vector3D<float> vector2(verticesList[surface]->at(id1), verticesList[surface]->at(id3));
          Vector3D<float> normal = vector2.cross(vector1);
          normal.normalize();
          singleNormals->at(id1*3)     += normal.x();
          singleNormals->at(id1*3 + 1) += normal.y();
          singleNormals->at(id1*3 + 2) += normal.z();
          singleNormals->at(id2*3)     += normal.x();
          singleNormals->at(id2*3 + 1) += normal.y();
          singleNormals->at(id2*3 + 2) += normal.z();
          singleNormals->at(id3*3)     += normal.x();
          singleNormals->at(id3*3 + 1) += normal.y();
          singleNormals->at(id3*3 + 2) += normal.z();
  }
}

unsigned int IsoSurface::getArrayIndex(const unsigned int x, const unsigned int y, const unsigned int z) const
{
  return x*numPoints.y()*numPoints.z() + y*numPoints.z() + z;
}


const unsigned int IsoSurface::edgeTable[256] = 
{
        0x0  , 0x109, 0x203, 0x30a, 0x406, 0x50f, 0x605, 0x70c,
        0x80c, 0x905, 0xa0f, 0xb06, 0xc0a, 0xd03, 0xe09, 0xf00,
        0x190, 0x99 , 0x393, 0x29a, 0x596, 0x49f, 0x795, 0x69c,
        0x99c, 0x895, 0xb9f, 0xa96, 0xd9a, 0xc93, 0xf99, 0xe90,
        0x230, 0x339, 0x33 , 0x13a, 0x636, 0x73f, 0x435, 0x53c,
        0xa3c, 0xb35, 0x83f, 0x936, 0xe3a, 0xf33, 0xc39, 0xd30,
        0x3a0, 0x2a9, 0x1a3, 0xaa , 0x7a6, 0x6af, 0x5a5, 0x4ac,
        0xbac, 0xaa5, 0x9af, 0x8a6, 0xfaa, 0xea3, 0xda9, 0xca0,
        0x460, 0x569, 0x663, 0x76a, 0x66 , 0x16f, 0x265, 0x36c,
        0xc6c, 0xd65, 0xe6f, 0xf66, 0x86a, 0x963, 0xa69, 0xb60,
        0x5f0, 0x4f9, 0x7f3, 0x6fa, 0x1f6, 0xff , 0x3f5, 0x2fc,
        0xdfc, 0xcf5, 0xfff, 0xef6, 0x9fa, 0x8f3, 0xbf9, 0xaf0,
        0x650, 0x759, 0x453, 0x55a, 0x256, 0x35f, 0x55 , 0x15c,
        0xe5c, 0xf55, 0xc5f, 0xd56, 0xa5a, 0xb53, 0x859, 0x950,
        0x7c0, 0x6c9, 0x5c3, 0x4ca, 0x3c6, 0x2cf, 0x1c5, 0xcc ,
        0xfcc, 0xec5, 0xdcf, 0xcc6, 0xbca, 0xac3, 0x9c9, 0x8c0,
        0x8c0, 0x9c9, 0xac3, 0xbca, 0xcc6, 0xdcf, 0xec5, 0xfcc,
        0xcc , 0x1c5, 0x2cf, 0x3c6, 0x4ca, 0x5c3, 0x6c9, 0x7c0,
        0x950, 0x859, 0xb53, 0xa5a, 0xd56, 0xc5f, 0xf55, 0xe5c,
        0x15c, 0x55 , 0x35f, 0x256, 0x55a, 0x453, 0x759, 0x650,
        0xaf0, 0xbf9, 0x8f3, 0x9fa, 0xef6, 0xfff, 0xcf5, 0xdfc,
        0x2fc, 0x3f5, 0xff , 0x1f6, 0x6fa, 0x7f3, 0x4f9, 0x5f0,
        0xb60, 0xa69, 0x963, 0x86a, 0xf66, 0xe6f, 0xd65, 0xc6c,
        0x36c, 0x265, 0x16f, 0x66 , 0x76a, 0x663, 0x569, 0x460,
        0xca0, 0xda9, 0xea3, 0xfaa, 0x8a6, 0x9af, 0xaa5, 0xbac,
        0x4ac, 0x5a5, 0x6af, 0x7a6, 0xaa , 0x1a3, 0x2a9, 0x3a0,
        0xd30, 0xc39, 0xf33, 0xe3a, 0x936, 0x83f, 0xb35, 0xa3c,
        0x53c, 0x435, 0x73f, 0x636, 0x13a, 0x33 , 0x339, 0x230,
        0xe90, 0xf99, 0xc93, 0xd9a, 0xa96, 0xb9f, 0x895, 0x99c,
        0x69c, 0x795, 0x49f, 0x596, 0x29a, 0x393, 0x99 , 0x190,
        0xf00, 0xe09, 0xd03, 0xc0a, 0xb06, 0xa0f, 0x905, 0x80c,
        0x70c, 0x605, 0x50f, 0x406, 0x30a, 0x203, 0x109, 0x0 
};

const int IsoSurface::triTable[256][16] =
{
  {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {0, 1, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {1, 8, 3, 9, 8, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {0, 8, 3, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {9, 2, 10, 0, 2, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {2, 8, 3, 2, 10, 8, 10, 9, 8, -1, -1, -1, -1, -1, -1, -1},
  {3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {0, 11, 2, 8, 11, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {1, 9, 0, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {1, 11, 2, 1, 9, 11, 9, 8, 11, -1, -1, -1, -1, -1, -1, -1},
  {3, 10, 1, 11, 10, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {0, 10, 1, 0, 8, 10, 8, 11, 10, -1, -1, -1, -1, -1, -1, -1},
  {3, 9, 0, 3, 11, 9, 11, 10, 9, -1, -1, -1, -1, -1, -1, -1},
  {9, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {4, 3, 0, 7, 3, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {0, 1, 9, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {4, 1, 9, 4, 7, 1, 7, 3, 1, -1, -1, -1, -1, -1, -1, -1},
  {1, 2, 10, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {3, 4, 7, 3, 0, 4, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1},
  {9, 2, 10, 9, 0, 2, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1},
  {2, 10, 9, 2, 9, 7, 2, 7, 3, 7, 9, 4, -1, -1, -1, -1},
  {8, 4, 7, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {11, 4, 7, 11, 2, 4, 2, 0, 4, -1, -1, -1, -1, -1, -1, -1},
  {9, 0, 1, 8, 4, 7, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1},
  {4, 7, 11, 9, 4, 11, 9, 11, 2, 9, 2, 1, -1, -1, -1, -1},
  {3, 10, 1, 3, 11, 10, 7, 8, 4, -1, -1, -1, -1, -1, -1, -1},
  {1, 11, 10, 1, 4, 11, 1, 0, 4, 7, 11, 4, -1, -1, -1, -1},
  {4, 7, 8, 9, 0, 11, 9, 11, 10, 11, 0, 3, -1, -1, -1, -1},
  {4, 7, 11, 4, 11, 9, 9, 11, 10, -1, -1, -1, -1, -1, -1, -1},
  {9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {9, 5, 4, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {0, 5, 4, 1, 5, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {8, 5, 4, 8, 3, 5, 3, 1, 5, -1, -1, -1, -1, -1, -1, -1},
  {1, 2, 10, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {3, 0, 8, 1, 2, 10, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1},
  {5, 2, 10, 5, 4, 2, 4, 0, 2, -1, -1, -1, -1, -1, -1, -1},
  {2, 10, 5, 3, 2, 5, 3, 5, 4, 3, 4, 8, -1, -1, -1, -1},
  {9, 5, 4, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {0, 11, 2, 0, 8, 11, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1},
  {0, 5, 4, 0, 1, 5, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1},
  {2, 1, 5, 2, 5, 8, 2, 8, 11, 4, 8, 5, -1, -1, -1, -1},
  {10, 3, 11, 10, 1, 3, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1},
  {4, 9, 5, 0, 8, 1, 8, 10, 1, 8, 11, 10, -1, -1, -1, -1},
  {5, 4, 0, 5, 0, 11, 5, 11, 10, 11, 0, 3, -1, -1, -1, -1},
  {5, 4, 8, 5, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1},
  {9, 7, 8, 5, 7, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {9, 3, 0, 9, 5, 3, 5, 7, 3, -1, -1, -1, -1, -1, -1, -1},
  {0, 7, 8, 0, 1, 7, 1, 5, 7, -1, -1, -1, -1, -1, -1, -1},
  {1, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {9, 7, 8, 9, 5, 7, 10, 1, 2, -1, -1, -1, -1, -1, -1, -1},
  {10, 1, 2, 9, 5, 0, 5, 3, 0, 5, 7, 3, -1, -1, -1, -1},
  {8, 0, 2, 8, 2, 5, 8, 5, 7, 10, 5, 2, -1, -1, -1, -1},
  {2, 10, 5, 2, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1},
  {7, 9, 5, 7, 8, 9, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1},
  {9, 5, 7, 9, 7, 2, 9, 2, 0, 2, 7, 11, -1, -1, -1, -1},
  {2, 3, 11, 0, 1, 8, 1, 7, 8, 1, 5, 7, -1, -1, -1, -1},
  {11, 2, 1, 11, 1, 7, 7, 1, 5, -1, -1, -1, -1, -1, -1, -1},
  {9, 5, 8, 8, 5, 7, 10, 1, 3, 10, 3, 11, -1, -1, -1, -1},
  {5, 7, 0, 5, 0, 9, 7, 11, 0, 1, 0, 10, 11, 10, 0, -1},
  {11, 10, 0, 11, 0, 3, 10, 5, 0, 8, 0, 7, 5, 7, 0, -1},
  {11, 10, 5, 7, 11, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {0, 8, 3, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {9, 0, 1, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {1, 8, 3, 1, 9, 8, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1},
  {1, 6, 5, 2, 6, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {1, 6, 5, 1, 2, 6, 3, 0, 8, -1, -1, -1, -1, -1, -1, -1},
  {9, 6, 5, 9, 0, 6, 0, 2, 6, -1, -1, -1, -1, -1, -1, -1},
  {5, 9, 8, 5, 8, 2, 5, 2, 6, 3, 2, 8, -1, -1, -1, -1},
  {2, 3, 11, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {11, 0, 8, 11, 2, 0, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1},
  {0, 1, 9, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1},
  {5, 10, 6, 1, 9, 2, 9, 11, 2, 9, 8, 11, -1, -1, -1, -1},
  {6, 3, 11, 6, 5, 3, 5, 1, 3, -1, -1, -1, -1, -1, -1, -1},
  {0, 8, 11, 0, 11, 5, 0, 5, 1, 5, 11, 6, -1, -1, -1, -1},
  {3, 11, 6, 0, 3, 6, 0, 6, 5, 0, 5, 9, -1, -1, -1, -1},
  {6, 5, 9, 6, 9, 11, 11, 9, 8, -1, -1, -1, -1, -1, -1, -1},
  {5, 10, 6, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {4, 3, 0, 4, 7, 3, 6, 5, 10, -1, -1, -1, -1, -1, -1, -1},
  {1, 9, 0, 5, 10, 6, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1},
  {10, 6, 5, 1, 9, 7, 1, 7, 3, 7, 9, 4, -1, -1, -1, -1},
  {6, 1, 2, 6, 5, 1, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1},
  {1, 2, 5, 5, 2, 6, 3, 0, 4, 3, 4, 7, -1, -1, -1, -1},
  {8, 4, 7, 9, 0, 5, 0, 6, 5, 0, 2, 6, -1, -1, -1, -1},
  {7, 3, 9, 7, 9, 4, 3, 2, 9, 5, 9, 6, 2, 6, 9, -1},
  {3, 11, 2, 7, 8, 4, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1},
  {5, 10, 6, 4, 7, 2, 4, 2, 0, 2, 7, 11, -1, -1, -1, -1},
  {0, 1, 9, 4, 7, 8, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1},
  {9, 2, 1, 9, 11, 2, 9, 4, 11, 7, 11, 4, 5, 10, 6, -1},
  {8, 4, 7, 3, 11, 5, 3, 5, 1, 5, 11, 6, -1, -1, -1, -1},
  {5, 1, 11, 5, 11, 6, 1, 0, 11, 7, 11, 4, 0, 4, 11, -1},
  {0, 5, 9, 0, 6, 5, 0, 3, 6, 11, 6, 3, 8, 4, 7, -1},
  {6, 5, 9, 6, 9, 11, 4, 7, 9, 7, 11, 9, -1, -1, -1, -1},
  {10, 4, 9, 6, 4, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {4, 10, 6, 4, 9, 10, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1},
  {10, 0, 1, 10, 6, 0, 6, 4, 0, -1, -1, -1, -1, -1, -1, -1},
  {8, 3, 1, 8, 1, 6, 8, 6, 4, 6, 1, 10, -1, -1, -1, -1},
  {1, 4, 9, 1, 2, 4, 2, 6, 4, -1, -1, -1, -1, -1, -1, -1},
  {3, 0, 8, 1, 2, 9, 2, 4, 9, 2, 6, 4, -1, -1, -1, -1},
  {0, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {8, 3, 2, 8, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1},
  {10, 4, 9, 10, 6, 4, 11, 2, 3, -1, -1, -1, -1, -1, -1, -1},
  {0, 8, 2, 2, 8, 11, 4, 9, 10, 4, 10, 6, -1, -1, -1, -1},
  {3, 11, 2, 0, 1, 6, 0, 6, 4, 6, 1, 10, -1, -1, -1, -1},
  {6, 4, 1, 6, 1, 10, 4, 8, 1, 2, 1, 11, 8, 11, 1, -1},
  {9, 6, 4, 9, 3, 6, 9, 1, 3, 11, 6, 3, -1, -1, -1, -1},
  {8, 11, 1, 8, 1, 0, 11, 6, 1, 9, 1, 4, 6, 4, 1, -1},
  {3, 11, 6, 3, 6, 0, 0, 6, 4, -1, -1, -1, -1, -1, -1, -1},
  {6, 4, 8, 11, 6, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {7, 10, 6, 7, 8, 10, 8, 9, 10, -1, -1, -1, -1, -1, -1, -1},
  {0, 7, 3, 0, 10, 7, 0, 9, 10, 6, 7, 10, -1, -1, -1, -1},
  {10, 6, 7, 1, 10, 7, 1, 7, 8, 1, 8, 0, -1, -1, -1, -1},
  {10, 6, 7, 10, 7, 1, 1, 7, 3, -1, -1, -1, -1, -1, -1, -1},
  {1, 2, 6, 1, 6, 8, 1, 8, 9, 8, 6, 7, -1, -1, -1, -1},
  {2, 6, 9, 2, 9, 1, 6, 7, 9, 0, 9, 3, 7, 3, 9, -1},
  {7, 8, 0, 7, 0, 6, 6, 0, 2, -1, -1, -1, -1, -1, -1, -1},
  {7, 3, 2, 6, 7, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {2, 3, 11, 10, 6, 8, 10, 8, 9, 8, 6, 7, -1, -1, -1, -1},
  {2, 0, 7, 2, 7, 11, 0, 9, 7, 6, 7, 10, 9, 10, 7, -1},
  {1, 8, 0, 1, 7, 8, 1, 10, 7, 6, 7, 10, 2, 3, 11, -1},
  {11, 2, 1, 11, 1, 7, 10, 6, 1, 6, 7, 1, -1, -1, -1, -1},
  {8, 9, 6, 8, 6, 7, 9, 1, 6, 11, 6, 3, 1, 3, 6, -1},
  {0, 9, 1, 11, 6, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {7, 8, 0, 7, 0, 6, 3, 11, 0, 11, 6, 0, -1, -1, -1, -1},
  {7, 11, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {3, 0, 8, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {0, 1, 9, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {8, 1, 9, 8, 3, 1, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1},
  {10, 1, 2, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {1, 2, 10, 3, 0, 8, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1},
  {2, 9, 0, 2, 10, 9, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1},
  {6, 11, 7, 2, 10, 3, 10, 8, 3, 10, 9, 8, -1, -1, -1, -1},
  {7, 2, 3, 6, 2, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {7, 0, 8, 7, 6, 0, 6, 2, 0, -1, -1, -1, -1, -1, -1, -1},
  {2, 7, 6, 2, 3, 7, 0, 1, 9, -1, -1, -1, -1, -1, -1, -1},
  {1, 6, 2, 1, 8, 6, 1, 9, 8, 8, 7, 6, -1, -1, -1, -1},
  {10, 7, 6, 10, 1, 7, 1, 3, 7, -1, -1, -1, -1, -1, -1, -1},
  {10, 7, 6, 1, 7, 10, 1, 8, 7, 1, 0, 8, -1, -1, -1, -1},
  {0, 3, 7, 0, 7, 10, 0, 10, 9, 6, 10, 7, -1, -1, -1, -1},
  {7, 6, 10, 7, 10, 8, 8, 10, 9, -1, -1, -1, -1, -1, -1, -1},
  {6, 8, 4, 11, 8, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {3, 6, 11, 3, 0, 6, 0, 4, 6, -1, -1, -1, -1, -1, -1, -1},
  {8, 6, 11, 8, 4, 6, 9, 0, 1, -1, -1, -1, -1, -1, -1, -1},
  {9, 4, 6, 9, 6, 3, 9, 3, 1, 11, 3, 6, -1, -1, -1, -1},
  {6, 8, 4, 6, 11, 8, 2, 10, 1, -1, -1, -1, -1, -1, -1, -1},
  {1, 2, 10, 3, 0, 11, 0, 6, 11, 0, 4, 6, -1, -1, -1, -1},
  {4, 11, 8, 4, 6, 11, 0, 2, 9, 2, 10, 9, -1, -1, -1, -1},
  {10, 9, 3, 10, 3, 2, 9, 4, 3, 11, 3, 6, 4, 6, 3, -1},
  {8, 2, 3, 8, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1},
  {0, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {1, 9, 0, 2, 3, 4, 2, 4, 6, 4, 3, 8, -1, -1, -1, -1},
  {1, 9, 4, 1, 4, 2, 2, 4, 6, -1, -1, -1, -1, -1, -1, -1},
  {8, 1, 3, 8, 6, 1, 8, 4, 6, 6, 10, 1, -1, -1, -1, -1},
  {10, 1, 0, 10, 0, 6, 6, 0, 4, -1, -1, -1, -1, -1, -1, -1},
  {4, 6, 3, 4, 3, 8, 6, 10, 3, 0, 3, 9, 10, 9, 3, -1},
  {10, 9, 4, 6, 10, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {4, 9, 5, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {0, 8, 3, 4, 9, 5, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1},
  {5, 0, 1, 5, 4, 0, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1},
  {11, 7, 6, 8, 3, 4, 3, 5, 4, 3, 1, 5, -1, -1, -1, -1},
  {9, 5, 4, 10, 1, 2, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1},
  {6, 11, 7, 1, 2, 10, 0, 8, 3, 4, 9, 5, -1, -1, -1, -1},
  {7, 6, 11, 5, 4, 10, 4, 2, 10, 4, 0, 2, -1, -1, -1, -1},
  {3, 4, 8, 3, 5, 4, 3, 2, 5, 10, 5, 2, 11, 7, 6, -1},
  {7, 2, 3, 7, 6, 2, 5, 4, 9, -1, -1, -1, -1, -1, -1, -1},
  {9, 5, 4, 0, 8, 6, 0, 6, 2, 6, 8, 7, -1, -1, -1, -1},
  {3, 6, 2, 3, 7, 6, 1, 5, 0, 5, 4, 0, -1, -1, -1, -1},
  {6, 2, 8, 6, 8, 7, 2, 1, 8, 4, 8, 5, 1, 5, 8, -1},
  {9, 5, 4, 10, 1, 6, 1, 7, 6, 1, 3, 7, -1, -1, -1, -1},
  {1, 6, 10, 1, 7, 6, 1, 0, 7, 8, 7, 0, 9, 5, 4, -1},
  {4, 0, 10, 4, 10, 5, 0, 3, 10, 6, 10, 7, 3, 7, 10, -1},
  {7, 6, 10, 7, 10, 8, 5, 4, 10, 4, 8, 10, -1, -1, -1, -1},
  {6, 9, 5, 6, 11, 9, 11, 8, 9, -1, -1, -1, -1, -1, -1, -1},
  {3, 6, 11, 0, 6, 3, 0, 5, 6, 0, 9, 5, -1, -1, -1, -1},
  {0, 11, 8, 0, 5, 11, 0, 1, 5, 5, 6, 11, -1, -1, -1, -1},
  {6, 11, 3, 6, 3, 5, 5, 3, 1, -1, -1, -1, -1, -1, -1, -1},
  {1, 2, 10, 9, 5, 11, 9, 11, 8, 11, 5, 6, -1, -1, -1, -1},
  {0, 11, 3, 0, 6, 11, 0, 9, 6, 5, 6, 9, 1, 2, 10, -1},
  {11, 8, 5, 11, 5, 6, 8, 0, 5, 10, 5, 2, 0, 2, 5, -1},
  {6, 11, 3, 6, 3, 5, 2, 10, 3, 10, 5, 3, -1, -1, -1, -1},
  {5, 8, 9, 5, 2, 8, 5, 6, 2, 3, 8, 2, -1, -1, -1, -1},
  {9, 5, 6, 9, 6, 0, 0, 6, 2, -1, -1, -1, -1, -1, -1, -1},
  {1, 5, 8, 1, 8, 0, 5, 6, 8, 3, 8, 2, 6, 2, 8, -1},
  {1, 5, 6, 2, 1, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {1, 3, 6, 1, 6, 10, 3, 8, 6, 5, 6, 9, 8, 9, 6, -1},
  {10, 1, 0, 10, 0, 6, 9, 5, 0, 5, 6, 0, -1, -1, -1, -1},
  {0, 3, 8, 5, 6, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {10, 5, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {11, 5, 10, 7, 5, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {11, 5, 10, 11, 7, 5, 8, 3, 0, -1, -1, -1, -1, -1, -1, -1},
  {5, 11, 7, 5, 10, 11, 1, 9, 0, -1, -1, -1, -1, -1, -1, -1},
  {10, 7, 5, 10, 11, 7, 9, 8, 1, 8, 3, 1, -1, -1, -1, -1},
  {11, 1, 2, 11, 7, 1, 7, 5, 1, -1, -1, -1, -1, -1, -1, -1},
  {0, 8, 3, 1, 2, 7, 1, 7, 5, 7, 2, 11, -1, -1, -1, -1},
  {9, 7, 5, 9, 2, 7, 9, 0, 2, 2, 11, 7, -1, -1, -1, -1},
  {7, 5, 2, 7, 2, 11, 5, 9, 2, 3, 2, 8, 9, 8, 2, -1},
  {2, 5, 10, 2, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1},
  {8, 2, 0, 8, 5, 2, 8, 7, 5, 10, 2, 5, -1, -1, -1, -1},
  {9, 0, 1, 5, 10, 3, 5, 3, 7, 3, 10, 2, -1, -1, -1, -1},
  {9, 8, 2, 9, 2, 1, 8, 7, 2, 10, 2, 5, 7, 5, 2, -1},
  {1, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {0, 8, 7, 0, 7, 1, 1, 7, 5, -1, -1, -1, -1, -1, -1, -1},
  {9, 0, 3, 9, 3, 5, 5, 3, 7, -1, -1, -1, -1, -1, -1, -1},
  {9, 8, 7, 5, 9, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {5, 8, 4, 5, 10, 8, 10, 11, 8, -1, -1, -1, -1, -1, -1, -1},
  {5, 0, 4, 5, 11, 0, 5, 10, 11, 11, 3, 0, -1, -1, -1, -1},
  {0, 1, 9, 8, 4, 10, 8, 10, 11, 10, 4, 5, -1, -1, -1, -1},
  {10, 11, 4, 10, 4, 5, 11, 3, 4, 9, 4, 1, 3, 1, 4, -1},
  {2, 5, 1, 2, 8, 5, 2, 11, 8, 4, 5, 8, -1, -1, -1, -1},
  {0, 4, 11, 0, 11, 3, 4, 5, 11, 2, 11, 1, 5, 1, 11, -1},
  {0, 2, 5, 0, 5, 9, 2, 11, 5, 4, 5, 8, 11, 8, 5, -1},
  {9, 4, 5, 2, 11, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {2, 5, 10, 3, 5, 2, 3, 4, 5, 3, 8, 4, -1, -1, -1, -1},
  {5, 10, 2, 5, 2, 4, 4, 2, 0, -1, -1, -1, -1, -1, -1, -1},
  {3, 10, 2, 3, 5, 10, 3, 8, 5, 4, 5, 8, 0, 1, 9, -1},
  {5, 10, 2, 5, 2, 4, 1, 9, 2, 9, 4, 2, -1, -1, -1, -1},
  {8, 4, 5, 8, 5, 3, 3, 5, 1, -1, -1, -1, -1, -1, -1, -1},
  {0, 4, 5, 1, 0, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {8, 4, 5, 8, 5, 3, 9, 0, 5, 0, 3, 5, -1, -1, -1, -1},
  {9, 4, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {4, 11, 7, 4, 9, 11, 9, 10, 11, -1, -1, -1, -1, -1, -1, -1},
  {0, 8, 3, 4, 9, 7, 9, 11, 7, 9, 10, 11, -1, -1, -1, -1},
  {1, 10, 11, 1, 11, 4, 1, 4, 0, 7, 4, 11, -1, -1, -1, -1},
  {3, 1, 4, 3, 4, 8, 1, 10, 4, 7, 4, 11, 10, 11, 4, -1},
  {4, 11, 7, 9, 11, 4, 9, 2, 11, 9, 1, 2, -1, -1, -1, -1},
  {9, 7, 4, 9, 11, 7, 9, 1, 11, 2, 11, 1, 0, 8, 3, -1},
  {11, 7, 4, 11, 4, 2, 2, 4, 0, -1, -1, -1, -1, -1, -1, -1},
  {11, 7, 4, 11, 4, 2, 8, 3, 4, 3, 2, 4, -1, -1, -1, -1},
  {2, 9, 10, 2, 7, 9, 2, 3, 7, 7, 4, 9, -1, -1, -1, -1},
  {9, 10, 7, 9, 7, 4, 10, 2, 7, 8, 7, 0, 2, 0, 7, -1},
  {3, 7, 10, 3, 10, 2, 7, 4, 10, 1, 10, 0, 4, 0, 10, -1},
  {1, 10, 2, 8, 7, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {4, 9, 1, 4, 1, 7, 7, 1, 3, -1, -1, -1, -1, -1, -1, -1},
  {4, 9, 1, 4, 1, 7, 0, 8, 1, 8, 7, 1, -1, -1, -1, -1},
  {4, 0, 3, 7, 4, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {4, 8, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {9, 10, 8, 10, 11, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {3, 0, 9, 3, 9, 11, 11, 9, 10, -1, -1, -1, -1, -1, -1, -1},
  {0, 1, 10, 0, 10, 8, 8, 10, 11, -1, -1, -1, -1, -1, -1, -1},
  {3, 1, 10, 11, 3, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {1, 2, 11, 1, 11, 9, 9, 11, 8, -1, -1, -1, -1, -1, -1, -1},
  {3, 0, 9, 3, 9, 11, 1, 2, 9, 2, 11, 9, -1, -1, -1, -1},
  {0, 2, 11, 8, 0, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {3, 2, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {2, 3, 8, 2, 8, 10, 10, 8, 9, -1, -1, -1, -1, -1, -1, -1},
  {9, 10, 2, 0, 9, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {2, 3, 8, 2, 8, 10, 0, 1, 8, 1, 10, 8, -1, -1, -1, -1},
  {1, 10, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {1, 3, 8, 9, 1, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {0, 9, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {0, 3, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
};

---