#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int ck(int m[3][3], int rv[3][3], int rh[3][3]);
void pr(int m[3][3], int rv[3][3], int rh[3][3]);
int newp(int p[27], int n);
void init(int p[27], int m[3][3], int rv[3][3], int rh[3][3]);
void set(int m[3][3], int rv[3][3], int rh[3][3], int pa);
void reset(int p[27], int m[3][3], int rv[3][3], int rh[3][3]);

main()
{
  //srand(time(0));
  srand(3);

  int m[3][3];
  int rv[3][3];
  int rh[3][3];
  int p[27];

  int suc[28];
  for(int i=0;i<=27;i++) suc[i]=0;

  for(int t=0;t<30000000;t++)
  {
    init(p,m,rv,rh);
  
    int n;
  
    for(n=1;n<=8;n++)
    {
      set(m,rv,rh,newp(p,n));
    }
  
  
    for(n=9;n<=27;n++)
    {
      set(m,rv,rh,newp(p,n));

      if(ck(m,rv,rh))
        break;

      reset(p,m,rv,rh);
    }
    for(int i=n;i<=27;i++)
    {
      suc[i]++;
    }

    if(!(t%1000000)) printf("%d\n",t);
  }
  printf("\n");
  for(int i=0;i<=27;i++)
    printf("%d %d\n",i,suc[i]);
}

int ck(int m[3][3], int rv[3][3], int rh[3][3])
{
  int ad;

  do
  {
    ad=0;
    for(int i=0;i<3;i++)
      for(int j=0;j<3;j++)
      {
        if(rv[i][j])
          if(m[i][j] ^ m[(i+1)%3][j])
          {
            m[i][j]=1;
            m[(i+1)%3][j]=1;
            ad++;
          }
        if(rh[i][j])
          if(m[i][j] ^ m[i][(j+1)%3])
          {
            m[i][j]=1;
            m[i][(j+1)%3]=1;
            ad++;
          }
      }
   }
   while(ad>0);

   for(int i=0;i<3;i++)
     for(int j=0;j<3;j++)
       if(m[i][j]==0)
         return 0;
   return 1;
}

void reset(int p[27], int m[3][3], int rv[3][3], int rh[3][3])
{
  for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
      m[i][j] = 0;
      rv[i][j] = 0;
      rh[i][j] = 0;
    }
  for(int pa=0;pa<27;pa++)
    if(p[pa])
      switch(pa/9)
      {
        case 0:
            m[pa%9/3][pa%9%3]=1;
          break;
        case 1:
            rv[pa%9/3][pa%9%3]=1;
          break;
        case 2:
            rh[pa%9/3][pa%9%3]=1;
          break;
      }
}

void set(int m[3][3], int rv[3][3], int rh[3][3], int pa)
{
  switch(pa/9)
  {
    case 0:
        m[pa%9/3][pa%9%3]=1;
      break;
    case 1:
        rv[pa%9/3][pa%9%3]=1;
      break;
    case 2:
        rh[pa%9/3][pa%9%3]=1;
      break;
  }
}

void init(int p[27], int m[3][3], int rv[3][3], int rh[3][3])
{
  for(int i=0;i<27;i++)
    p[i]=0;
  for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
      m[i][j] = 0;
      rv[i][j] = 0;
      rh[i][j] = 0;
    }
}

int newp(int p[27], int n)
{
  int i = rand()%(27-n+1);
  int j = -1;
  for(;i>=0;i--)
  {
    j++;
    for(;p[j];j++)
      ;
  }
  p[j]=1;
  return j;
}

void pr(int m[3][3], int rv[3][3], int rh[3][3])
{
  for(int i=0;i<3;i++)
  {
    for(int j=0;j<3;j++)
    {
      printf("%s",m[i][j]?"o":" ");
      printf("%s",rh[i][j]?"--":"  ");
    }
    printf("\n");
    for(int j=0;j<3;j++)
      printf("%s",rv[i][j]?"|  ":"   ");
    printf("\n");
  }
  printf("=========\n");
}