import java.io.*;

//-----------------------------------------------------
// Klasse GoBang-Spiel (GoBangSpiel) / Hauptprogramm
//-----------------------------------------------------
public class GoBangSpiel {

// Attribute
  protected GoBangSpieler spieler_a, spieler_b;
  protected GoBangBrett brett;
  protected GoBangRegeln regeln;

// Methoden
 
  // Konstruktor (Initialisierung eines Spiels)
  public GoBangSpiel(GoBangSpieler a, GoBangSpieler b, 
                     GoBangBrett brett, GoBangRegeln regeln) {
    this.spieler_a = a; this.spieler_b = b;
    this.brett = brett; this.regeln = regeln;
  }

  // Durchfuehrung eines Spiels
  public void spielen() {
    // Spieler A beginnt
    GoBangSpieler akt_spieler = this.spieler_a;
    GoBangSpielzug zug = null;
    this.brett.gebeSpielbrettAus();
 
 
    // abwechselndes Ziehen bis Spielende erreicht ist
    do {
      if (akt_spieler == this.spieler_a) 
        System.out.println("Spieler A ist am Zug!");
      else 
        System.out.println("Spieler B ist am Zug!");

      // legalen Spielzug ermitteln und ausfuehren
      zug = akt_spieler.liefereNaechstenSpielzug(zug);
      while (!this.regeln.spielzugOK(zug))
      {
        System.out.println("Ungueltig; neue Eingabe!");
        zug=akt_spieler.liefereNaechstenSpielzug(zug);
      }
      this.brett.fuehreSpielzugAus(zug);
      this.brett.gebeSpielbrettAus();
 
      // der andere Spieler ist nun ab Zug
      if (akt_spieler == spieler_a)
        akt_spieler = this.spieler_b;
      else
        akt_spieler = this.spieler_a;
    } while (!this.regeln.spielEnde());
 
    // Spiel ist zuende
    this.regeln.gebeSiegerBekannt();
  }

  // Hauptprogramm; 
  // hier startet das GoBang-Programm
  public static void main(String[] args) {
    GoBangSpieler a = 
      new GoBangSpieler(GoBangFigur.A_FIGUR);
    GoBangSpieler b = 
      new GoBangProgramm(GoBangFigur.B_FIGUR);
    GoBangBrett brett = new GoBangBrett();
    GoBangRegeln regeln = new GoBangRegeln(brett);

    GoBangSpiel gobang=new GoBangSpiel(a,b,brett,regeln);
    gobang.spielen();
  }
}

//-----------------------------------------------------
// Klasse GoBang-Brett (GoBangBrett)
//-----------------------------------------------------
class GoBangBrett {

// Attribute
  protected GoBangFigur[][] brett;

// Methoden 
  // Konstruktor (Initialisierung des GoBang-Brettes)
  public GoBangBrett() { 
    // anfangs ist das Spielbrett (8x8-Matrix) leer
    this.brett = new GoBangFigur[8][8];
    for (int i=0; i<8; i++) 
      for (int j=0; j<8; j++) 
        this.brett[i][j] = null;
   } 

  // Ausfuehrung eines Spielzugs auf dem Brett
  public void fuehreSpielzugAus(GoBangSpielzug zug) { 
    // abhaengig vom aktuellen Spieler, wird eine 
    // A_Figur oder eine B_Figur an die Stelle 
    //  gesetzt, die der Spielzug angibt
    int z = zug.welcheZeile();
    int s = zug.welcheSpalte();
    if (zug.vonSpielerA()) 
      this.brett[z][s] = 
        new GoBangFigur(GoBangFigur.A_FIGUR, z, s, this);
    else 
      this.brett[z][s] = 
        new GoBangFigur(GoBangFigur.B_FIGUR, z, s, this);
  } 

  // Ausgabe des aktuellen Spielbretts
  public void gebeSpielbrettAus() { 
    System.out.print("  ");
    for (int j=0; j<8; j++) {
      System.out.print(j); System.out.print(" ");
    }
    System.out.println();

    System.out.print("-");
    for (int j=0; j<8; j++) 
      System.out.print("--");
    System.out.println();
 
    for (int i=0; i<8; i++) {
      System.out.print(i);
      System.out.print("|");
      for (int j=0; j<8; j++) {
        if (this.brett[i][j] == null)
          System.out.print(" ");
        else if (this.brett[i][j].istAFigur()) 
          System.out.print("X");
        else 
          System.out.print("O");
        System.out.print("|");
      }  
      System.out.println();
 
      System.out.print("-");
      for (int j=0; j<8; j++) 
        System.out.print("--");
      System.out.println();
  } }


  // Lieferung der Figur an der Stelle z/s
  public GoBangFigur liefereFigur(int z, int s) { 
    if ((z >= 0) && (z < 8) &&
        (s >= 0) && (s < 8))
      return this.brett[z][s];
    return null;
  }
}

//-----------------------------------------------------
// Klasse GoBang-Figur (GoBangFigur)
//-----------------------------------------------------
class GoBangFigur {

// Konstanten
  public final static boolean A_FIGUR = true;
  public final static boolean B_FIGUR = !A_FIGUR;

// Attribute
  protected boolean a_oder_b;  // a == true
  protected int zeile;         // 0 - 7
  protected int spalte;        // 0 - 7
  protected GoBangBrett brett;

// Methoden
  // Konstruktor (Initialisierung einer Figur)
  public GoBangFigur(boolean a_oder_b,
                     int zeile, int spalte,
                     GoBangBrett brett) {
    this.a_oder_b = a_oder_b; this.brett = brett;
    this.zeile = zeile; this.spalte = spalte;
  }

  public boolean istAFigur() { return this.a_oder_b; }
  public int welcheZeile() { return this.zeile; }
  public int welcheSpalte() { return this.spalte; }

}

//-----------------------------------------------------
// Klasse GoBang-Spielzug (GoBangSpielzug)
//-----------------------------------------------------
class GoBangSpielzug {

// Attribute
  protected int zeile;  // 0 - 7
  protected int spalte; // 0 - 7
  protected boolean ist_spieler_a;
 
// Methoden
  // Konstruktor (Initialisierung eines Spielzugs)
  public GoBangSpielzug(int z, int s, boolean a) {
    this.zeile = z; 
    this.spalte = s;
    this.ist_spieler_a = a;
  }
  public int welcheZeile() { return this.zeile; }
  public int welcheSpalte() { return this.spalte; }
  public boolean vonSpielerA() { return this.ist_spieler_a; }
}
 
//-----------------------------------------------------
// Klasse GoBang-Regeln (GoBangRegeln)
//-----------------------------------------------------
class GoBangRegeln {

// Attribute
  protected GoBangBrett brett;

// Methoden
  // Konstruktor (Initialisierung der Regeln)
  public GoBangRegeln(GoBangBrett brett) {
    this.brett = brett;
  }

  // Ueberpruefung eines Spielzugs
  public boolean spielzugOK(GoBangSpielzug zug) {
    // ein Spielzug ist ok, wenn die Positionangaben 
    // im gueltigen Bereich liegen und 
    // das Feld noch nicht besetzt ist
    // entweder dies der erste Spielzug ist oder
    // ein Nachbarfeld durch eine Figur besetzt ist
    return
      (zug.welcheZeile() >= 0) && 
      (zug.welcheZeile() <= 7) &&
      (zug.welcheSpalte() >= 0) && 
      (zug.welcheSpalte() <= 7) &&
      (this.brett.liefereFigur(zug.welcheZeile(),
             zug.welcheSpalte()) == null) &&
      (this.istErsterSpielzug() ||
       this.existiertNachbar(zug.welcheZeile(),
             zug.welcheSpalte())
      );
  }

  // Ueberpruefung des Spielendes
  public boolean spielEnde() {
    // ein Spiel ist beendet, wenn alle Felder 
    // besetzt sind oder wenn ein Sieger feststeht
    int besetzte_felder = 0;
    for (int i=0; i<8; i++) 
      for (int j=0; j<8; j++) 
        if (this.brett.liefereFigur(i, j) != null) 
          besetzte_felder++;
    return (besetzte_felder == 8*8) || 
           (this.ermittleSieger() != ' ');
  }

  // Ausgabe des Siegers
  public void gebeSiegerBekannt() {
    char sieger = this.ermittleSieger();
    if (sieger == 'A') 
      System.out.println("Sieger ist Spieler A!");
    else if (sieger == 'B') 
      System.out.println("Sieger ist Spieler B!");
    else 
      System.out.println("Unentschieden!");
  }

  // Ueberpruefung ob erster Spielzug
  private boolean istErsterSpielzug() {
    for (int i=0; i<8; i++) 
      for (int j=0; j<8; j++) 
        if (this.brett.liefereFigur(i, j) != null) 
          return false;
    return true;
  }

  // Ueberpruefung ob Nachbar existiert
  private boolean existiertNachbar(int z, int s) {
    return 
      (this.brett.liefereFigur(z-1, s-1) != null) ||
      (this.brett.liefereFigur(z-1, s) != null) ||
      (this.brett.liefereFigur(z-1, s+1) != null) ||
      (this.brett.liefereFigur(z, s-1) != null) ||
      (this.brett.liefereFigur(z, s+1) != null) ||
      (this.brett.liefereFigur(z+1, s-1) != null) ||
      (this.brett.liefereFigur(z+1, s) != null) ||
      (this.brett.liefereFigur(z+1, s+1) != null);
  }

  // Ermittlung eines evtl. Siegers
  private char ermittleSieger() {
    for (int i=0; i<8; i++) {
      for (int j=0; j<8; j++) {
         char sieger = existiertFuenferReihe(i, j);
         if (sieger != ' ') {
           return sieger;
         }
      }
    }
    return ' '; // noch kein Sieger
  }

  // Ueberpruefung, ob 5er Reihe existiert
  private char existiertFuenferReihe(int z, int s) {
    GoBangFigur figur = this.brett.liefereFigur(z, s);
    if (figur == null) return ' ';
    int anzahl;
    GoBangFigur nachbar;

    // horizontale ueberpruefen
    anzahl = 1;
    nachbar = figur;
    for (int zaehler = 1; 
         (anzahl < 5) && (nachbar != null);
         zaehler++
        ) {
      nachbar = this.brett.liefereFigur(z, s+zaehler);
      if ((nachbar != null) && 
          (nachbar.istAFigur() == figur.istAFigur())
         ) {
        anzahl++;
      } else {
        break;
      }
    } 
    if (anzahl == 5) {
      if (figur.istAFigur()) return 'A';
      else return 'B';
    }

    // vertikale ueberpruefen
    anzahl = 1;
    nachbar = figur;
    for (int zaehler = 1; 
         (anzahl < 5) && (nachbar != null);
         zaehler++
        ) {
      nachbar = this.brett.liefereFigur(z+zaehler, s);
      if ((nachbar != null) && 
          (nachbar.istAFigur() == figur.istAFigur())
         ) {
        anzahl++;
      } else {
        break;
      }
    } 
    if (anzahl == 5) {
      if (figur.istAFigur()) return 'A';
      else return 'B';
    }

    // eine Diagonale ueberpruefen
    anzahl = 1;
    nachbar = figur;
    for (int zaehler = 1; 
         (anzahl < 5) && (nachbar != null);
         zaehler++
        ) {
      nachbar = this.brett.liefereFigur(z+zaehler, s+zaehler);
      if ((nachbar != null) && 
          (nachbar.istAFigur() == figur.istAFigur())
         ) {
        anzahl++;
      } else {
        break;
      }
    } 
    if (anzahl == 5) {
      if (figur.istAFigur()) return 'A';
      else return 'B';
    }

    // die andere Diagonale ueberpruefen
    anzahl = 1;
    nachbar = figur;
    for (int zaehler = 1; 
         (anzahl < 5) && (nachbar != null);
         zaehler++
        ) {
      nachbar = this.brett.liefereFigur(z+zaehler, s-zaehler);
      if ((nachbar != null) && 
          (nachbar.istAFigur() == figur.istAFigur())
         ) {
        anzahl++;
      } else {
        break;
      }
    } 
    if (anzahl == 5) {
      if (figur.istAFigur()) return 'A';
      else return 'B';
    }

    // es existiert keine 5er Reihe
    return ' ';
  }

}


//-----------------------------------------------------
// Klasse GoBang-Spieler (GoBangSpieler)
//-----------------------------------------------------

class GoBangSpieler {

// Attribute
  protected boolean ist_spieler_a;

// Methoden 
  // Konstruktor (Initialisierung eines Spielers)
  public GoBangSpieler(boolean a_oder_b) {
    this.ist_spieler_a = a_oder_b;
  }

  // Ueberpruefung, ob es Spieler A ist
  public boolean istSpielerA() { 
    return this.ist_spieler_a; 
  }

  // erfragt und liefert naechsten Spielzug des 
  // Spielers; uebergeben wird der letzte Zug des
  // Gegners
  public GoBangSpielzug 
   liefereNaechstenSpielzug (GoBangSpielzug gegner_zug) { 
    return this.erfrageNaechstenSpielzugBeimSpieler(); 
  } 
 
  // erfragt naechsten Spielzug beim Spieler
  protected 
   GoBangSpielzug erfrageNaechstenSpielzugBeimSpieler() {
    System.out.println("Zeile eingeben (0-7): ");
    int zeile = this.readInt();
    System.out.println("Spalte eingeben (0-7): ");
    int spalte = this.readInt();
    return new GoBangSpielzug(zeile, spalte, this.ist_spieler_a);
  }

  // Zahl einlesen
  private static int readInt() {
    DataInputStream input = 
      new DataInputStream(System.in);
    try {
      String eingabe = input.readLine();
      Integer i = new Integer(eingabe);
      return i.intValue();
   } catch (Exception e) { return -1; }
  }
}

//-----------------------------------------------------
// Klasse GoBang-Programm (GoBangProgramm)
//-----------------------------------------------------

class GoBangProgramm extends GoBangSpieler {

// Attribute
  protected GoBangBrett brett;
  protected GoBangRegeln regeln;

// Methoden
  // Konstruktor (Initialisierung eines Spielers)
  public GoBangProgramm(boolean a_oder_b) {
    super(a_oder_b);
    // auf einem eigenen Brett werden die Zuege nachgehalten
    this.brett = new GoBangBrett();
    this.regeln = new GoBangRegeln(this.brett);
  }

  // erfragt und liefert naechsten Spielzug des
  // Spielers; uebergeben wird der letzte Zug des
  // Gegners
  public GoBangSpielzug
   liefereNaechstenSpielzug(GoBangSpielzug gegner_zug) {
    if (gegner_zug != null)
      this.brett.fuehreSpielzugAus(gegner_zug);

    GoBangSpielzug eigener_zug = this.ermittleNaechstenSpielzug();
    this.brett.fuehreSpielzugAus(eigener_zug);
    return eigener_zug;
  }
   
  // berechnet naechsten Spielzug
  protected GoBangSpielzug ermittleNaechstenSpielzug() {
    for (int i=0; i<8; i++) {
      for (int j=0; j<8; j++) {
        GoBangSpielzug zug = new GoBangSpielzug(i, j, this.istSpielerA());
        if (this.regeln.spielzugOK(zug)) {
          return zug;
        }
      }  
    }  
    return null; // nicht moeglich
  }
   
}