program ioi94day1prb2ver2(input, output, inp, out) ;
{ Tom Verhoeff, Eindhoven University of Technology }
{ On-the-fly computation of room areas and maximum room area }


{ General Section }

const
  Test = true ;

var 
  inp, out: text ;

procedure Init ;
  begin
  if Test then
    writeln('IOI''94 - Day 1 - Problem 2: The Castle') ;
  assign(inp, 'input.txt') ;
  reset(inp) ;
  assign(out, 'output.txt') ;
  rewrite(out) ;
  if Test then writeln('Initialized')
  end { Init } ;

procedure Fini ;
  begin
  close(inp) ;
  close(out)
  end { Fini } ;


{ Problem Specific Section }

const
  MaxM = 50 ;
  MaxN = 50 ;

type
  Row = 1..MaxM ;
  Column = 1..MaxN ;
  Direction = (west, north, east, south) ;
  Module = record
    wall: array [Direction] of boolean ;
    nr: integer ; { room number, -1 if unknown }
    end { Module } ;

var
  M: Row ;
  N: Column ;
  Map: array [Row, Column] of Module ;

procedure ReadInput ;
  { read M, N, and Map ; initialize room numbers to -1 }
  var r: Row ; c: Column ; w: integer ; d: Direction ;
  begin
  readln(inp, M, N) ;
  if Test then writeln('Number of rows is ', M:1, ', number of columns ', N:1) ;
  for r := 1 to M do begin
    for c := 1 to N do with Map[r, c] do begin
      read(inp, w) ; { w encodes the walls of module Map[r, c] }
      for d := west to south do begin
        wall[d] := odd(w) ;
        w := w div 2
        end { for d } ;
      nr := -1
      end { for c with Map } ;
    readln(inp)
    end { for r } ;
  if Test then writeln('Input read') ;
  end { ReadInput } ;

procedure WriteCastle ;
  { write Map to output }
  var r: Row ; c: Column ;
  begin
  for c := 1 to N do with Map[1, c] do
    if wall[north] then write(' _') else write('  ') ;
  writeln ;
  for r := 1 to M do begin
    for c := 1 to N do with Map[r, c] do begin
      if (c = 1) then if wall[west] then write('|') else write(' ') ;
      if wall[south] then write('_') else write(' ') ;
      if wall[east] then write('|') else write(' ')
      end { for c with Map } ;
    writeln
    end { for r }
  end { WriteCastle } ;

type
  RoomNumber = 0..MaxM*MaxN ;

var
  rooms: RoomNumber ; { number of rooms completely painted }
  area: array[RoomNumber] of integer ; { area[n] is area of room nr. n }
  maxarea: integer ; { maximum room area }

procedure PaintMap ;
  { paint the map }
  
  procedure PaintRoom(r: Row; c: Column) ;
    { if Map[r, c] is unpainted then paint it and all modules connected to it }
    begin
    with Map[r, c] do
      if nr = -1 then begin
        nr := rooms ; inc(area[rooms]) ;
        if not wall[west]  then PaintRoom(r, c-1) ;
        if not wall[north] then PaintRoom(r-1, c) ;
        if not wall[east]  then PaintRoom(r, c+1) ;
        if not wall[south] then PaintRoom(r+1, c)
        end { if }
    end { PaintRoom } ;

  var r: Row ; c: Column ;
  begin
  rooms := 0 ; maxarea := 0 ;
  for r := 1 to M do
    for c := 1 to N do
      if Map[r, c].nr = -1 then begin
        area[rooms] := 0 ;
        PaintRoom(r, c) ;
        if area[rooms] > maxarea then maxarea := area[rooms] ;
        rooms := succ(rooms)
        end { if }
  end { PaintMap } ;

procedure WriteColors ;  
  { write Map colors to output }
  var r: Row ; c: Column ;
  begin
  for r := 1 to M do begin
    for c := 1 to N do write(Map[r, c].nr:2) ;
    writeln
    end { for r }
  end { WriteColors } ;

var
  bestrow: Row ; bestcol: Column ; bestdir: Direction ;

procedure BestWall ;
  var r: Row ; c: Column ; maxp: integer ;

  procedure Update(k1, k2: RoomNumber; d: Direction) ;
    var p: integer ;
    begin
    if k1 = k2 then p := area[k1] else p := area[k1] + area[k2] ;
    if p > maxp then begin
      maxp := p ; bestrow := r ; bestcol := c ; bestdir := d
      end { if }
    end { Update } ;

  begin
  maxp := 0 ;
  for r := 1 to M do
    for c := 1 to N do with Map[r, c] do begin
      if (r <> M) and wall[south] then Update(nr, Map[r+1, c].nr, south) ;
      if (c <> N) and wall[east]  then Update(nr, Map[r, c+1].nr, east) ;
      end { for c with Map }
  end { BestWall } ;

procedure ComputeAnswer ;
  begin
  PaintMap ;
  if Test then WriteColors ;
  BestWall
  end { ComputeAnswer } ;

procedure WriteOutput ;
  begin
  if Test then begin
    writeln('Number of rooms = ', rooms:1) ;
    writeln('Maximum room area = ', maxarea:1) ;
    writeln('Best wall to remove = ', bestrow:1, ' ', bestcol:1, ' ', bestdir:1)
    end { if Test } ;
  writeln(out, rooms:1) ;
  writeln(out, maxarea:1) ;
  write(out, bestrow:1, ' ', bestcol:1, ' ') ;
  case bestdir of
    south: writeln(out, 'S') ;
    east: writeln(out, 'E') ;
    end { case }
  end { WriteOutput } ;

begin
Init ;
ReadInput ;
if Test then WriteCastle ;
ComputeAnswer ;
WriteOutput ;
Fini
end.