{ Petr Hruska }
{$R+}
Uses Ulice; { vstupni data }

Const MaxBarev = Sirka;
Type TBarva = -1 .. MaxBarev;
     TObarveni = Array[1 .. Sirka] Of TBarva;
Const Zelena : TBarva = 0;
      Prekazka : TBarva = -1;

Var R : t_rada;
    P : TObarveni;
{ Sklad barev, obsahuje nepouzite barvy }
Sklad : Record
          B : Array[1 .. MaxBarev] Of TBarva;
          Pocet : Integer;
        End;

{ Pocet pouziti dane barvy }
Pouziti : Array[TBarva] Of Integer;

Procedure Konec(Vysledek : Boolean);
Var F : Text;
Begin
  Assign(F, 'VYSTUP.TXT');
  Rewrite(F);
  If Vysledek Then Writeln(F, 'A') Else Writeln(F, 'N');
  Close(F);
  Halt;
End;

{ predpoklada, ze barva neni ve skladu }
Procedure Uskladni(B : TBarva);
Begin
  Inc(Sklad.Pocet);
  Sklad.B[Sklad.Pocet] := B;
End;

Procedure ZvysPouziti(B : TBarva);
Begin
  Inc(Pouziti[B]);
End;


{ Odebere barvu ze skladu a zvysi jeji pouziti o 1,
  predpoklada neprazdny sklad. }
Function Vyskladni : TBarva;
Var B : TBarva;
Begin
  B := Sklad.B[Sklad.Pocet];
  Dec(Sklad.Pocet);
  ZvysPouziti(B);
  Vyskladni := B;
End;

{ Naplni sklad barvani s kladnymi hodnotami tak,
  aby sly ven napred nejmensi cisla. }
Procedure NaplnSklad;
Var I : Integer;
Begin
  Sklad.Pocet := 0;
  For I := MaxBarev DownTo 1 Do Uskladni(I);
End;

Procedure SnizPouziti(B : TBarva);
Begin
  Dec(Pouziti[B]);
  If Pouziti[B] = 0 Then
    Begin
      If B = Zelena Then Konec(False);
      Uskladni(B);
    End;
End;

Function PocetPouziti(B : TBarva) : Integer;
Begin
  PocetPouziti := Pouziti[B];
End;

Procedure VynulujPouziti;
Var I : Integer;
Begin
  For I := -1 To MaxBarev Do Pouziti[I] := 0;
End;

Procedure ObarviPocatek(Var P : TObarveni);
Var I : Integer;
Begin
  For I := 1 To Sirka Do P[I] := Zelena;
  Pouziti[Zelena] := Sirka;
End;

Procedure Prebarvi(Var P : TObarveni; Stara, Nova : Integer);
Var I : Integer;
Begin
  For I := 1 To Sirka Do If P[I] = Stara Then
    Begin
      P[I] := Nova;
      SnizPouziti(Stara);
      ZvysPouziti(Nova);
      If PocetPouziti(Stara) = 0 Then Break;
    End;
End;

Procedure Slij(Var P : TObarveni; A, B : Integer);
Begin
  If P[A] = Zelena Then
    Prebarvi(P, P[B], P[A])
  Else If P[B] = Zelena Then
    Prebarvi(P, P[A], P[B])
  Else If PocetPouziti(P[A]) < PocetPouziti(P[B]) Then
    Prebarvi(P, P[B], P[A])
  Else
    Prebarvi(P, P[A], P[B]);
End;

Procedure ObarviDalsi(Var R : t_rada; Var P : TObarveni);
Var I : Integer;
Begin
  { Mista, kde byly prekazky nejak obarvime }
  For I := 1 To Sirka Do
    If P[I] = Prekazka Then P[I] := Vyskladni;

  { Mista, kde jsou prekazky ted, oznacime jako prekazky }
  For I := 1 To Sirka Do
    If R[I] = '1' Then
      Begin
        SnizPouziti(P[I]);
        P[I] := Prekazka;
      End;

  { Slijeme barvy, ktere sousedi }
  For I := 1 To Sirka - 1 Do
    If (P[I] <> Prekazka) And (P[I+1] <> Prekazka) And (P[I] <> P[I+1]) Then
      Slij(P, I, I+1);
End;

Begin
  ulice_init;
  NaplnSklad;
  VynulujPouziti;

  { V obarveni P bude vzdy aktualni obarveni. }
  ObarviPocatek(P);
  Writeln;
  R := next;
  While R <> '' do
    Begin
      ObarviDalsi(R, P);
      R := next;
    End;

  ulice_done;
  Konec(True);
End.