// For information about Breakthrough, visit
//
// http://en.wikipedia.org/wiki/Breakthrough_%28board_game%29
//
// To get enough memory, type:
//
// java -mx99m Breakth37
//

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

class Move
{
   int x11, x21, x31, x12, x22, x32, x13, x23, x33,
   x14, x24, x34, x15, x25, x35, x16, x26, x36, x17, x27, x37;
   Move prev = null;
}

public class Breakth37 {

static byte[] x;
static int[][] y, z;
static char[] p3, letter;
static int [] p1, p2, p4, p5, p6;
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 a00, a01, a02, a03, a04, a05, a06, a07, a08, a09, a10, a11, a12,
          a13, a14, a15, a16, a17, a18, a19, a20,
          b, c, d, e, f, g, i, j, k, l, h00, h01, h02, h03, h04, h05, h06,
          h07, h08, h09, h10, h11, h12, h13, h14, h15, h16, h17, h18, h19,
          h20, m, n, r, s;
      char q;
      x = new byte[80621568];
      y = new int[4][8];
      z = new int[4][8];
      letter = new char[4];
      p1 = new int[200];
      p2 = new int[200];
      p3 = new char[200];
      p4 = new int[200];
      p5 = new int[200];
      p6 = new int[200];
      String stripe = "\n +---+---+---+";


      System.out.println("\nBreakthrough 3x7 oracle by J K Haugland");
      System.out.println("\nCounting positions...");

      c = 0; d = 0;
      for (m = 0; m < 80621568; m++)
         {
            a00 = m / 40310784;
            a01 = (m / 20155392) % 2;
            a02 = (m / 10077696) % 2;
            a03 = (m /  5038848) % 2;
            a04 = (m /  2519424) % 2;
            a05 = (m /  1259712) % 2;
            a06 = (m /   419904) % 3;
            a07 = (m /   139968) % 3;
            a08 = (m /    46656) % 3;
            a09 = (m /    15552) % 3;
            a10 = (m /     5184) % 3;
            a11 = (m /     1728) % 3;
            a12 = (m /      576) % 3;
            a13 = (m /      192) % 3;
            a14 = (m /       64) % 3;
            a15 = (m /       32) % 2;
            a16 = (m /       16) % 2;
            a17 = (m /        8) % 2;
            a18 = (m /        4) % 2;
            a19 = (m /        2) % 2;
            a20 = m % 2;

            b = 0;
            if (a12 == 1 && a18 + a20 == 0) b = 3;
            if (a12 == 1 && a15 + a19 == 0) b = 3;
            if (a13 == 1 && a19 == 0) b = 3;
            if (a13 == 1 && a16 + a18 + a20 == 0) b = 3;
            if (a14 == 1 && a18 + a20 == 0) b = 3;
            if (a14 == 1 && a17 + a19 == 0) b = 3;

            if (a06 != 1 && a07 != 1 && a08 != 1 && a09 != 1 && a10 != 1 && a11 != 1 
             && a12 != 1 && a13 != 1 && a14 != 1 &&
            a00 + a01 + a02 + a03 + a04 + a05 == 0) b = 2;
            x[m] = (byte)b;
            if (b == 2) c++;
            if (b == 3)
               {
                  d++;
                  if (d % 1000000 == 0) System.out.print("-");
               }
         }
//      System.out.println ("2  "+c);
      System.out.println ("3  "+d);

      c = 4;
      do
      {
      j = 0;
      for (m = 0; m < 80621568; m++)
      if (x[m] == 0) // legal and not already assigned
      {
         a00 = m / 40310784;
         a01 = (m / 20155392) % 2;
         a02 = (m / 10077696) % 2;
         a03 = (m /  5038848) % 2;
         a04 = (m /  2519424) % 2;
         a05 = (m /  1259712) % 2;
         a06 = (m /   419904) % 3;
         a07 = (m /   139968) % 3;
         a08 = (m /    46656) % 3;
         a09 = (m /    15552) % 3;
         a10 = (m /     5184) % 3;
         a11 = (m /     1728) % 3;
         a12 = (m /      576) % 3;
         a13 = (m /      192) % 3;
         a14 = (m /       64) % 3;
         a15 = (m /       32) % 2;
         a16 = (m /       16) % 2;
         a17 = (m /        8) % 2;
         a18 = (m /        4) % 2;
         a19 = (m /        2) % 2;
         a20 = m % 2;
         stop : {
            y[1][1] = a00; y[2][1] = a01; y[3][1] = a02; y[1][2] = a03; y[2][2] = a04;
            y[3][2] = a05; y[1][3] = a06; y[2][3] = a07; y[3][3] = a08; y[1][4] = a09;
            y[2][4] = a10; y[3][4] = a11; y[1][5] = a12; y[2][5] = a13; y[3][5] = a14;
            y[1][6] = a15; y[2][6] = a16; y[3][6] = a17; y[1][7] = a18; y[2][7] = a19;
            y[3][7] = a20;
            for (d = 1; d < 4; d++)
            for (e = 1; e < 6; e++)
            if (y[d][e] == 1)
            for (f = 1; f < 4; f++)
            if (d - f < 2 && f - d < 2)
            if (y[f][e + 1] == 0 || (d != f && y[f][e + 1] == 2) || 
               (d != f && e == 5 && y[f][e + 1] == 1))
            {
            for (k = 1; k < 4; k++)
            for (l = 1; l < 8; l++)
               z[k][l] = y[k][l];
            z[d][e] = 0;
            z[f][e + 1] = 1;
            if (e < 5)
               {
                  h00 = z[3][7]; h01 = z[2][7]; h02 = z[1][7]; h03 = z[3][6];
                  h04 = z[2][6]; h05 = z[1][6]; h06 = 3 - z[3][5]; h07 = 3 - z[2][5];
                  h08 = 3 - z[1][5]; h09 = 3 - z[3][4]; h10 = 3 - z[2][4];
                  h11 = 3 - z[1][4]; h12 = 3 - z[3][3]; h13 = 3 - z[2][3];
                  h14 = 3 - z[1][3]; h15 = z[3][2]; h16 = z[2][2];
                  h17 = z[1][2]; h18 = z[3][1]; h19 = z[2][1]; h20 = z[1][1];
                  h06 = h06 % 3; h07 = h07 % 3; h08 = h08 % 3; h09 = h09 % 3;
                  h10 = h10 % 3; h11 = h11 % 3; h12 = h12 % 3; h13 = h13 % 3; h14 = h14 % 3;
                  n = h04 + 2 * (h03 + 2 * (h02 + 2 * (h01 + 2 * h00)));
                  n = h09 + 3 * (h08 + 3 * (h07 + 3 * (h06 + 3 * (h05 + 2 * n))));
                  n = h14 + 3 * (h13 + 3 * (h12 + 3 * (h11 + 3 * (h10 + 3 * n))));
                  n = h19 + 2 * (h18 + 2 * (h17 + 2 * (h16 + 2 * (h15 + 2 * n))));
                  n = h20 + 2 * n;
                  i = x[n];
                  if (c % 2 == 1)
                     {
                        if (i == c - 1)
                           {
                              x[m] = (byte)c;
                              break stop;
                           }
                     }
                  else
                     {
                        if (i < c && i > 0) x[m] = (byte)c;
                        else
                           {
                              x[m] = 0;
                              break stop;
                           }
                     }
               }
            else
               {
                  k = 0;
                  for (l = 1; l < 4; l++)
                  if (z[l][7] == 1 && (l - f == 1 || f - l == 1))
                     {
                        h00 = z[1][1]; h01 = z[2][1]; h02 = z[3][1]; h03 = z[1][2];
                        h04 = z[2][2]; h05 = z[3][2]; h06 = z[1][3]; h07 = z[2][3];
                        h08 = z[3][3]; h09 = z[1][4]; h10 = z[2][4]; h11 = z[3][4];
                        h12 = z[1][5]; h13 = z[2][5]; h14 = z[3][5]; h15 = z[1][6];
                        h16 = z[2][6]; h17 = z[3][6]; h18 = z[1][7]; h19 = z[2][7];
                        h20 = z[3][7];
                        if (l == 1) h18 = 0; if (l == 2) h19 = 0; if (l == 3) h20 = 0;
                        n = h04 + 2 * (h03 + 2 * (h02 + 2 * (h01 + 2 * h00)));
                        n = h09 + 3 * (h08 + 3 * (h07 + 3 * (h06 + 3 * (h05 + 2 * n))));
                        n = h14 + 3 * (h13 + 3 * (h12 + 3 * (h11 + 3 * (h10 + 3 * n))));
                        n = h19 + 2 * (h18 + 2 * (h17 + 2 * (h16 + 2 * (h15 + 2 * n))));
                        n = h20 + 2 * n;
                        i = x[n];
                        if (c % 2 == 1)
                           {
                              if (i % 2 == 0 || i == c) k = 1;
                           }
                        else
                           {
                              if (i % 2 == 0 && i > 0 && i < c) k = 1;
                           }
                     }
                  if (c % 2 == 1)
                     {
                        if (k == 0)
                           {
                              x[m] = (byte)c;
                              break stop;
                           }
                     }
                  else
                     {
                        if (k == 1) x[m] = (byte)c;
                        else
                           {
                              x[m] = 0;
                              break stop;
                           }
                     }
               }
            }
         }
      if (x[m] == c)
         {
            j++;
            if (j % 1000000 == 0) System.out.print("-");
            n = a04 + 2 * (a05 + 2 * (a00 + 2 * (a01 + 2 * a02)));
            n = a11 + 3 * (a06 + 3 * (a07 + 3 * (a08 + 3 * (a03 + 2 * n))));
            n = a12 + 3 * (a13 + 3 * (a14 + 3 * (a09 + 3 * (a10 + 3 * n))));
            n = a19 + 2 * (a20 + 2 * (a15 + 2 * (a16 + 2 * (a17 + 2 * n))));
            n = a18 + 2 * n;
            if (x[n] == 0)
               {
                  x[n] = (byte)c;
                  j++;
                  if (j % 1000000 == 0) System.out.print("-");
               }
         }
      }
      System.out.println(c+"  "+j);
      c++;
      } while (j > 0);

      letter[1] = 'A'; letter[2] = 'B'; letter[3] = 'C';

      System.out.println("\n\nDeepest positions:");
      for (m = 0; m < 80621568; m++)
      if (x[m] > 37)
      {
      a00 = m / 40310784;
      a01 = (m / 20155392) % 2;
      a02 = (m / 10077696) % 2;
      a03 = (m /  5038848) % 2;
      a04 = (m /  2519424) % 2;
      a05 = (m /  1259712) % 2;
      a06 = (m /   419904) % 3;
      a07 = (m /   139968) % 3;
      a08 = (m /    46656) % 3;
      a09 = (m /    15552) % 3;
      a10 = (m /     5184) % 3;
      a11 = (m /     1728) % 3;
      a12 = (m /      576) % 3;
      a13 = (m /      192) % 3;
      a14 = (m /       64) % 3;
      a15 = (m /       32) % 2;
      a16 = (m /       16) % 2;
      a17 = (m /        8) % 2;
      a18 = (m /        4) % 2;
      a19 = (m /        2) % 2;
      a20 = m % 2;
      System.out.println(" ");
      System.out.println(2 * a18+" "+2 * a19+" "+2 * a20);
      System.out.println(2 * a15+" "+2 * a16+" "+2 * a17);
      System.out.println(a12+" "+a13+" "+a14);
      System.out.println(a09+" "+a10+" "+a11);
      System.out.println(a06+" "+a07+" "+a08);
      System.out.println(a03+" "+a04+" "+a05);
      System.out.println(a00+" "+a01+" "+a02);
      System.out.println("("+x[m]+")");
      }
      j = 0; r = 77; s = 0;
      do {
      if (r == 77)
         {
            for (e = 1; e < 4; e++)
               {
                  y[e][1] = 1; y[e][2] = 1; y[e][3] = 0; 
                  y[e][4] = 0; y[e][5] = 0; y[e][6] = 2; y[e][7] = 2;
               }
            s = 0;
            mv = new Move();
         }
      else if (r == 88)
      {
      c = 1;
      do {
         c = 0;
         System.out.println("Enter one three-digit number for each row");
         System.out.println("1 = your piece, 2 = opponent piece, 0 = empty space");
         for (e = 1; e < 4; e++)
         for (f = 1; f < 8; f++)
            y[e][f] = 0;
         for (e = 1; e < 8; e++)
            {
               f = lesInt();
               y[1][8 - e] = f / 100;
               y[2][8 - e] = (f / 10) % 10;
               y[3][8 - e] = f % 10;
            }
         for (e = 1; e < 4; e++)
            {
               if (y[e][7] != 0 && y[e][7] != 2) c = 1;
               if (y[e][6] != 0 && y[e][6] != 2) c = 1;
               if (y[e][5] < 0 || y[e][5] > 2) c = 1;
               if (y[e][4] < 0 || y[e][4] > 2) c = 1;
               if (y[e][3] < 0 || y[e][3] > 2) c = 1;
               if (y[e][2] < 0 || y[e][2] > 2) c = 1;
               if (y[e][1] < 0 || y[e][1] > 1) c = 1;
            }
         f = 0;
         for (e = 1; e < 4; e++)
            if (y[e][2] == 2)
               {
                  f++;
                  g = 0;
                  for (i = 1; i < 4; i++)
                     if (i - e == 1 || e - i == 1)
                     if (y[i][1] == 1) g++;
                  if (g == 0) c = 1;
               }
         if (f > 1) c = 1;
         k = 0; l = 0;
         for (e = 1; e < 4; e++)
         for (f = 1; f < 8; f++)
            {
               if (y[e][f] == 1) k++;
               if (y[e][f] == 2) l++;
            }
         if (k == 0 || l == 0) c = 1;
         if (c == 1) System.out.println("Invalid choice or too few moves left!");
      } while (c == 1);
      s = 0;
      mv = new Move();
      }
      c = 0;
      System.out.println(stripe);
      for (f = 7; f > 0; f--)
         {
            System.out.print(f+"|");
            for (e = 1; e < 4; e++)
               {
                  if (s == 0) g = y[e][f]; else g = y[4 - e][8 - f];
                  if (g == 0) System.out.print("   |");
                  else if (g + s == 2) System.out.print(" x |");
                  else System.out.print(" o |");
               }
            System.out.println(stripe);
         }
      System.out.println("   A   B   C\n");
      for (e = 1; e < 4; e++)
      for (f = 6; f < 8; f++)
         if (y[e][f] == 2) y[e][f] = 1;
      if (y[1][2] == 2 || y[2][2] == 2 || y[3][2] == 2)
         {
            for (e = 1; e < 4; e++)
            if (y[e][1] == 1)
            for (f = 1; f < 4; f++)
            if (y[f][2] == 2 && (e - f == 1 || f - e == 1))
               {
                  c++;
                  p1[c] = e; p2[c] = 1; p3[c] = 'x'; p4[c] = f; p5[c] = 2;
               }
         }
      else
         {
            for (e = 1; e < 4; e++)
            for (f = 1; f < 6; f++)
            if (y[e][f] == 1)
            for (g = 1; g < 4; g++)
            if (e - g < 2 && g - e < 2)
            if (y[g][f + 1] == 0 || (e != g && y[g][f + 1] == 2) || 
               (e != g && f == 5 && y[g][f + 1] == 1))
               {
                  c++;
                  p1[c] = e; p2[c] = f; p4[c] = g; p5[c] = f + 1;
                  if (y[g][f + 1] == 0) p3[c] = '-'; else p3[c] = 'x';
               }
         }
      for (d = 1; d <= c; d++)
         {
            for (e = 1; e < 4; e++)
            for (f = 1; f < 8; f++)
               z[e][f] = y[e][f];
            z[p1[d]][p2[d]] = 0;
            z[p4[d]][p5[d]] = 1;
            if (p2[d] < 5)
               {
                  h00 = z[3][7]; h01 = z[2][7]; h02 = z[1][7]; h03 = z[3][6];
                  h04 = z[2][6]; h05 = z[1][6]; h06 = 3 - z[3][5]; h07 = 3 - z[2][5];
                  h08 = 3 - z[1][5]; h09 = 3 - z[3][4]; h10 = 3 - z[2][4];
                  h11 = 3 - z[1][4]; h12 = 3 - z[3][3]; h13 = 3 - z[2][3];
                  h14 = 3 - z[1][3]; h15 = z[3][2]; h16 = z[2][2];
                  h17 = z[1][2]; h18 = z[3][1]; h19 = z[2][1]; h20 = z[1][1];
                  h06 = h06 % 3; h07 = h07 % 3; h08 = h08 % 3; h09 = h09 % 3;
                  h10 = h10 % 3; h11 = h11 % 3; h12 = h12 % 3; h13 = h13 % 3; h14 = h14 % 3;
                  n = h04 + 2 * (h03 + 2 * (h02 + 2 * (h01 + 2 * h00)));
                  n = h09 + 3 * (h08 + 3 * (h07 + 3 * (h06 + 3 * (h05 + 2 * n))));
                  n = h14 + 3 * (h13 + 3 * (h12 + 3 * (h11 + 3 * (h10 + 3 * n))));
                  n = h19 + 2 * (h18 + 2 * (h17 + 2 * (h16 + 2 * (h15 + 2 * n))));
                  n = h20 + 2 * n;
                  p6[d] = 50 - (x[n] + 1);
                  if (p6[d] % 2 == 0) p6[d] = -p6[d];
                  p6[d] = p6[d] + 50;
               }
            else
               {
                  p6[d] = 100; e = p4[d];
                  for (f = 1; f < 4; f++)
                  if (z[f][7] == 1 && (e - f == 1 || f - e == 1))
                     {
                        h00 = z[1][1]; h01 = z[2][1]; h02 = z[3][1]; h03 = z[1][2];
                        h04 = z[2][2]; h05 = z[3][2]; h06 = z[1][3]; h07 = z[2][3];
                        h08 = z[3][3]; h09 = z[1][4]; h10 = z[2][4]; h11 = z[3][4];
                        h12 = z[1][5]; h13 = z[2][5]; h14 = z[3][5]; h15 = z[1][6];
                        h16 = z[2][6]; h17 = z[3][6]; h18 = z[1][7]; h19 = z[2][7];
                        h20 = z[3][7];
                        if (f == 1) h18 = 0; if (f == 2) h19 = 0; if (f == 3) h20 = 0;
                        n = h04 + 2 * (h03 + 2 * (h02 + 2 * (h01 + 2 * h00)));
                        n = h09 + 3 * (h08 + 3 * (h07 + 3 * (h06 + 3 * (h05 + 2 * n))));
                        n = h14 + 3 * (h13 + 3 * (h12 + 3 * (h11 + 3 * (h10 + 3 * n))));
                        n = h19 + 2 * (h18 + 2 * (h17 + 2 * (h16 + 2 * (h15 + 2 * n))));
                        n = h20 + 2 * n;
                        g = 50 - (x[n] + 2);
                        if (g % 2 == 0) g = -g;
                        g = g + 50;
                        if (g < p6[d]) p6[d] = g;
                     }
               }
         }
      for (e = 1; e < c; e++)
      for (f = e + 1; f <= c; f++)
      if (p6[e] < p6[f])
         {
            d = p1[e]; p1[e] = p1[f]; p1[f] = d;
            d = p2[e]; p2[e] = p2[f]; p2[f] = d;
            q = p3[e]; p3[e] = p3[f]; p3[f] = q;
            d = p4[e]; p4[e] = p4[f]; p4[f] = d;
            d = p5[e]; p5[e] = p5[f]; p5[f] = d;
            d = p6[e]; p6[e] = p6[f]; p6[f] = d;
         }
      for (e = 1; e < c; e++)
      for (f = e + 1; f <= c; f++)
      if (p6[e] == p6[f] && (p1[e] + 5 * p2[e] > p1[f] + 5 * p2[f] ||
         (p1[e] + 5 * p2[e] == p1[f] + 5 * p2[f] && p4[e] + 5 * p5[e] > p4[f] + 5 * p5[f])))
         {
            d = p1[e]; p1[e] = p1[f]; p1[f] = d;
            d = p2[e]; p2[e] = p2[f]; p2[f] = d;
            q = p3[e]; p3[e] = p3[f]; p3[f] = q;
            d = p4[e]; p4[e] = p4[f]; p4[f] = d;
            d = p5[e]; p5[e] = p5[f]; p5[f] = d;
            d = p6[e]; p6[e] = p6[f]; p6[f] = d;
         }
      for (d = 1; d <= c; d++)
         {
            if (s == 0) System.out.print(d+". "+letter[p1[d]]+p2[d]+p3[d]+letter[p4[d]]+p5[d]+": ");
            else System.out.print(d+". "+letter[4-p1[d]]+(8-p2[d])+p3[d]+letter[4-p4[d]]+(8-p5[d])+": ");
            if (p6[d] > 50) System.out.print("Win"); else System.out.print("Loss");
            p6[d] = p6[d] - 50;
            if (p6[d] < 0) p6[d] = -p6[d];
            p6[d] = 50 - p6[d];
            System.out.println(" in "+p6[d]+" moves");
         }
      if (p6[1] > 4)
      {
      if (mv.prev != null) System.out.println ("66. Retract last move");
      System.out.println ("77. Back to start");
      System.out.println ("88. Enter new position");
      System.out.println ("99. Quit");
      r = 0;
      do {
            System.out.print("Enter alternative: ");
            r = lesInt();
         }
      while (r != 99 && r != 88 && r!= 77 && (r != 66 || mv.prev == null) && (r < 1 || r > c));
      }
      else r = 77;
      if (r <= c)
         {
            for (e = 1; e < 4; e++)
            for (f = 6; f < 8; f++) y[e][f] = 2 * y[e][f];
            mv2 = new Move();
            mv2 = mv;
            mv = new Move();
            mv.prev = mv2;
            mv.x11 = y[1][1]; mv.x21 = y[2][1]; mv.x31 = y[3][1];
            mv.x12 = y[1][2]; mv.x22 = y[2][2]; mv.x32 = y[3][2];
            mv.x13 = y[1][3]; mv.x23 = y[2][3]; mv.x33 = y[3][3];
            mv.x14 = y[1][4]; mv.x24 = y[2][4]; mv.x34 = y[3][4];
            mv.x15 = y[1][5]; mv.x25 = y[2][5]; mv.x35 = y[3][5];
            mv.x16 = y[1][6]; mv.x26 = y[2][6]; mv.x36 = y[3][6];
            mv.x17 = y[1][7]; mv.x27 = y[2][7]; mv.x37 = y[3][7];
            y[p1[r]][p2[r]] = 0;
            y[p4[r]][p5[r]] = 1;
            for (e = 1; e < 4; e++)
            for (f = 1; f < 5; f++)
            if (f < 4 || e < 2)
               {
                  g = y[4 - e][8 - f];
                  y[4 - e][8 - f] = y[e][f];
                  y[e][f] = g;
               }
            for (e = 1; e < 4; e++)
            for (f = 1; f < 8; f++)
               if (y[e][f] > 0) y[e][f] = 3 - y[e][f];
         }
      if (r == 66)
         {
            y[1][1] = mv.x11; y[2][1] = mv.x21; y[3][1] = mv.x31;
            y[1][2] = mv.x12; y[2][2] = mv.x22; y[3][2] = mv.x32;
            y[1][3] = mv.x13; y[2][3] = mv.x23; y[3][3] = mv.x33;
            y[1][4] = mv.x14; y[2][4] = mv.x24; y[3][4] = mv.x34;
            y[1][5] = mv.x15; y[2][5] = mv.x25; y[3][5] = mv.x35;
            y[1][6] = mv.x16; y[2][6] = mv.x26; y[3][6] = mv.x36;
            y[1][7] = mv.x17; y[2][7] = mv.x27; y[3][7] = mv.x37;
            mv = mv.prev;
         }
      if (r == 99) j = 1;
      s = 1 - s;
      } while (j == 0);
   }
}