#include 
#include 
#include 
#include 
#include    // useful assert macro for correctness
using namespace std;
class Maze{
 // Data members - private- not accessible outside
private:
int rows, cols;
bool** Vwall;
bool** Hwall;  // 2-d array for interior walls
bool ** Visited; // flag for each cell

public:
 //constructor- read in Maze data & initialize
 Maze(){
   int num;
   cin >> rows; cin >> cols;
   Vwall = new bool * [rows];  //  rows x cols-1  is size
   Hwall = new bool * [rows-1];  // (rows-1) x cols  is size
   Visited = new bool * [rows];  // rows x cols
   for( int i = 0 ; i < rows ; i++ )
            {Vwall[i] = new bool[cols-1];
             Visited[i] = new bool[cols];
             if (i < (rows-1)) Hwall[i] = new bool[cols];}
   for(int i = 0; i < rows ; i++){  // read in wall data
      for(int j = 0; j < (cols-1); j++){ // Vertical wall data
        cin >> num; 
        if (num == 0) Vwall[i][j] = false;
        else Vwall[i][j] = true;}
      if (i < (rows-1))  // Horizontal walls data
         for(int j = 0; j < cols; j++){
                 cin >> num; 
                 if (num == 0) Hwall[i][j] = false;
                 else Hwall[i][j] = true;}
     for (int j=0; j < cols; j++) Visited[i][j] = false;} // All free
  }

// destructor to free up the Vwall, Hwall space
~Maze(){
 for( int i = 0 ; i < rows ; i++ ) 
     {delete [] Vwall[i]; delete [] Visited[i];}
 for( int i = 0 ; i < (rows-1) ; i++ ) {delete [] Hwall[i];}   
 delete [] Vwall; delete [] Hwall; delete [] Visited;    
}

void showmaze(){
 for (int i = 0; i < cols; i++) {cout << " ..";}
 cout << endl;  // draw top border
 for (int i = 0; i < rows; i++) {
  cout << ":" ; // left outer wall
  for (int j = 0; j < (cols - 1); j++)
    {cout << "  ";
     if (Vwall[i][j]) cout << ":" ; else cout << " ";}
  cout << "  :" << endl; // right outer wall
  if (i < (rows - 1)) {for (int j = 0; j < cols; j++)
                 {if (Hwall[i][j]) cout << " .." ; else cout << "   ";}}
  else {for (int j = 0; j < cols; j++) cout << " ..";}
 cout << endl;}
}

bool canmove(int x, int y, int dir){
 switch(dir){
    case 1:  // move up
      {return ((x > 0) && !Hwall[x-1][y] && !Visited[x-1][y]);} 
    case 2:  // move right
      {return ((y < cols - 1) && !Vwall[x][y] && !Visited[x][y+1]);}
    case 3:  // move down
      {return ((x < rows - 1) && !Hwall[x][y] && !Visited[x+1][y]);}
    case 4:  // move left
      {return ((y > 0) && !Vwall[x][y-1] && !Visited[x][y-1]);}
}}              

 void solve(int x1, int y1, int x2, int y2){
   assert ((x1 <= rows - 1) && (y1 <= cols - 1));  // Sanity check
   assert ((x2 <= rows - 1) && (y2 <= cols - 1));  // for Rat & Cheese
 //  showmaze();
   stack Stck;
   int curX = x1; int curY = y1; int dir = 1; bool flag = false;
   do{
    while (dir < 4) {
     if ((curX == x2) && (curY == y2)) {flag = true;break;};
     if (canmove(curX,curY,dir)) {
       Visited[curX][curY] = true;
       Stck.push(curX); Stck.push(curY); Stck.push(dir); 
 //      cout << "Move from " << curX << "," << curY << " dir " << dir;
       switch(dir){
         case 1: {curX = curX - 1; break;}
         case 2: {curY = curY + 1; break;}
         case 3: {curX = curX + 1; break;}
         case 4: {curY = curY - 1;}}
       dir = 1;
//       cout << " to " << curX << "," << curY << endl;
        }
      else dir++;}
    if (flag || Stck.empty()) break;
    else { dir = Stck.top() + 1; Stck.pop();
           curY = Stck.top(); Stck.pop();
           curX = Stck.top(); Stck.pop(); }} while (true);
   if (flag) {while (!Stck.empty()){
                cout << setw(1) << Stck.top();
                Stck.pop(); Stck.pop(); Stck.pop();}
              cout << endl;}
   else {cout << "0" << endl;} // no path exists
}
};