program minu__laukas;

  const PR = 'MINOS.DAT';
        RZ = 'MINOS.REZ';
        DYDIS = 75;  { maksimalus ‘aidimo laukas}
        { ažtuonios kryptys }
        const d: array [1..8] of record
                                   x, y: integer;
                                 end = ((x: -1; y: -1), (x: -1; y:  0),
                                        (x: -1; y:  1), (x:  0; y: -1),
                                        (x:  0; y:  1), (x:  1; y: -1),
                                        (x:  1; y:  0), (x:  1; y:  1));

  type laukas = array [1..DYDIS, 1..DYDIS] of char;
       sarasas = array [1..DYDIS*DYDIS] of record
                                             x, y : integer
                                           end;

  { ‘emiau apražyti globalieji kintamieji }
  var n: integer;  { lauko dydis }
      lau,         { ‘aidimo laukas }
      spr: laukas; { rastasis sprendinys }

      ilg: integer;      { tikrintin— langeli— s…ražo ilgis }
      tikrinti: sarasas; { tikrintin— langeli— s…ražas }

      sk: integer;       { nagrin‚jamos grup‚s langeli— s…ražo ilgis }
      grupe: sarasas;    { nagrin‚jama grup‚ }

  { --------------duomen— Ťvedimas bei ižvedimas-------------}
  procedure skaityti (var n: integer; var lau: laukas);
    var f: text;
        i, j : integer;
  begin
    assign (f, PR);
    reset (f);
    readln (f, n);
    for i := 1 to n do
      begin
        for j := 1 to n do
             read (f, lau[i, j]);
        readln (f)
      end;
    close( f );
  end; { skaityti }

  procedure spausdinti (n: integer; spr: laukas);
    var f: text;
        i, j: integer;
  begin
    assign (f, RZ);
    rewrite (f);
    for i := 1 to n do
      begin
        for j := 1 to n do
          write (f, spr[i, j]);
        writeln (f)
      end;
    close (f);
  end; { spausdinti }

  {---------------pagalbin‚s funkcijos ir proced–ros -----------}
  function lauke (x, y: integer): boolean;
  begin
    lauke := (x >= 1) and (x <= n) and (y >= 1) and (y <= n);
  end; { lauke }

  function minos (x, y: integer ): integer;
    { kiek min— supa langelŤ (x, y) }
    var i, sk: integer;
  begin
    sk := 0;
    for i := 1 to 8 do
      if lauke (x + d[i].x, y + d[i].y)
         then if lau[x + d[i].x, y + d[i].y] = 'M'
                 then sk := sk + 1;
    minos := sk
  end; { minos }

  function uzv (x, y: integer): integer;
    { kiek u‘vert— langeli— supa duot… langelŤ }
    var i, sk: integer;
  begin
    sk := 0;
    for i := 1 to 8 do
      if lauke (x + d[i].x, y + d[i].y)
         then if lau[x + d[i].x, y + d[i].y] = 'U'
                 then sk := sk + 1;
    uzv := sk
  end; { u‘v }

  function ska (c: char): integer;
    { simbolinŤ skai‡iaus u‘raž… paver‡ia skai‡iumi }
  begin
    ska := ord(c) - ord('0');
  end; { ska }

  {---------------langeli— atvertimas ------------------------}
  procedure keisti (x, y: integer; simb: char; var lau: laukas);
    { visus u‘vertus langelius esan‡ius apie langelŤ, kurio numeris
      s…raže "tikrinti" yra nr, pakei‡iame nurodytu simboliu }
    var i, xx, yy : integer;
  begin
    for i := 1 to 8 do
      begin
        xx := x + d[i].x; yy := y + d[i].y;
        if lauke (xx, yy) { jei neižeinama u‘ lauko rib— }
           then if lau[xx, yy] = 'U'
                   then lau[xx, yy] := simb;
     end;
  end; { keisti }

  procedure atversti (var ilg: integer; var tikrinti: sarasas;
                      var lau: laukas);
    { atver‡iami langeliai, kuriuos galima atversti be perrinkimo }
    var pirma, antra,
        keista: boolean;  { ar padaryti pakeitimai ‘aidimo lauke }
        i: integer;
  begin
    keista := true;
    while keista do    { iežkoti tol, kol buvo padaryta pakeitim— }
      begin
        keista := false;
        i := 1;
        while i <= ilg do
          with tikrinti[i] do
            begin
              { ar tenkinama pirma ar antra s…lygos }
              pirma := ska(lau[x, y]) = minos(x, y) + uzv(x, y);
              antra := ska(lau[x, y]) = minos (x, y);
              if pirma
                  then keisti (x, y, 'M', lau)  { pirma s…lyga }
                  else if antra
                          then keisti (x, y, 'L', lau); { antra s…lyga }
              if pirma or antra
                then begin
                       keista := true;
                       { iž s…ražo pažalinamas elementas i }
                       tikrinti[i] := tikrinti[ilg];
                       ilg := ilg - 1;
                     end
                else i := i + 1;
            end
      end;
  end; { atversti }

  procedure atnaujinti_spr (const lau: laukas; var spr: laukas);
    { atnaujinamas sprendinys, esantis lentel‚je "spr" }
    var i, j : integer;
  begin
    for i := 1 to n do
      for j := 1 to n do
        case spr[i, j] of
          'U': if lau[i, j] in ['M', 'L']
                  then spr[i, j] := lau[i, j];
          'M': if lau[i, j] <> 'M'        { langelyje gali b–ti mina, }
                  then spr[i, j] := 'N';  { bet gali jos ir }
          'L': if lau[i, j] <> 'L'        { neb–ti }
                  then spr[i, j] := 'N';
          'N', '0'..'9': ; { nekeisti nieko }
        end;
  end; { atnaujinti_spr }

  {------------------susijusi— langeli— grup‚s radimas ----------------}
  procedure grupuoti (var sk, ilg: integer; { rast—j— langeli— skai‡ius }
                      var grupe, tikrinti: sarasas);
    var i, j, k: integer;
    { iežkoma langeli—, susijusi— su paskutiniu s…ražo "tikrinti" langeliu;
      rastieji langeliai pažalinami iž s…ražo "tikrinti" }
  begin
    { iežkosime langeli—, susijusi— su paskutiniuoju s…ražo langeliu }
    sk := 1;
    grupe[sk] := tikrinti[ilg];
    ilg := ilg - 1; { paskutinysis langelis pažalinamas iž s…ražo }
    i := 1;
    while i <= sk do { ar s…ražo "visi" langelis }
      begin
        j := 1;
        while j <= ilg do { susijŠs su s…ražo "tikrinti" langeliu }
          begin
            if (abs (tikrinti[j].x - grupe[i].x) < 3) and { jei atstumas }
               (abs (tikrinti[j].y - grupe[i].y) < 3)     { tinkamas }
            then begin
                   sk := sk + 1;            { ŤražomŠ nauj… "susijusŤ" }
                   grupe[sk] := tikrinti[j]; { langelŤ Ť s…r…ž… "visi" }
                   tikrinti[j] := tikrinti[ilg]; { ir pažaliname iž s…ražo }
                   ilg := ilg - 1;               { "tikrinti" }
                   j := j - 1;
                 end;
             j := j + 1
          end;
         i := i + 1;
      end
  end; { grupuoti }

  {----------------------rekursin‚ sprendinio paiežka--------------}
  function gerai (x, y: integer): boolean;
    { k1 tik atvertas langelis (x, y); patikrinama, ar viskas gerai }
    var taip: boolean;
        i, xx, yy: integer;
  begin
    taip := true;
    for i := 1 to 8 do
      begin
        xx := x+d[i].x; yy := y+d[i].y;
        if lauke (xx, yy)
         then if lau[xx, yy] in ['0'..'9']
               then taip := taip and (minos(xx, yy) <= ska(lau[xx, yy])) and
                       (ska(lau[xx, yy]) <= minos(xx, yy) + uzv (xx, yy))
      end;
    gerai := taip;
  end; { gerai }

  procedure ieskoti (nr, kaim: integer);
   { d‚liojamos minos apie langelŤ, kurio numeris masyve "grup‚" yra nr }
    var x, y, xx, yy: integer;
  begin
   if nr > sk
     then atnaujinti_spr (lau, spr) { rastas sprendinys }
   else begin
          x := grupe[nr].x; y := grupe[nr].y;
          if uzv (x, y) = 0 { jei visi langeliai atverti }
             then ieskoti (nr+1, 1)
          else begin
                 xx := x + d[kaim].x; yy := y + d[kaim].y;
                 if lauke(xx, yy) then
                   if lau[xx, yy] = 'U' then
                    begin
                      { dedame min… }
                      lau[xx, yy] := 'M';
                      { patikriname, ar viskas gerai }
                      if gerai (xx, yy) then ieskoti (nr, kaim+1);
                      { nededame minos }
                      lau[xx, yy] := 'L';
                      if gerai (xx, yy) then ieskoti (nr, kaim+1);
                      { atstatome reikžmŠ }
                      lau[xx, yy] := 'U';
                    end
                   else ieskoti (nr, kaim+1) { jei ne u‘vertas langelis }
                 else ieskoti (nr, kaim+1); { jei u‘ lauko rib— }
               end;
        end;
  end; { iežkoti }


  procedure minu_laukas (var spr: laukas);
    var i, j: integer;
  begin
    { langelius su skai‡iais, Ťražome Ť masyv… "tikrinti" }
    ilg := 0;
    for i := 1 to n do
      for j := 1 to n do
        if lau[i, j] in ['0'..'9']
           then begin
                  ilg := ilg + 1;
                  with tikrinti[ilg] do
                     begin
                       x := i; y := j;
                     end;
                end;
    { atveriame langelius, kuriems nereikia perrinkimo }
    atversti (ilg, tikrinti, lau);
    { iežkosime sprendinio }
    spr := lau;
    while ilg <> 0 do { kol s…ražas "tikrinti" n‚ra tuž‡ias }
     begin
       grupuoti (sk, ilg, grupe, tikrinti);  { atskiriame grupŠ }
       ieskoti (1, 1);                       { ir iežkome sprendinio }
       lau := spr;
     end;
    { visi likŠ u‘verti langeliai - ne‘inomi }
    for i := 1 to n do
      for j := 1 to n do
        if spr[i, j] = 'U'
           then spr[i, j] := 'N';
  end; { min—_laukas }

begin
  skaityti (n, lau);
  minu_laukas (spr);
  spausdinti (n, spr);
end.