class amaze{
 
  final char free=' ';
  final char wall='*';
  final char down='v';
  final char up='^';
  final char left='<';
  final char right='>';
  final char bad='X';
  final char happy='#';

  char [][] grid;

  String [] sgrid = { "   *   **    ",
                      " *   *    ** ",
                      "****** * * **",
                      "   *   * *   ",
                      " * ****   ** ",
                      "    *   *    ",
                      "**  *   *    ",
                      "        *    ",
                      " ********* **",
                      "    *        " };

  amaze() {
     // The grid is read as String in sgrid.
     // It can also be read from the input.
     // But to work on the grid it is easier to have as char:

     grid = new char[sgrid.length][sgrid[0].length()];
     for (int i=0;i<sgrid.length;++i) 
       for (int j=0;j<sgrid[0].length();++j) 
          grid[i][j]=sgrid[i].charAt(j);
  }
    
  public void setdown (int i, int j) {grid[i][j]=down;}
  public void setup   (int i, int j) {grid[i][j]=up;}
  public void setright(int i, int j) {grid[i][j]=right;}
  public void setleft (int i, int j) {grid[i][j]=left;}

  public void setbad  (int i, int j) {grid[i][j]=bad;}
  public void sethappy(int i, int j) {grid[i][j]=happy;}

  public boolean isFree(int i, int j ){ return grid[i][j]==free;}
  public boolean isEnd(int i, int j) {
       return (i == grid.length-1 && j == grid[0].length-1); }

    
  
  public void print_maze(){
        for (int i=0;i<grid.length;++i)  {
          for (int j=0;j<sgrid[0].length();++j) 
               System.out.print (grid[i][j]);
          System.out.println();
        }
  }

  public boolean solve(int row, int col){
      boolean done = false;
 
      if (valid(row,col) ) {
       if (isEnd(row,col) ){
            done = true; // solved!
            sethappy(row,col);
       }
       else {
              setbad(row,col);
              done = solve(row+1,col);
              if (done) setdown(row,col); 
              else {   
                 done = solve(row-1,col);
                 if (done) setup(row,col); 
                 else {
                   done = solve(row,col-1);
                   if (done)  setleft(row,col);
                   else {
                      done = solve(row,col+1);
                      if (done)  setright(row,col);
                   }
                 }
              }
            } 
     }     
     return done;
  }

private boolean valid (int r, int c){
      boolean res=false;
      if (r>=0 && r < grid.length &&
                c >=0 && c< grid[0].length)
        if (isFree(r,c)) res=true;
      return res;
  }
          
}

class Maze{

 
  public static void main (String [] args) {

  amaze labyrinth = new amaze();
  labyrinth.print_maze();
  if (!labyrinth.solve(0,0)) System.out.print("NOT ");
  System.out.println("SOLVED");
  labyrinth.print_maze();
 }
}