#include <fstream.h>
#include <iostream.h>
#include <assert.h>

#define MAXPIECES 20
#define MAXORIENT 12
#define MAXPSIZE 10
#define MAXGSIZE 10 
#define DEBUGMODE true

int grid[MAXGSIZE][MAXGSIZE][2];
int mux[MAXGSIZE][MAXGSIZE][2];
int pieces[MAXPIECES][MAXORIENT][MAXPSIZE][MAXPSIZE][2];
int hei[MAXPIECES][MAXORIENT];
int wid[MAXPIECES][MAXORIENT];
int originrow[MAXPIECES][MAXORIENT];
int origincol[MAXPIECES][MAXORIENT];
int orinum[MAXPIECES];

int srow[MAXPIECES];
int scol[MAXPIECES];
int sori[MAXPIECES];
bool splaced[MAXPIECES];
int numpieces;
long numsols=0;

void printsol(void) {
  int maxrow=0; int maxcol=0;
  cout << "Solution:\n";
  for (int piece=0;piece<numpieces;piece++) if (splaced[piece]) {
    cout << "Piece " << piece << ":";
    cout << "  row " << srow[piece] << ",";
    cout << "  col " << scol[piece] << ",";
    cout << "  ori " << sori[piece] << "\n";

    for (int lcv=0;lcv<hei[piece][sori[piece]];lcv++) {
      for (int lcv2=0;lcv2<wid[piece][sori[piece]];lcv2++) {
        cout << pieces[piece][sori[piece]][lcv][lcv2][0] << " " 
             << pieces[piece][sori[piece]][lcv][lcv2][1] << " ";
      }
      cout << "\n";
    }
  }
}

bool tryplace(int piece,int ori,int currow, int curcol) {
  bool success = true;
  int orgrow = currow-originrow[piece][ori];
  int orgcol = curcol-origincol[piece][ori];
  // see if we can place the piece at that location.
  if ((orgrow>=0)&&(orgcol>=0)) {
    // will be within bounds
    for(int row=0;row<hei[piece][ori];row++) 
      for(int col=0;col<wid[piece][ori];col++) 
        for(int cell=0;cell<2;cell++) {

      int dude = mux[orgrow+row][orgcol+col][cell];
      switch (dude) {
        case 0:
          if (pieces[piece][ori][row][col][cell]!=0) {
            success = false; goto OUTT; } break;
        case 1:
          if (pieces[piece][ori][row][col][cell]
            !=grid[orgrow+row][orgcol+col][cell]) {
            success = false; goto OUTT; } 
      }
    }
    OUTT: if (success) {
      // we can place!
      for(int row=0;row<hei[piece][ori];row++) 
        for(int col=0;col<wid[piece][ori];col++) 
          for(int cell=0;cell<2;cell++) {

        mux[orgrow+row][orgcol+col][cell] --;
        grid[orgrow+row][orgcol+col][cell]
          -= pieces[piece][ori][row][col][cell];
        if (pieces[piece][ori][row][col][cell]==11)
          mux[orgrow+row][orgcol+col][cell] --;
      }
      srow[piece] = currow;
      scol[piece] = curcol;
      sori[piece] = ori;
      splaced[piece] = true;
//if (DEBUGMODE) cout << "Placed " << piece << "\n";
    }
  }
  return(success);
}

void unplace(int piece,int ori,int currow, int curcol) {
  int orgrow = currow-originrow[piece][ori];
  int orgcol = curcol-origincol[piece][ori];
  for(int row=0;row<hei[piece][ori];row++) 
    for(int col=0;col<wid[piece][ori];col++) 
      for(int cell=0;cell<2;cell++) {

    if (pieces[piece][ori][row][col][cell]==11)
      mux[orgrow+row][orgcol+col][cell]++;
    mux[orgrow+row][orgcol+col][cell]++;
    grid[orgrow+row][orgcol+col][cell]
      += pieces[piece][ori][row][col][cell];
  }
  splaced[piece] = false;
//if (DEBUGMODE) cout << "UNPlaced " << piece << "\n";
}

void recurse( int placed, int currow, int curcol, int startpiece ) {
//if (DEBUGMODE) cout << "curstat: " << grid[currow][curcol][0]
//   << " " << grid[currow][curcol][1] << "\n";
if (DEBUGMODE && placed>=3) printsol();
  if (placed == numpieces) {
    // found solution
    printsol();
    numsols++;
  } else if ((grid[currow][curcol][0] == 0) 
          && (grid[currow][curcol][1] == 0)) {
    // cell filled, next piece
//if (DEBUGMODE) cout << "(" << currow << "," << curcol << ") filled\n";
    if (curcol==MAXGSIZE) {
      if (currow!=MAXGSIZE) 
        recurse(placed,currow+1,0,0);
    } else 
      recurse(placed,currow,curcol+1,0);
  } else {
    // try placing a piece
    for (int piece=startpiece;piece<numpieces;piece++) if (!splaced[piece]) 
                 for (int ori=0;ori<orinum[piece];ori++) {
      if (tryplace(piece,ori,currow,curcol)) {
//if (DEBUGMODE) cout << "Placed piece " << piece
 //   << " with ori " << ori
  //  << " at (" << currow << "," << curcol << ")\n";
        recurse(placed+1,currow,curcol,piece+1);
//if (DEBUGMODE) cout << "Pop\n";
        unplace(piece,ori,currow,curcol);
      }
    }
  }
}

void clearall (void) {
  for (int lcv1=0;lcv1<MAXGSIZE;lcv1++)
  for (int lcv2=0;lcv2<MAXGSIZE;lcv2++) {
    mux[lcv1][lcv2][0] = 2;
    mux[lcv1][lcv2][1] = 2;
    grid[lcv1][lcv2][0] = 0;
    grid[lcv1][lcv2][1] = 0;
  }
  for (int lcv1=0;lcv1<MAXPIECES;lcv1++) {
    srow[lcv1]=0;scol[lcv1]=0;sori[lcv1]=0;
//if (DEBUGMODE) cout << "UNPlaced " << lcv1 << "\n";
    splaced[lcv1]=false;orinum[lcv1]=0;
    for (int lcv2=0;lcv2<MAXORIENT;lcv2++) {
      hei[lcv1][lcv2]=0;
      wid[lcv1][lcv2]=0;
      originrow[lcv1][lcv2]=MAXPSIZE;
      origincol[lcv1][lcv2]=MAXPSIZE;
      for (int lcv3=0;lcv3<MAXPSIZE;lcv3++)
      for (int lcv4=0;lcv4<MAXPSIZE;lcv4++) {
        pieces[lcv1][lcv2][lcv3][lcv4][0]=0;
        pieces[lcv1][lcv2][lcv3][lcv4][1]=0;
      }
    }
  }
}

void eatpieces (ifstream & in) {
  int insanitym = 0;
  int insanityz = 0;
  int insanityx = 0; int insanityq = 0; 
  int pie=0;int ori=0;int row=0;int col=0;

  in >> ws;
  while (in.peek() != 'M') {
    insanitym++;
    in >> ws;
    while (in.peek() != 'Z') {
      insanityz++;
      in >> ws;
      while (in.peek() != 'Q') {
        insanityq++; 
        in >> ws;
        while (in.peek() != 'X') {
          insanityx++; 
          in >> pieces[pie][ori][row][col][0] 
             >> pieces[pie][ori][row][col][1];
          if ((originrow[pie][ori] > row) 
            &&(origincol[pie][ori] > col)
            &&((pieces[pie][ori][row][col][0] != 0)
             ||(pieces[pie][ori][row][col][1] != 0))) {
            originrow[pie][ori] = row;
            origincol[pie][ori] = col;
          }
          col++; 
          in >> ws; 
          assert(insanityx<65000);
        }
        if (col > wid[pie][ori]) wid[pie][ori] = col; 
        insanityx=0; 
        in.get(); // 'X'
        in >> ws; 
        row++; 
        col=0; 
        assert(insanityq<65000);
      }
      if (row > hei[pie][ori]) hei[pie][ori] = row;
      insanityq=0;
      in.get(); // 'Q'
      in >> ws;
      ori++;
      row=0;
      assert(insanityz<65000);
    }
    orinum[pie]=ori;
    insanityz=0;
    in.get(); // 'Z'
    in >> ws;
    pie++;
    ori=0;
    assert(insanitym<65000);
  }
  numpieces = pie;
}

void eatgrid (ifstream & in) {
  int insanityx = 0; int insanityq = 0; int row=0;int col=0;
  in >> ws;
  while (in.peek() != 'Q') {
    insanityq++; in >> ws;
    col=0;
    while (in.peek() != 'X') {
      insanityx++; in >> grid[row][col][0] >> grid[row][col][1];
      col++; in >> ws; assert(insanityx<65000);
    }
    insanityx=0; in.get(); in >> ws; row++; col=0; assert(insanityq<65000);
  }
  in.get();
}

void main (int argc, char * argv []) {
  ifstream gd;

  clearall();
  // First, the grid
  cout << "Reading grid " << argv[1] << "...\n";
  gd.open(argv[1],ios::in);
  eatgrid(gd); 
  gd.close();
  // Next, the pieces
  cout << "Reading pieces " << argv[2] << "...\n";
  gd.open(argv[2],ios::in);
  eatpieces(gd); 
  gd.close();
  
  cout << "Solving ... \n";
  recurse(0,0,0,0);
  cout << numsols << " total solutions.\n";
}