//    For information about Dao, visit
// http://www.di.fc.ul.pt/~jpn/gv/dao.htm

import java.io.*;
// import java.util.*;

class Move
{
   int x1, y1, x2, y2, z1;
   Move prev = null;
}

public class Dao {

static int[][][] u;
static int[][][][] s;
static int[] v, p;
static int[][] q, t, w, y;
static byte[][] x;
static char[] piece, letter;
static String[] choice;
static Move mv, mv2;

   public static String lesTekst()
     {
    	String s = null;
     	BufferedReader inn= new BufferedReader(new InputStreamReader (System.in));
      	try
      	      {	s = inn.readLine(); }
	catch(IOException e){} 
      	return s;}

   public static int lesInt()
      {
      	int tall = 0;
      	String s = null; 
      	boolean done = false;

      	do
             {	s = lesTekst();   
         	try
         	    {	tall = Integer.parseInt(s);
            		done = true;   }     
         	catch(NumberFormatException e)
                    {   System.out.print("Illegal format! Enter an integer: ");
            		System.out.flush();}}
	while(!done);
        return tall;}


public static void main(String args[])
   {
      int a, b, c, d, e, f, g, h, i, j, k, l, m, c1, f1, g1, h1, h2, h3, h4;
      s = new int[16][16][16][16];
      t = new int[1820][5];
      u = new int[1820][4][4];
      v = new int[1820];
      w = new int[4][4];
      x = new byte[1820][1820];
      y = new int[34][6];
      p = new int[34];
      q = new int[16][8];
      piece = new char[3];
      letter = new char[4];
      choice = new String[34];
      String stripe = "\n +---+---+---+---+";
      for (a = 0; a < 16; a++)
         {
            b = a % 4; c = a / 4;
            q[a][0] = a;
            q[a][1] = (3 - b) + 4 * c;
            q[a][2] = b + 4 * (3 - c);
            q[a][3] = (3 - b) + 4 * (3 - c);
            q[a][4] = c + 4 * b;
            q[a][5] = (3 - c) + 4 * b;
            q[a][6] = c + 4 * (3 - b);
            q[a][7] = (3 - c) + 4 * (3 - b);
         }
      d = -1;
      for (a = 0; a < 13; a++)
      for (b = a + 1; b < 14; b++)
      for (c = b + 1; c < 15; c++)
      for (g = c + 1; g < 16; g++)
         {
            d++;
            for (e = 0; e < 4; e++)
            for (f = 0; f < 4; f++)
               u[d][e][f] = 0;
            u[d][a % 4][a / 4] = 1;
            u[d][b % 4][b / 4] = 1;
            u[d][c % 4][c / 4] = 1;
            u[d][g % 4][g / 4] = 1;
            v[d] = 0;
            if (a + 4 == b && b + 4 == c && c + 4 == g) v[d] = 1;
            if (a % 4 == 0 && a + 3 == g) v[d] = 1;
            if (a % 4 < 3 && a + 1 == b && a + 4 == c && c + 1 == g) v[d] = 1;
            if (a == 0 && b == 3 && c == 12 && g == 15) v[d] = 1;
            s[a][b][c][g] = d; s[a][b][g][c] = d; s[a][c][b][g] = d;
            s[a][c][g][b] = d; s[a][g][b][c] = d; s[a][g][c][b] = d;
            s[b][a][c][g] = d; s[b][a][g][c] = d; s[b][c][a][g] = d;
            s[b][c][g][a] = d; s[b][g][a][c] = d; s[b][g][c][a] = d;
            s[c][b][a][g] = d; s[c][b][g][a] = d; s[c][a][b][g] = d;
            s[c][a][g][b] = d; s[c][g][b][a] = d; s[c][g][a][b] = d;
            s[g][b][c][a] = d; s[g][b][a][c] = d; s[g][c][b][a] = d;
            s[g][c][a][b] = d; s[g][a][b][c] = d; s[g][a][c][b] = d;
            t[d][0] = a; t[d][1] = b; t[d][2] = c; t[d][3] = g; t[d][4] = 2;
         }
      for (a = 0; a < 1820; a++)
      for (b = 1; b < 8; b++)
         {
            if (t[a][4] == 1) t[a][4] = 2;
            c = 0;
            while (c < 16 && t[a][4] == 2)
               {
                  if (u[a][c % 4][c / 4] != u[a][q[c][b] % 4][q[c][b] / 4])
                     {
                        if (u[a][c % 4][c / 4] == 1) t[a][4] = 1;
                        else t[a][4] = 0;
                     }
                  c++;
               }
            if (t[a][4] == 2) t[a][4] = 1;
         }
      System.out.println("\nDao oracle by J K Haugland");
      System.out.println("\nCounting positions...");
      j = 0;
      for (a = 0; a < 1820; a++)
      for (b = 0; b < 1820; b++)
         {
            x[a][b] = 100;                  // default value
            if (v[b] == 1) x[a][b] = 0;     // finished game - 0 moves left
            if (u[a][0][0] + u[b][0][1] + u[b][1][0] + u[b][1][1] == 4) x[a][b] = -1;
            if (u[a][3][0] + u[b][3][1] + u[b][2][0] + u[b][2][1] == 4) x[a][b] = -1;
            if (u[a][0][3] + u[b][0][2] + u[b][1][3] + u[b][1][2] == 4) x[a][b] = -1;
            if (u[a][3][3] + u[b][3][2] + u[b][2][3] + u[b][2][2] == 4) x[a][b] = -1;
            if (v[a] == 1) x[a][b] = 110;   // default value for illegal positions
            if (u[a][t[b][0] % 4][t[b][0] / 4] == 1 ||
                u[a][t[b][1] % 4][t[b][1] / 4] == 1 ||
                u[a][t[b][2] % 4][t[b][2] / 4] == 1 ||
                u[a][t[b][3] % 4][t[b][3] / 4] == 1) x[a][b] = 110;
            if (x[a][b] == 0) j++;
         }
      System.out.println("0  "+j);
      c = 1;
      do
      {
      j = 0;
      for (a = 0; a < 1820; a++)
      if (t[a][4] == 1)
      for (b = 0; b < 1820; b++)
      {
      if (x[a][b] == 100)                   // legal and not already assigned
      {
         stop : {
            for (k = 0; k < 4; k++)
            {
            d = t[a][k] % 4; e = t[a][k] / 4;
            for (f = -1; f <= 1; f++)
            for (g = -1; g <= 1; g++)
            if (f * f + g * g > 0)
            if (d + f >= 0 && d + f < 4 && e + g >= 0 && e + g < 4)
            if (u[a][d + f][e + g] == 0 && u[b][d + f][e + g] == 0)
               {
                  f1 = f; g1 = g;
                  while (d + f1 + f >= 0 && d + f1 + f < 4 &&
                         e + g1 + g >= 0 && e + g1 + g < 4 &&
                         u[a][d+f1+f][e+g1+g] == 0 &&
                         u[b][d+f1+f][e+g1+g] == 0)
                     { f1 += f; g1 += g; }
                  for (h = 0; h < 4; h++) p[h] = t[a][h];
                  p[k] = d + f1 + 4 * (e + g1);
                  h = s[p[0]][p[1]][p[2]][p[3]];
                  if (c % 2 == 1)
                     {
                        if (x[b][h] == c - 1)
                           {
                              x[a][b] = (byte)c;
                              break stop;
                           }
                     }
                  else
                     {
                        if (x[b][h] < c) x[a][b] = (byte)c;
                        else
                           {
                              x[a][b] = 100;
                              break stop;
                           }
                     }
               }
            }
         }
      if (x[a][b] == c)
         {
            j++;
            if (j % 10000 == 0) System.out.print("-");
            for (d = 1; d < 8; d++)
               {
                  e = s[q[t[a][0]][d]][q[t[a][1]][d]][q[t[a][2]][d]][q[t[a][3]][d]];
                  f = s[q[t[b][0]][d]][q[t[b][1]][d]][q[t[b][2]][d]][q[t[b][3]][d]];
                  if (x[e][f] != c)
                     {
                        x[e][f] = (byte)c;
                        j++;
                        if (j % 10000 == 0) System.out.print("-");
                     }
               }
         }
      }
      }
      System.out.println(c+"  "+j);
      c++;
      } while (j > 0);
      for (a = 0; a < 1820; a++)
      for (b = 0; b < 1820; b++)
         if (x[a][b] == 100) j++;
      System.out.println("\nNumber of draws: "+j);

      piece[0] = 'o'; piece[1] = ' '; piece[2] = 'x';
      letter[0] = 'A'; letter[1] = 'B';
      letter[2] = 'C'; letter[3] = 'D';

      System.out.println("\nPositions leading to maximum length perfect play:");
      for (a = 0; a < 1820; a++)
      if (t[a][4] == 1)
      for (b = 0; b < 1820; b++)
      if (x[a][b] == c - 2)
         {
            System.out.print("x -");
            for (d = 0; d < 4; d++)
               System.out.print(" "+letter[t[a][d] % 4]+(1+t[a][d] / 4));
            System.out.print("   o -");
            for (d = 0; d < 4; d++)
               System.out.print(" "+letter[t[b][d] % 4]+(1+t[b][d] / 4));
            System.out.println("");
         }

      a = s[0][5][10][15]; b = s[3][6][9][12];
      for (c = 0; c < 4; c++)
      for (d = 0; d < 4; d++) w[c][d] = u[a][c][d] - u[b][c][d];

      mv = new Move();

      while (x[a][b] > 0)
         {
            System.out.println(stripe);
            for (d = 3; d >= 0; d--)
               {
                  System.out.print((d+1)+"|");
                  for (c = 0; c < 4; c++)
                     System.out.print(" "+piece[1+w[c][d]]+" |");
                  System.out.println(stripe);
               }
            System.out.println("   A   B   C   D\n");

            j = 0;
            if (x[a][b] == 110) System.out.println("Illegal position"); else
            for (k = 0; k < 4; k++)
            {
            d = t[a][k] % 4; e = t[a][k] / 4;
            for (f = -1; f <= 1; f++)
            for (g = -1; g <= 1; g++)
            if (f * f + g * g > 0)
            if (d + f >= 0 && d + f < 4 && e + g >= 0 && e + g < 4)
            if (w[d + f][e + g] == 0)
               {
                  f1 = f; g1 = g;
                  while (d + f1 + f >= 0 && d + f1 + f < 4 &&
                         e + g1 + g >= 0 && e + g1 + g < 4 &&
                         w[d + f1 + f][e + g1 + g] == 0)
                     { f1 += f; g1 += g; }
                  for (h = 0; h < 4; h++) p[h] = t[a][h];
                  p[k] = d + f1 + 4 * (e + g1);
                  h = s[p[0]][p[1]][p[2]][p[3]];
                  j++;
                  choice[j] = ". "+letter[d]+(e+1)+" -> "+
                  letter[d+f1]+(e+g1+1)+" : ";
                  if (x[b][h] == 100) choice[j] += "Draw";
                  else
                     {
                        if (x[b][h] % 2 == 0) choice[j] += "Win";
                           else choice[j] += "Loss";
                        if (x[b][h] > 0) choice[j] += " in "+
                            (x[b][h]+1)+" moves";
                     }
                  y[j][0] = d; y[j][1] = e; y[j][2] = d+f1;
                  y[j][3] = e+g1; y[j][4] = h; y[j][5] = (int)x[b][h];
                  if (y[j][5] % 2 == 0)
                     y[j][5] = y[j][5] - 100;
                  else y[j][5] = 100 - y[j][5];
               }
            }
            for (c = 1; c <= j; c++) p[c] = c;
            for (c = 1; c < j; c++)
            for (d = c + 1; d <= j; d++)
               if (y[p[c]][5] > y[p[d]][5])
                  {
                     e = p[c];
                     p[c] = p[d];
                     p[d] = e;
                  }
            for (c = 1; c <= j; c++)
               System.out.println(c+choice[p[c]]);
            if (mv.prev != null)
               System.out.println("77. Retract last move");
            System.out.println("88. Back to start");
            System.out.println("99. Enter new position");
            do {
                  System.out.print("Enter alternative: ");
                  d = lesInt();
               }
            while (d != 99 && d != 88 && (d < 1 || d > j) &&
                   (d != 77 || mv.prev == null));
            if (d == 77)
              {
                b = a; a = mv.z1;
                for (c = 0; c < 4; c++)
                for (d = 0; d < 4; d++) w[c][d] = -w[c][d];
                piece[1] = piece[0]; piece[0] = piece[2];
                piece[2] = piece[1]; piece[1] = ' ';

                w[mv.x1][mv.y1] = 1;
                w[mv.x2][mv.y2] = 0;
                mv = mv.prev;
              }            
            else if (d == 88)
               {
                  a = s[0][5][10][15];
                  b = s[3][6][9][12];
                  for (c = 0; c < 4; c++)
                  for (d = 0; d < 4; d++)
                     w[c][d] = u[a][c][d] - u[b][c][d];
                  piece[0] = 'o'; piece[1] = ' '; piece[2] = 'x';
                  mv = new Move();
               }
            else if (d == 99)
               {
                  do {
                        System.out.println("Enter one four-digit number for each row");
                        System.out.println("0 = blank; 1 = 'x' (plays first); 2 = 'o'");
                        for (e = 0; e < 4; e++)
                        for (f = 0; f < 4; f++)
                           w[e][f] = 0;
                        for (e = 0; e < 4; e++)
                           {
                              f = lesInt();
                              w[0][3 - e] = f / 1000;
                              w[1][3 - e] = (f / 100) % 10;
                              w[2][3 - e] = (f / 10) % 10;
                              w[3][3 - e] = f % 10;
                              for (f = 0; f < 4; f++)
                                 if (w[f][3 - e] == 2) w[f][3 - e] = -1;
                           }
                        h1 = 0; h2 = 0; h3 = 0;
                        for (e = 0; e < 4; e++)
                        for (f = 0; f < 4; f++)
                           {
                              if (w[e][f] == 0) h1++;
                              if (w[e][f] == 1) h2++;
                              if (w[e][f] == -1) h3++;
                           }
                        if (h1 != 8) System.out.println
                           ("Error: "+h1+" blanks (should be 8)");
                        if (h2 != 4) System.out.println
                           ("Error: "+h2+" x's (should be 4)");
                        if (h3 != 4) System.out.println
                           ("Error: "+h3+" o's (should be 4)");
                     }
                  while (h1 != 8 || h2 != 4 || h3 != 4);
                  h1 = 0;
                  while (w[h1 % 4][h1 / 4] <= 0) h1++;
                  h2 = h1 + 1;
                  while (w[h2 % 4][h2 / 4] <= 0) h2++;
                  h3 = h2 + 1;
                  while (w[h3 % 4][h3 / 4] <= 0) h3++;
                  h4 = h3 + 1;
                  while (w[h4 % 4][h4 / 4] <= 0) h4++;
                  a = s[h1][h2][h3][h4];
                  h1 = 0;
                  while (w[h1 % 4][h1 / 4] >= 0) h1++;
                  h2 = h1 + 1;
                  while (w[h2 % 4][h2 / 4] >= 0) h2++;
                  h3 = h2 + 1;
                  while (w[h3 % 4][h3 / 4] >= 0) h3++;
                  h4 = h3 + 1;
                  while (w[h4 % 4][h4 / 4] >= 0) h4++;
                  b = s[h1][h2][h3][h4];
                  piece[0] = 'o'; piece[1] = ' '; piece[2] = 'x';
                  mv = new Move();
               }
            else
               {
                  c = p[d];
                  mv2 = new Move();
                  mv2 = mv;
                  mv = new Move();
                  mv.prev = mv2;
                  mv.x1 = y[c][0]; mv.y1 = y[c][1];
                  mv.x2 = y[c][2]; mv.y2 = y[c][3];
                  mv.z1 = a; a = b; b = y[c][4];

                  w[y[c][0]][y[c][1]] = 0;
                  w[y[c][2]][y[c][3]] = 1;
                  for (c = 0; c < 4; c++)
                  for (d = 0; d < 4; d++) w[c][d] = -w[c][d];
                  piece[1] = piece[0]; piece[0] = piece[2];
                  piece[2] = piece[1]; piece[1] = ' ';
               }
         }
      System.out.println(stripe);
      for (d = 3; d >= 0; d--)
         {
            System.out.print((d+1)+"|");
            for (c = 0; c < 4; c++)
               System.out.print(" "+piece[1+w[c][d]]+" |");
            System.out.println(stripe);
         }
      System.out.println("   A   B   C   D\n\n G A M E   O V E R\n");
   }
}