//  For information about Neutreeko, visit
//
// http://home.no.net/zamunda/neutreeko.htm
//
//     If you want to analyze 7x7, type
//
//          java -mx380m Neutreeko
//
//           to get enough memory


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

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

public class Neutreeko {

static int[][][] s, u;
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, b1, b2, b3, b4, b5, b6;
      String stripe;

      System.out.println("\nNeutreeko (c) 2001, 2002 J K Haugland");
      System.out.println("\nEnter 0 for standard Neutreeko");
      System.out.println("Enter 1 for the 2006 variant (reach the centre square to win)");
      System.out.println("\nOtherwise, enter board size: ");
      b2 = 0; b6 = 0;
      do {
        System.out.print("Width = ");
        b1 = lesInt();
        if (b1 == 0)
          {
            b1 = 5; b2 = 5; b6 = 1;
            System.out.println("\nWidth = 5");
            System.out.println("Height = 5");
            System.out.println("Orientation = both orthogonal and diagonal");
          }
        if (b1 == 1)
          {
            b1 = 5; b2 = 5; b6 = 5;
            System.out.println("\nWidth = 5");
            System.out.println("Height = 5");
          }
        if (b1 < 3) System.out.println("Too narrow");
        if (b1 > 7) System.out.println("Too wide");
      } while (b1 < 3 || b1 > 7);
      while (b2 < 3 || b2 > 7) {
        System.out.print("Height = ");
        b2 = lesInt();
        if (b2 < 3) System.out.println("Too low");
        if (b2 > 7) System.out.println("Too high");
      }
      if (b6 == 0) System.out.println("");
      if (b6 != 5)
      while (b6 < 1 || (b6 > 3 && (b6 > 4 || (b1 < 5 && b2 < 5)))) {
        System.out.println("Enter orientation of winning lines:");
        System.out.println("1 = both orthogonal and diagonal");
        System.out.println("2 = orthogonal only");
        System.out.println("3 = diagonal only");
        if (b1 > 4 || b2 > 4) System.out.println("4 = all equidistant");
        b6 = lesInt();
      }
      if (b1 == b2) b5 = 8; else b5 = 4;
      b3 = b1 * b2;
      b4 = (b3 * (b3 - 1) * (b3 - 2)) / 6;
      System.out.println("\nCounting positions...");
      s = new int[b3][b3][b3];
      t = new int[b4][4];
      u = new int[b4][b1][b2];
      v = new int[b4];
      w = new int[b1][b2];
      x = new byte[b4][b4];
      y = new int[25][6];
      p = new int[25];
      q = new int[b3][b5];
      piece = new char[3];
      letter = new char[7];
      choice = new String[25];
      for (a = 0; a < b3; a++)
         {
            b = a % b1; c = a / b1;
            q[a][0] = a;
            q[a][1] = (b1 - 1 - b) + b1 * c;
            q[a][2] = b + b1 * (b2 - 1 - c);
            q[a][3] = (b1 - 1 - b) + b1 * (b2 - 1 - c);
            if (b5 == 8)
               {
                  q[a][4] = c + b1 * b;
                  q[a][5] = (b1 - 1 - c) + b1 * b;
                  q[a][6] = c + b1 * (b1 - 1 - b);
                  q[a][7] = (b1 - 1 - c) + b1 * (b1 - 1 - b);
               }
         }
      d = -1;
      for (a = 0; a < b3 - 2; a++)
      for (b = a + 1; b < b3 - 1; b++)
      for (c = b + 1; c < b3; c++)
         {
            d++;
            for (e = 0; e < b1; e++)
            for (f = 0; f < b2; f++)
               u[d][e][f] = 0;
            u[d][a % b1][a / b1] = 1;
            u[d][b % b1][b / b1] = 1;
            u[d][c % b1][c / b1] = 1;
            v[d] = 0;
            if (b6 == 5) {if (a == 12 || b == 12 || c == 12) v[d] = 1;}
            else
            {
            if ((a % b1) + (c % b1) == 2 * (b % b1) && (a / b1) 
              + (c / b1) == 2 * (b / b1))
            if ((a % b1) - (c % b1) <= 2 && (c % b1) - (a % b1) 
              <= 2 && (a / b1) - (c / b1) <= 2 && (c / b1) 
              - (a / b1) <= 2) v[d] = 1;
            if (b6 == 2 && (a % b1) != (c % b1) &&
                            (a / b1) != (c / b1)) v[d] = 0;
            if (b6 == 3 && ((a % b1) == (c % b1) ||
                             (a / b1) == (c / b1))) v[d] = 0;
            if ((a % b1) + (c % b1) == 2 * (b % b1) && (a / b1) 
              + (c / b1) == 2 * (b / b1) && b6 == 4) v[d] = 1;
            }
            s[a][b][c] = d; s[a][c][b] = d; s[b][a][c] = d;
            s[b][c][a] = d; s[c][a][b] = d; s[c][b][a] = d;
            t[d][0] = a; t[d][1] = b; t[d][2] = c; t[d][3] = 2;
         }
      for (a = 0; a < b4; a++)
      for (b = 1; b < b5; b++)
         {
            if (t[a][3] == 1) t[a][3] = 2;
            c = 0;
            while (c < b3 && t[a][3] == 2)
               {
                  if (u[a][c % b1][c / b1] != u[a][q[c][b] % b1][q[c][b] / b1])
                     {
                        if (u[a][c % b1][c / b1] == 1) t[a][3] = 1;
                        else t[a][3] = 0;
                     }
                  c++;
               }
            if (t[a][3] == 2) t[a][3] = 1;
         }
      j = 0;
      for (a = 0; a < b4; a++)
      for (b = 0; b < b4; b++)
         {
            x[a][b] = 124;                  // default value
            if (v[b] == 1) x[a][b] = -120;  // finished game - 0 moves left
            if (v[a] == 1) x[a][b] = 126;   // default value for illegal positions
            if (u[a][t[b][0] % b1][t[b][0] / b1] == 1 ||
                u[a][t[b][1] % b1][t[b][1] / b1] == 1 ||
                u[a][t[b][2] % b1][t[b][2] / b1] == 1) x[a][b] = 126;
            if (x[a][b] == -120)
               {
                  j++;
                  if (j % 100000 == 0) System.out.print("-");
               }
         }
      System.out.println("0  "+j);
      c = -119;
      do                                // find all positions with c+120 moves left
      {
      j = 0;                            // number of such positions
      for (a = 0; a < b4; a++)
      if (t[a][3] == 1)
      for (b = 0; b < b4; b++)
      {
      if (x[a][b] == 124)               // legal and not already assigned
      {
         stop : {
            for (k = 0; k < 3; k++)
            {
            d = t[a][k] % b1; e = t[a][k] / b1;
            for (f = -1; f <= 1; f++)
            for (g = -1; g <= 1; g++)
            if (f * f + g * g > 0)
            if (d + f >= 0 && d + f < b1 && e + g >= 0 && e + g < b2)
            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 < b1 &&
                         e + g1 + g >= 0 && e + g1 + g < b2 &&
                         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 < 3; h++) p[h] = t[a][h];
                  p[k] = d + f1 + b1 * (e + g1);
                  h = s[p[0]][p[1]][p[2]];
                  if (c % 2 == 0)
                     {
                        if (x[b][h] < c) x[a][b] = (byte)c;
                        else
                           {
                              x[a][b] = 124;
                              break stop;
                           }
                     }
                  else
                     {
                        if (x[b][h] == c - 1)
                           {
                              x[a][b] = (byte)c;
                              break stop;
                           }
                     }
               }
            }
         }
      if (x[a][b] == c)
         {
            j++;
            if (j % 100000 == 0) System.out.print("-");
            for (d = 1; d < b5; d++)
               {
                  e = s[q[t[a][0]][d]][q[t[a][1]][d]][q[t[a][2]][d]];
                  f = s[q[t[b][0]][d]][q[t[b][1]][d]][q[t[b][2]][d]];
                  if (x[e][f] != c)
                     {
                        x[e][f] = (byte)c;
                        j++;
                        if (j % 100000 == 0) System.out.print("-");
                     }
               }
         }
      }
      }
      System.out.println((c+120)+"  "+j);
      c++;
      }
      while (j > 0);
      for (a = 0; a < b4; a++)
      for (b = 0; b < b4; b++)
         if (x[a][b] == 124) 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';
      letter[4] = 'E'; letter[5] = 'F'; letter[6] = 'G';

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

      if (b1 == 5 && b2 == 5 && b6 == 1)
        { a = s[1][3][17]; b = s[7][21][23]; }
      else if (b6 == 5)
        { a = s[2][15][19]; b = s[5][9][22]; }
      else
        { System.out.println("\n(This may not be a suitable opening position)");
          a = s[0][2][b3 - 2];
          b = s[1][b3 - 3][b3 - 1]; }
      for (c = 0; c < b1; c++)
      for (d = 0; d < b2; d++)
         w[c][d] = u[a][c][d] - u[b][c][d];

      mv = new Move();

      stripe = "\n +";
      for (c = 0; c < b1; c++) stripe += "---+";
      while (x[a][b] > -120)
        {
          System.out.println(stripe);
          for (d = b2 - 1; d >= 0; d--)
            {
              System.out.print((d+1)+"|");
              for (c = 0; c < b1; c++)
                System.out.print(" "+piece[1+w[c][d]]+" |");
              System.out.println(stripe);
            }
          for (c = 0; c < b1; c++) System.out.print("   "+letter[c]);
          System.out.println("");
          System.out.println("");
          j = 0;
          if (x[a][b] == 126) System.out.println("Illegal position"); else
          for (k = 0; k < 3; k++)
          {
          d = t[a][k] % b1; e = t[a][k] / b1;
          for (f = -1; f <= 1; f++)
          for (g = -1; g <= 1; g++)
          if (f * f + g * g > 0)
          if (d + f >= 0 && d + f < b1 && e + g >= 0 && e + g < b2)
          if (w[d + f][e + g] == 0)
            {
              f1 = f; g1 = g;
              while (d + f1 + f >= 0 && d + f1 + f < b1 &&
                     e + g1 + g >= 0 && e + g1 + g < b2 &&
                     w[d + f1 + f][e + g1 + g] == 0)
                { f1 += f; g1 += g; }
              for (h = 0; h < 3; h++) p[h] = t[a][h];
              p[k] = d + f1 + b1 * (e + g1);
              h = s[p[0]][p[1]][p[2]];
              j++;
              choice[j] = ". "+letter[d]+(e+1)+" -> "+letter[d+f1]
                        +(e+g1+1)+" : ";
              if (x[b][h] == 124) choice[j] += "Draw";
              else
                {
                  if (x[b][h] % 2 == 0) choice[j] += "Win";
                    else choice[j] += "Loss";
                  if (x[b][h] > -120) choice[j] += " in "+
                    (x[b][h]+121)+" 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] = 120 + (int)x[b][h];
              if (y[j][5] % 2 == 0)
                y[j][5] = y[j][5] - 244;
              else y[j][5] = 244 - 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");
          if ((b1 == 5 && b2 == 5 && b6 == 1) || (b6 == 5))
            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 < 1 || d > j) && (d != 88 ||
            b1 != 5 || b2 != 5 || b6 == 2 || b6 == 3 || b6 == 4) && (d != 77 || mv.prev == null));
          if (d == 77)
            {
              b = a; a = mv.z1;
              for (c = 0; c < b1; c++)
              for (d = 0; d < b2; 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[1][3][17]; b = s[7][21][23];
              if (b6 == 5) { a = s[2][15][19]; b = s[5][9][22]; }
              for (c = 0; c < b1; c++)
              for (d = 0; d < b2; 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 "+b1+
                  "-digit number for each row");
                System.out.println("0 = blank; 1 = 'x' (plays first); 2 = 'o'");
                for (e = 0; e < b1; e++)
                for (f = 0; f < b2; f++)
                  w[e][f] = 0;
                for (e = b2 - 1; e >= 0; e--)
                  {
                    f = lesInt();
                    for (g = b1 - 1; g >= 0; g--)
                      {
                        w[g][e] = f % 10;
                        f = f / 10;
                      }
                    for (f = 0; f < b1; f++)
                      if (w[f][e] == 2) w[f][e] = -1;
                  }
                h1 = 0; h2 = 0; h3 = 0;
                for (e = 0; e < b1; e++)
                for (f = 0; f < b2; f++)
                  {
                    if (w[e][f] == 0) h1++;
                    if (w[e][f] == 1) h2++;
                    if (w[e][f] == -1) h3++;
                  }
                if (h1 != b3 - 6) System.out.println
                  ("Error: "+h1+" blanks (should be "+(b3-6)+")");
                if (h2 != 3) System.out.println
                  ("Error: "+h2+" x's (should be 3)");
                if (h3 != 3) System.out.println
                  ("Error: "+h3+" o's (should be 3)");
              }
              while (h1 != b3 - 6 || h2 != 3 || h3 != 3);
              h1 = 0;
              while (w[h1 % b1][h1 / b1] <= 0) h1++;
              h2 = h1 + 1;
              while (w[h2 % b1][h2 / b1] <= 0) h2++;
              h3 = h2 + 1;
              while (w[h3 % b1][h3 / b1] <= 0) h3++;
              a = s[h1][h2][h3];
              h1 = 0;
              while (w[h1 % b1][h1 / b1] >= 0) h1++;
              h2 = h1 + 1;
              while (w[h2 % b1][h2 / b1] >= 0) h2++;
              h3 = h2 + 1;
              while (w[h3 % b1][h3 / b1] >= 0) h3++;
              b = s[h1][h2][h3];
              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 < b1; c++)
              for (d = 0; d < b2; 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 = b2 - 1; d >= 0; d--)
        {
          System.out.print((d+1)+"|");
          for (c = 0; c < b1; c++)
            System.out.print(" "+piece[1+w[c][d]]+" |");
          System.out.println(stripe);
        }
      for (c = 0; c < b1; c++) System.out.print("   "+letter[c]);
      System.out.println("");
      System.out.println("\nGAME OVER\n");
   }
}