import java.io.*;

//-----------------------------------------------------
// Klasse DistanzSpiel / Hauptprogramm
//-----------------------------------------------------
public class DistanzSpiel {

// Attribute
  DistanzSpieler spielerWeiss, spielerSchwarz;
  DistanzBrett brett;
  DistanzRegeln regeln;

// Methoden
 
  // Konstruktor (Initialisierung eines Spiels)
  public DistanzSpiel(DistanzSpieler a, 
                      DistanzSpieler b, 
                      DistanzBrett brett, 
                      DistanzRegeln regeln
                     ) 
  {
    this.spielerWeiss = a; 
    this.spielerSchwarz = b;
    this.brett = brett; 
    this.regeln = regeln;
  }

  // Durchfuehrung eines Spiels
  public void spielen() {
    // Spieler Weiss beginnt
    DistanzSpieler aktSpieler = this.spielerWeiss;
    DistanzSpielzug zug = null;
    this.brett.gebeSpielbrettAus();
 
    // abwechselndes Ziehen bis Spielende erreicht ist
    do {
      if (aktSpieler == this.spielerWeiss) 
        System.out.println("Spieler Weiss ist am Zug!");
      else 
        System.out.println("Spieler Schwarz ist am Zug!");

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

  // Hauptprogramm; 
  // hier startet das Distanz-Programm
  public static void main(String[] args) {
    DistanzSpieler weiss = 
      new DistanzSpieler(DistanzFigur.WEISS);
    DistanzSpieler schwarz = 
      new DistanzSpieler(DistanzFigur.SCHWARZ);
    DistanzBrett brett = new DistanzBrett();
    DistanzRegeln regeln = 
      new DistanzRegeln(brett, weiss, schwarz);

    DistanzSpiel parob = 
      new DistanzSpiel(weiss,schwarz,brett,regeln);
    parob.spielen();
  }
}

//-----------------------------------------------------
// Klasse DistanzBrett
//-----------------------------------------------------
class DistanzBrett {

/*
gewaehlte Datenstruktur:

   0 1 2 3 4 5 6 7
  +-+-+-+-+-+-+-+-+
0 | |h|k| |h|h| | |
  +-+-+-+-+-+-+-+-+
1 | | | | | | | | |
  +-+-+-+-+-+-+-+-+
2 | | | | | | | | |
  +-+-+-+-+-+-+-+-+
3 | | | | | | | | |
  +-+-+-+-+-+-+-+-+
4 | | | | | | | | |
  +-+-+-+-+-+-+-+-+
5 | | | | | | | | |
  +-+-+-+-+-+-+-+-+
6 | | | | | | | | |
  +-+-+-+-+-+-+-+-+
7 | | |H|H| |K|H| |
  +-+-+-+-+-+-+-+-+

repraesentiert als 8 x 8 - Matrix; 
Schwarze Spielfiguren:
  h = Helfer
  k = Koenig
  g = Gefangener

Weisse Spielfiguren:
  H = Helfer
  K = Koenig
  G = Gefangener
*/

// Konstanten
  public final static int GROESSE = 8;
  public final static int HELFER  = 3;

// Attribute
  DistanzFeld[][] brett;

// Methoden 
  // Konstruktor (Initialisierung des Distanz-Brettes)
  public DistanzBrett() { 
    this.brett = new DistanzFeld[GROESSE][GROESSE];
    for (int z=0; z<GROESSE; z++) 
      for (int s=0; s<GROESSE; s++) 
        this.brett[z][s] = new DistanzFeld(z, s);

    // mit schwarzen Figuren besetzte Felder
    this.brett[0][1] = new DistanzFeld(
      new DistanzFigur(DistanzFigur.SCHWARZ, 
                       DistanzFigur.HELFER_SCHWARZ), 0, 1);

    this.brett[0][2] = new DistanzFeld(
      new DistanzFigur(DistanzFigur.SCHWARZ, 
                       DistanzFigur.KOENIG_SCHWARZ), 0, 2);

    this.brett[0][4] = new DistanzFeld(
      new DistanzFigur(DistanzFigur.SCHWARZ, 
                       DistanzFigur.HELFER_SCHWARZ), 0, 4);

    this.brett[0][5] = new DistanzFeld(
      new DistanzFigur(DistanzFigur.SCHWARZ, 
                       DistanzFigur.HELFER_SCHWARZ), 0, 5);

    // mit weissen Figuren besetzte Felder
    this.brett[GROESSE-1][2] = new DistanzFeld(
      new DistanzFigur(DistanzFigur.WEISS, 
                       DistanzFigur.HELFER_WEISS), GROESSE-1, 2);

    this.brett[GROESSE-1][3] = new DistanzFeld(
      new DistanzFigur(DistanzFigur.WEISS, 
                       DistanzFigur.HELFER_WEISS), GROESSE-1, 3);

    this.brett[GROESSE-1][5] = new DistanzFeld(
      new DistanzFigur(DistanzFigur.WEISS, 
                       DistanzFigur.KOENIG_WEISS), GROESSE-1, 5);

    this.brett[GROESSE-1][6] = new DistanzFeld(
      new DistanzFigur(DistanzFigur.WEISS, 
                       DistanzFigur.HELFER_WEISS), GROESSE-1, 6);

  } 

  // Ausfuehrung eines Spielzugs auf dem Brett
  public void fuehreSpielzugAus(DistanzSpielzug zug) { 
    int vonZeile = zug.vonWo().liefereZeile();
    int vonSpalte = zug.vonWo().liefereSpalte();
    int nachZeile = zug.nachWohin().liefereZeile();
    int nachSpalte = zug.nachWohin().liefereSpalte();

    DistanzFigur vonFigur = this.brett[vonZeile][vonSpalte].liefereFigur();
    DistanzFigur nachFigur = this.brett[nachZeile][nachSpalte].liefereFigur();

    if (this.brett[nachZeile][nachSpalte].istLeer()) { // leeres Feld
      this.brett[vonZeile][vonSpalte].entferneFigur();
      this.brett[nachZeile][nachSpalte].setzeFigur(vonFigur);
      return;
    } 

    // Figurentausch
    this.brett[vonZeile][vonSpalte].entferneFigur();
    this.brett[nachZeile][nachSpalte].entferneFigur();
    this.brett[nachZeile][nachSpalte].setzeFigur(vonFigur);
    this.brett[vonZeile][vonSpalte].setzeFigur(nachFigur);

    if (vonFigur.istWeiss() && nachFigur.istWeiss() ||
         !vonFigur.istWeiss() && !nachFigur.istWeiss()) { // Befreiung
      if (vonFigur.istKoenig()) {
        nachFigur.befreiung();
      }
    } else { // Gefangennahme
      nachFigur.gefangennahme();  // egal, wenn schon gefangen war
    }
      
  } 

  // Ausgabe des aktuellen Spielbretts
  public void gebeSpielbrettAus() { 

    System.out.println();   
    System.out.println("  Spieler B (Schwarz)");
    System.out.println();   
    System.out.print("  ");
    for (int j=0; j<GROESSE; j++) {
      System.out.print(j); System.out.print(" ");
    }
    System.out.println();

    System.out.print("-");
    for (int j=0; j<GROESSE; j++)
      System.out.print("--");
    System.out.println();   

    for (int i=0; i<GROESSE; i++) {
      System.out.print(i);  
      System.out.print("|");
      for (int j=0; j<GROESSE; j++) {
        System.out.print(liefereZeichen(i, j));
        System.out.print("|");
      }  
      System.out.println();

      System.out.print("-");
      for (int j=0; j<GROESSE; j++)
        System.out.print("--");
      System.out.println();
    }
    System.out.println();
    System.out.println("  Spieler A (WEISS)");
    System.out.println();

  }

  // Lieferung der Figur an der Stelle pos
  public DistanzFeld liefereFeld(Position pos) { 
    return this.brett[pos.liefereZeile()][pos.liefereSpalte()];
  }

  // Lieferung der Figur an der Stelle z/s
  public DistanzFeld liefereFeld(int z, int s) { 
    return this.brett[z][s];
  }

  // Lieferung des Figurzeichens oder Leerzeichen, falls 
  // leeres Feld
  public char liefereZeichen(int z, int s) { 
    if (this.brett[z][s].istLeer()) {
     return ' ';
    } else {
     return this.brett[z][s].liefereFigur().liefereTyp();
    }
  }

  // liefert alle Figuren eines Spielers
  public DistanzFigur[] liefereFiguren(DistanzSpieler spieler) { 
    DistanzFigur[] figuren = new DistanzFigur[HELFER+1];
    int pos = 0;
    for (int z=0; z<GROESSE; z++) {
      for (int s=0; s<GROESSE; s++) {
        if (!this.brett[z][s].istLeer() &&
            this.brett[z][s].liefereFigur().istWeiss() ==
            spieler.istWeiss()) {
          figuren[pos++] = this.brett[z][s].liefereFigur();
        }
      }
    }
    return figuren;
  }

}

//-----------------------------------------------------
// Klasse DistanzFeld
//-----------------------------------------------------
class DistanzFeld {

  int zeile, spalte;
  DistanzFigur figur;

  public DistanzFeld(int zeile, int spalte) {
    // leeres Feld
    this.figur = null;
    this.zeile = zeile;
    this.spalte = spalte;
  }

  public DistanzFeld(DistanzFigur figur, int zeile, int spalte) {
    this.figur = figur;
    this.zeile = zeile;
    this.spalte = spalte;
    figur.neuesFeld(this);
  }

  public DistanzFigur liefereFigur() {
    return this.figur;
  }

  public int liefereZeile() {
    return this.zeile;
  }

  public int liefereSpalte() {
    return this.spalte;
  }

  public boolean istLeer() {
    return this.figur == null;
  }

  public DistanzFigur entferneFigur() {
    DistanzFigur fig = this.figur;
    this.figur = null;
    return fig;
  }

  public void setzeFigur(DistanzFigur figur) {
    this.figur = figur;
    figur.neuesFeld(this);
  }

}

//-----------------------------------------------------
// Klasse DistanzFigur
//-----------------------------------------------------
class DistanzFigur {

// Konstanten
  public final static boolean WEISS   = true;
  public final static boolean SCHWARZ = !WEISS;

  public final static char HELFER_WEISS     = 'H';
  public final static char KOENIG_WEISS     = 'K';
  public final static char GEFANGENER_WEISS = 'G';

  public final static char HELFER_SCHWARZ     = 'h';
  public final static char KOENIG_SCHWARZ     = 'k';
  public final static char GEFANGENER_SCHWARZ = 'g';


// Attribute
  boolean istWeiss;
  char typ;
  DistanzFeld feld;    
  boolean istGefangen;

// Methoden
  // Konstruktor (Initialisierung einer Figur)
  public DistanzFigur(boolean istWeiss,
                      char typ
                     ) 
  {
    this.istWeiss = istWeiss; 
    this.typ = typ; 
    this.istGefangen = false;
    // anschliessend wird direkt neuesFeld aufgerufen und damit this.feld 
    //   initialisiert
  }

  public boolean istWeiss() { 
    return this.istWeiss; 
  }

  public int liefereZeile() { 
    return this.feld.liefereZeile(); 
  }

  public int liefereSpalte() { 
    return this.feld.liefereSpalte(); 
  }

  public char liefereTyp() { 
    if (!this.istGefangen) {
      return this.typ; 
    } else {
      if (this.istWeiss) return GEFANGENER_WEISS;
      return GEFANGENER_SCHWARZ;
    }
  }

  public DistanzFeld liefereFeld() { 
    return this.feld; 
  }

  public void neuesFeld(DistanzFeld feld) { 
    this.feld = feld; 
  }

  public boolean istGefangen() { 
    return this.istGefangen; 
  }

  public boolean istKoenig() { 
    return this.typ == KOENIG_SCHWARZ || this.typ == KOENIG_WEISS; 
  }

  public boolean istHelfer() { 
    return this.typ == HELFER_SCHWARZ || this.typ == HELFER_WEISS; 
  }

  public void gefangennahme() { 
    this.istGefangen = true; 
  }

  public void befreiung() { 
    this.istGefangen = false; 
  }


}

//-----------------------------------------------------
// Klasse Position
//-----------------------------------------------------

class Position {

// Attribute
  int zeile;
  int spalte;

// Methoden
  // Konstruktor (Initialisierung)
  public Position(int z, int s) {
    this.zeile = z;
    this.spalte = s;
  }

  public int liefereZeile() {
    return this.zeile;
  }

  public int liefereSpalte() {
    return this.spalte;
  }

  public boolean identisch(Position andere) {
    return this.zeile == andere.zeile && this.spalte == andere.spalte;
  }

}

//-----------------------------------------------------
// Klasse DistanzSpielzug
//-----------------------------------------------------

class DistanzSpielzug {

// Attribute
  Position von; 
  Position nach;
 
// Methoden
  // Konstruktor (Initialisierung eines Spielzugs)
  public DistanzSpielzug(Position von, Position nach) {
    this.von = von; 
    this.nach = nach;
  }

  // Konstruktor (Initialisierung eines Spielzugs)
  public DistanzSpielzug(int vonZeile, int vonSpalte,
                         int nachZeile, int nachSpalte
                        ) {
    this.von = new Position(vonZeile, vonSpalte); 
    this.nach = new Position(nachZeile, nachSpalte);
  }


  public Position vonWo() { 
    return this.von; 
  }

  public Position nachWohin() { 
    return this.nach; 
  }

}
 
//-----------------------------------------------------
// Klasse DistanzRegeln
//-----------------------------------------------------
class DistanzRegeln {

// Attribute
  DistanzBrett brett;
  DistanzSpieler weiss;
  DistanzSpieler schwarz;
  String sieger;

// Methoden
  // Konstruktor (Initialisierung der Regeln)
  public DistanzRegeln(DistanzBrett brett,
                       DistanzSpieler weiss,
                       DistanzSpieler schwarz
                      ) {
    this.brett = brett;
    this.weiss = weiss;
    this.schwarz = schwarz;
    this.sieger = null;
  }

  // Ueberpruefung eines Spielzugs
  public boolean spielzugOK(DistanzSpielzug zug, 
                            DistanzSpieler spieler
                           ) 
  {
    // korrekte Felder?
    if (zug.vonWo().liefereZeile() < 0 || 
        zug.vonWo().liefereSpalte() < 0 ||
        zug.vonWo().liefereZeile() >= DistanzBrett.GROESSE || 
        zug.vonWo().liefereSpalte() >= DistanzBrett.GROESSE ||
        zug.nachWohin().liefereZeile() < 0 || 
        zug.nachWohin().liefereSpalte() < 0 ||
        zug.nachWohin().liefereZeile() >= DistanzBrett.GROESSE || 
        zug.nachWohin().liefereSpalte() >= DistanzBrett.GROESSE) {
      return false;
    }

    // Figur darf nicht stehenbleiben !
    if (zug.vonWo().identisch(zug.nachWohin())) {
      return false;
    }

    // steht auf dem angegebenen Feld eine korrekte Figur ?
    DistanzFeld vonFeld = this.brett.liefereFeld(zug.vonWo());
    if (vonFeld.istLeer() ||
        (spieler.istWeiss() !=
         vonFeld.liefereFigur().istWeiss())
       ) {
      return false;
    }

    // Gefangene koennen nicht verschoben werden
    if (vonFeld.liefereFigur().istGefangen()) {
      return false;
    }

    // stimmt die Distanz ?
    int zeilenDistanz = abs(zug.vonWo().liefereZeile() - 
                            zug.nachWohin().liefereZeile());
    int spaltenDistanz = abs(zug.vonWo().liefereSpalte() - 
                             zug.nachWohin().liefereSpalte());
    DistanzFigur[] figuren = this.brett.liefereFiguren(spieler);
    boolean distanzOk = false;
    distanzUeberpruefung:
    for (int erste=0; erste<figuren.length; erste++) {
      for (int zweite=erste+1; zweite<figuren.length; zweite++) {
        if (figuren[erste] != this.brett.liefereFeld(zug.vonWo()).liefereFigur() &&
            figuren[zweite] != this.brett.liefereFeld(zug.vonWo()).liefereFigur()) {
          int zD = abs(figuren[erste].liefereFeld().liefereZeile() -
                       figuren[zweite].liefereFeld().liefereZeile());
          int sD = abs(figuren[erste].liefereFeld().liefereSpalte() -
                       figuren[zweite].liefereFeld().liefereSpalte());
          if (zeilenDistanz == zD && spaltenDistanz == sD ||
              zeilenDistanz == sD && spaltenDistanz == zD
             ) {
            distanzOk = true;
            break distanzUeberpruefung;
          }
        }
      }
    }
    if (!distanzOk) {
      return false;
    }

    // alles ok!
    return true;
  }

  // Ueberpruefung des Spielendes; Uebergeben wird der Spieler, der als naechstes
  // am Zug ist
  public boolean spielEnde(DistanzSpieler spieler) {
    // das spiel ist beendet, wenn (1) beim vorangehenden Zug der Koenig des
    // Spielers gefangen genommen wurde  oder
    // (2) wenn der aktuelle Spieler keinen gueltigen Zug mehr ausfuehren kann;
    // in beiden Faellen ist der andere Spieler Sieger

    DistanzFigur[] figuren = this.brett.liefereFiguren(spieler);

    // zunaechst (1) ueberpruefen
    for (int zaehler=0; zaehler<figuren.length; zaehler++) {
      if (figuren[zaehler].istKoenig() && figuren[zaehler].istGefangen()) {
        if (spieler == this.weiss) {
          this.sieger = "Koenig gefangen! Sieger ist Spieler B (SCHWARZ)";
        } else {
          this.sieger = "Koenig gefangen! Sieger ist Spieler A (WEISS)";
        }
        return true;
      }
    }

    // dann (2) ueberpruefen; einfach alle ueberhaupt  moeglichen Zuege ueberpruefen
    for (int zugFigur=0; zugFigur<figuren.length; zugFigur++) {
      for (int erste=0; erste<figuren.length; erste++) {
        for (int zweite=erste+1; zweite<figuren.length; zweite++) {
          if (figuren[erste] != figuren[zugFigur] &&
              figuren[zweite] != figuren[zugFigur]) {
            int zD = abs(figuren[erste].liefereFeld().liefereZeile() -
                         figuren[zweite].liefereFeld().liefereZeile());
            int sD = abs(figuren[erste].liefereFeld().liefereSpalte() -
                         figuren[zweite].liefereFeld().liefereSpalte());

            int zeile = figuren[zugFigur].liefereZeile();
            int spalte = figuren[zugFigur].liefereSpalte();

            if (spielzugOK(new DistanzSpielzug(zeile, spalte, zeile+zD, zeile+sD),
                           spieler) ||
                spielzugOK(new DistanzSpielzug(zeile, spalte, zeile+zD, zeile-sD),
                           spieler) ||
                spielzugOK(new DistanzSpielzug(zeile, spalte, zeile-zD, zeile+sD),
                           spieler) ||
                spielzugOK(new DistanzSpielzug(zeile, spalte, zeile-zD, zeile-sD),
                           spieler) ||
                spielzugOK(new DistanzSpielzug(zeile, spalte, zeile+sD, zeile+zD),
                           spieler) ||
                spielzugOK(new DistanzSpielzug(zeile, spalte, zeile+sD, zeile-zD),
                           spieler) ||
                spielzugOK(new DistanzSpielzug(zeile, spalte, zeile-sD, zeile+zD),
                           spieler) ||
                spielzugOK(new DistanzSpielzug(zeile, spalte, zeile-sD, zeile-zD),
                           spieler)
               ) {
              return false;  // Moeglicher Zug wurde gefunden!
            }
          }
        }  
      }
    }
    // es gibt keinen moeglichen Zug mehr
    if (spieler == this.weiss) {
      this.sieger = "Koenig gefangen! Sieger ist Spieler B (SCHWARZ)";
    } else {
      this.sieger = "Koenig gefangen! Sieger ist Spieler A (WEISS)";
    }
    return true;
  }

  // Ausgabe des Siegers
  public void gebeSiegerBekannt() {
    System.out.println(this.sieger);
  }

  // berechnet den Betrag einer Zahl
  public static int abs(int zahl) {
    return zahl >= 0 ? zahl : -zahl;
  }

}


//-----------------------------------------------------
// Klasse DistanzSpieler
//-----------------------------------------------------

class DistanzSpieler {

// Attribute
  boolean istWeiss;

// Methoden 
  // Konstruktor (Initialisierung eines Spielers)
  public DistanzSpieler(boolean istWeiss) {
    this.istWeiss = istWeiss;
  }

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

  // erfragt und liefert naechsten Spielzug des 
  // Spielers; uebergeben wird der letzte Zug des
  // Gegners
  public DistanzSpielzug 
   liefereNaechstenSpielzug (DistanzSpielzug gegnerZug) 
  { 
    return this.erfrageNaechstenSpielzugBeimSpieler(); 
  } 
 
  // erfragt naechsten Spielzug beim Spieler
  public 
   DistanzSpielzug erfrageNaechstenSpielzugBeimSpieler() 
  {
    System.out.println("von Zeile (0-" + (DistanzBrett.GROESSE-1) + "): ");
    int vonZeile = this.readInt();
    System.out.println("von Spalte (0-" + (DistanzBrett.GROESSE-1) + "): ");
    int vonSpalte = this.readInt();
    System.out.println("nach Zeile (0-" + (DistanzBrett.GROESSE-1) + "): ");
    int nachZeile = this.readInt();
    System.out.println("nach Spalte (0-" + (DistanzBrett.GROESSE-1) + "): ");
    int nachSpalte = this.readInt();
    return new DistanzSpielzug(vonZeile, vonSpalte, nachZeile, nachSpalte);
  }

  // Zahl einlesen
  public static int readInt() {
    try {
      BufferedReader input =
        new BufferedReader(new InputStreamReader(System.in));
      String eingabe = input.readLine();
      Integer stringToInt = new Integer(eingabe);
      return stringToInt.intValue();
    }
    catch (Exception e) {
      return 0;
    }
  }  

}