#ifndef _HAMWAY_
#define _HAMWAY_

#include <vector>
#include <iostream>
#include <cassert>
#include <cmath>
#include <algorithm>

using namespace std;


class HamiltonWayMaker{
public:
  static void check(vector< pair<int,int> >,int,int,int,int);
  static vector< pair<int,int> > makeWay(int,int,int,int,bool rev = false);
};

void HamiltonWayMaker::check(vector< pair<int,int> > v,int n,int m,int x,int y){
#define ensure(Expr) if (!(Expr)) { \
                              cerr << n <<" "<<m<<" "<<x<<" "<<y<<endl;\
                              cerr << "[ ";\
                              for (int i = 0; i < (int)v.size(); i++)\
                                 cerr <<"("<<v[i].first <<" "<<v[i].second <<") ";\
                              cerr << "]"<<endl;\
                              cerr << "Condition " << #Expr << " failed"<<endl; \
                              exit(1);\
                            }

    if (n > 1 && m > 1)
        ensure((int)v.size() == n*m);
    ensure(v[0] == make_pair(x,y));

    for (int i = 0; i < (int)v.size(); i++)
        ensure(0 <= v[i].first && v[i].first < n && 0 <= v[i].second && v[i].second < m);

    for (int i = 1; i < (int)v.size(); i++){
        ensure(abs(v[i].first - v[i-1].first) <= 1);
        ensure(abs(v[i].second - v[i-1].second) <= 1);
    }

    if (n > 1 && m > 1){
        sort(v.begin(),v.end());
        ensure(unique(v.begin(),v.end()) == v.end());
    }

#undef ensure 
}

vector< pair<int,int> > HamiltonWayMaker::makeWay(int n,int m,int x,int y,bool rev){

    if (m == 1 && n != 1){
      vector<pair<int,int> > result = HamiltonWayMaker::makeWay(m,n,y,x);
      for (int i = 0; i < (int)result.size(); i++)
        swap(result[i].first,result[i].second);
      #ifdef HAMDEBUG
        check(result,n,m,x,y);
      #endif   
      return result;        
    }

    if (n == 1){
        vector<pair<int,int> > result;
        if (y < n-y-1){
            for (int i = y; i > 0; i--)
                result.push_back(make_pair(0,i));
            for (int i = 0; i < m; i++)
                result.push_back(make_pair(0,i));
        }
        else {
            for (int i = y; i < m-1; i++)
                result.push_back(make_pair(0,i));
            for (int i = m-1; i >=0; i--)
                result.push_back(make_pair(0,i));
        }
        #ifdef HAMDEBUG
            check(result,n,m,x,y);
        #endif
        return result;
    }

    if (x == 0 || rev){
      vector<pair<int,int> > result = HamiltonWayMaker::makeWay(n,m,n-x-1,y);
      for (int i = 0; i < (int)result.size(); i++)
        result[i].first = n - result[i].first - 1;
      #ifdef HAMDEBUG
        check(result,n,m,x,y);
      #endif   
      return result;
    }

    if (y == 0){
      vector<pair<int,int> > result = HamiltonWayMaker::makeWay(n,m,x,m-y-1);
      for (int i = 0; i < (int)result.size(); i++)
        result[i].second = m - result[i].second - 1;
      #ifdef HAMDEBUG
        check(result,n,m,x,y);
      #endif   
      return result;
    }

    
    vector< pair<int,int> > result;

    for (int i = y; i < m; i++)
        result.push_back(make_pair(x,i));

    int i,j;

    for (i = x-1; i > 1; i--){        
        for (j = m-1; j >= y; j--)
            result.push_back(make_pair(i,j));

        i--;

        for ( j = y; j < m; j++)
            result.push_back(make_pair(i,j));
    }

    if (i == 0){        
        for ( j = m-1; j >= y; j--)
            result.push_back(make_pair(0,j));
    }
    else {
        for ( j = m-1; j >= y; j--){
            result.push_back(make_pair(1,j));
            result.push_back(make_pair(0,j));
        }
    }

    for (j = y-1; j > 1; j--){
        for (i = 0; i <= x; i++)
            result.push_back(make_pair(i,j));
        j--;
        for (i = x; i >= 0; i--)
            result.push_back(make_pair(i,j));
    }

    if (j == 0){        
        for ( i = 0; i <= x; i++)
            result.push_back(make_pair(i,0));
    }
    else {
        for ( i = 0; i <= x; i++){
            result.push_back(make_pair(i,1));
            result.push_back(make_pair(i,0));
        }
    }

    
    for (i = x+1; i < n; i++){
        if ((x-i) & 1){
            for (j = 0; j < m; j++)
                result.push_back(make_pair(i,j));
        }
        else {
            for (j = m-1; j >= 0; j--)
                result.push_back(make_pair(i,j));
        }
    }

    #ifdef HAMDEBUG
        check(result,n,m,x,y);
    #endif
    return result;
}

#endif
