#!/usr/bin/ruby

if STDIN.tty?
   puts "Expecting maze on stdin"
else
   x = [];
   STDIN.each_line{|l| x.push(l)};

   b = {};
   d = 0;
   q = [0, 0];
   p = [[0, 0, 0, 0]];
   while p.size > 0;
      i, j, u, v = p.shift;
      if i >= 0 && i < x.size && j >= 0 && x[i][j] == 32.chr && !b[[i, j]];
         b[[i, j]] = [u, v];

         n = (i << 16) + j;
         if d < n;
            d = n;
            q = [i, j];
         end;

         [[-1, 0], [1, 0], [0, -1], [0, 1]].each{|m, n|
            p.push([i + m, j + n, i, j])
         };
      end;
   end;

   while q != [0, 0];
      x[q[0]][q[1]] = '%';
      q = b[q];
   end;
   x[0][0] = '%';

   x.each{|l| puts l};
end