//----------------------------------------------------------------------
//	File:           garden.cpp
//	Programmer:     David Mount
//	Last modified:  Mar 2003
//	Description:    Pippin's garden problem (max empty square)
//----------------------------------------------------------------------
//	This program solves Pippin's garden problem in which we are
//	given as input an axis-aligned rectangle (Pippin's yard) and a
//	set of points in this rectangle (trees) and we are asked to
//	compute the largest square (the garden) contained within this
//	rectangle, such that none of the points are in the interior of
//	this square.  All inputs are in integer coordinates.
//----------------------------------------------------------------------

#include <stdlib.h>			// standard library
#include <iostream.h>		// input/ouput
#include <assert.h>			// assertion checking

// Uncomment the following lines if using APCS classes
// #include "apvector.h"
// #include "apmatrix.h"
// #include "apstack.h"
// #include "apqueue.h"

#include "apstring.cpp"

// using namespace std;			// make standard names available

const bool DEBUGGING = false;		// debug output flag

//----------------------------------------------------------------------
//  Point2D - a 2-dimensional point with integer coordinates
//----------------------------------------------------------------------

typedef int	Coord;				// coordinates are ints

enum Axis {X = 0, Y = 1};			// axis names

class Point2D {
private:
    Coord	c[2];				// coordinates
public:
    Point2D(Coord x = 0, Coord y = 0)		// constructor
    {  c[X] = x;  c[Y] = y;  }

    Coord& operator[](Axis i)			// index
    {  return c[i];  }
};

						// input operator
istream& operator>>(istream& in, Point2D& p)
{  return in >> p[X] >> p[Y];  }

						// output operator
ostream& operator<<(ostream& out, Point2D& p)
{  return out << p[X] << " " << p[Y];  }

//----------------------------------------------------------------------
//  Rect2D - a 2-dimensional rectangle
//----------------------------------------------------------------------

class Rect2D {
    Point2D	lo;				// lower left point
    Point2D	hi;				// upper right point
public:
    						// constructor from points
    Rect2D(Point2D l=Point2D(), Point2D h=Point2D())
    {  lo = l;  hi = h;  }
    						// constructor from sides
    Rect2D(Coord l, Coord r, Coord b, Coord t)
    {  lo = Point2D(l,b);  hi = Point2D(r,t);  }

    Point2D& lowLeft() { return lo; }		// access lower left
    Point2D& upRight() { return hi; }		// access upper right
    Coord& left()   { return lo[X]; }		// access sides
    Coord& right()  { return hi[X]; }
    Coord& bottom() { return lo[Y]; }
    Coord& top()    { return hi[Y]; }
    Coord width()				// width
    {  return hi[X] - lo[X];  }
    Coord height()				// height
    {  return hi[Y] - lo[Y];  }
    bool properlyContains(Point2D p)		// does rect contain p?
    {  return ( p[X] > lo[X] && p[Y] > lo[Y] &&
		p[X] < hi[X] && p[Y] < hi[Y]);
    }
    bool contains(Point2D p)			// does rect contain p?
    {  return ( p[X] >= lo[X] && p[Y] >= lo[Y] &&
		p[X] <= hi[X] && p[Y] <= hi[Y]);
    }
    bool contains(Rect2D r)			// does rect contain r?
    {  return ( r.lo[X] >= lo[X] && r.lo[Y] >= lo[Y] &&
		r.hi[X] <= hi[X] && r.hi[Y] <= hi[Y]);
    }
};

						// input operator
istream& operator>>(istream& in, Rect2D& r)
{  return cin >> r.left() >> r.right() >> r.bottom() >> r.top();  }

						// output operator
ostream& operator<<(ostream& out, Rect2D& r)
{
    return out	<< r.left()   << " "
		<< r.right()  << " "
		<< r.bottom() << " "
		<< r.top();
}

//----------------------------------------------------------------------
//  findGarden - returns the maximum garden (square) in a rectangle
//  	The algorithm is a very simple (and stupid) brute force search.
//  	It enumerates all possible lower left corners, and for each it
//  	computes the largest empty square by repeatedly attempting to
//  	enlarge the current square by one more unit of width and testing
//  	whether any points fall within this square.  The arguments
//  	consist of
//
//	outer - the outer rectangle
//	nPts - the number of points
//	pts - the points to be avoided
//
//	The program stores the largest rectangle seen so far in
//	"largest", which is returned in the end.
//----------------------------------------------------------------------

Rect2D findGarden(Rect2D outer, int nPts, Point2D pts[]) {
    Rect2D largest(0, 0, 0, 0);			// largest rectangle
    for (Coord x = outer.left(); x < outer.right(); x++) {
	for (Coord y = outer.bottom(); y < outer.top(); y++) {
	    Coord w = 0;			// width of square
	    bool isOkay = true;			// is the test square okay?
	    while (isOkay) {
		int ww = w + 1;			// next width to test
						// square to be tested
		Rect2D testSq = Rect2D(x, x+ww, y, y+ww);
						// must be inside outer
		if (!outer.contains(testSq)) isOkay = false;
		for (int i = 0; i < nPts && isOkay; i++) {
		    if (testSq.properlyContains(pts[i]))
			isOkay = false;		// ith point is inside square
		}
		if (isOkay) w = ww;		// update width if okay
	    }
	    if (w > largest.width()) {		// new largest square?
		largest = Rect2D(x, x+w, y, y+w);
	    }
	    if (DEBUGGING) {			// for debugging only
		cout << "  Testing: " << x << " " << y << " " << w << endl;
	    	if (w == largest.width()) {
		    Rect2D curr(x, x+w, y, y+w);
		    cout << "New or tied for largest = " << curr
			 << " width = " << w << endl;
		}
	    }
	}
    }
    return largest;				// return largest square
}

//----------------------------------------------------------------------
//  Main program
//  	Inputs outer rectangle and points and calls findGarden() to
//  	compute the garden.
//----------------------------------------------------------------------

int main() {
    const int MAX_PTS = 10000;			// maximum number of points
    int nPts;
    Point2D pts[MAX_PTS];			// array of points
    Coord outerWidth, outerHeight;		// outer rectangle size
    cin >> outerWidth >> outerHeight;
    Rect2D outer(0, outerWidth, 0, outerHeight);// outer rectangle
    cin >> nPts;				// input number of points
    assert(nPts <= MAX_PTS);
    for (int i = 0; i < nPts; i++) {		// input the points
	cin >> pts[i];
	assert(outer.contains(pts[i]));		// check pts[i] is in bounds
    }
    						// find garden square
    Rect2D square = findGarden(outer, nPts, pts);
    cout << square << endl;			// output final square
    return EXIT_SUCCESS;
}