#!/usr/bin/ruby

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

   # Breadth-first search
   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]]
         # Mark cell as visited
         b[[i, j]] = [u, v]

         # Record maximum distance away from starting point
         n = (i << 16) + j
         if d < n
            d = n
            q = [i, j]
         end

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

   # Draw path from furthest point to starting point
   while q != [0, 0]
      x[q[0]][q[1]] = '%'
      q = b[q]
   end
   x[0][0] = '%'

   # Output solution
   x.each{|l| puts l}
end