#include #include #include using namespace std; #define IMPORTANCE_BOUND 100 #define LEFT 0 #define RIGHT 1 class SquareLand { public: int left, bottom, length, importance; int getLeft() const { return left; } int getRight() const { return left+length; } int getBottom() const { return bottom; } int getTop() const { return bottom+length; } }; class Event { public: int kind, position, top, bottom; static Event makeLeft( int position, int top, int bottom ) { Event result; result.kind = LEFT; result.position = position; result.top = top; result.bottom = bottom; return result; } static Event makeRight( int position, int top, int bottom ) { Event result; result.kind = RIGHT; result.position = position; result.top = top; result.bottom = bottom; return result; } bool operator < ( const Event &e ) const { if ( position < e.position ) return true; if ( position > e.position ) return false; if ( kind > e.kind ) return true; if ( kind < e.kind ) return false; return (top < e.top); } }; bool overlap( int m1, int M1, int m2, int M2 ) { return ( m2 < M1 && m1 < M2 ); } bool canExpropriateSub( vector &E, const int top, const int bottom, int A ) { int lastEventPosition = 1; int nonlineSegment = 0; if ( bottom <= 0 ) return false; for ( int i = 0; i < E.size(); i++ ) { const int position = E[i].position; if ( !overlap(bottom, top, E[i].bottom, E[i].top) ) continue; if ( nonlineSegment == 0 && (position - lastEventPosition) >= A ) return true; if ( E[i].kind == LEFT ) nonlineSegment++; else nonlineSegment--; lastEventPosition = position; } return false; } bool canExpropriate( const vector &LD, const int L, const int A ) { vector E; for ( int i = 0; i < LD.size(); i++ ) E.push_back(Event::makeLeft(LD[i].getLeft(), LD[i].getTop(), LD[i].getBottom())), E.push_back(Event::makeRight(LD[i].getRight(), LD[i].getTop(), LD[i].getBottom())); // sentinel. E.push_back(Event::makeLeft(L+1, L+1, 1)); sort(E.begin(), E.end()); if ( canExpropriateSub(E, L+1, L+1-A, A) ) return true; for ( int i = 0; i < LD.size(); i++ ) if ( canExpropriateSub(E, LD[i].getBottom(), LD[i].getBottom()-A, A) ) return true; return false; } int main() { int L, A, nland; vector LD; cin >> L >> A >> nland; LD.resize(nland); for ( int i = 0; i < nland; i++ ) cin >> LD[i].importance >> LD[i].length >> LD[i].left >> LD[i].bottom; int bound = 1; while ( bound <= IMPORTANCE_BOUND ) { if ( canExpropriate(LD, L, A) ) break; bound = LD[0].importance; for ( int i = 1; i < LD.size(); i++ ) bound = min(bound, LD[i].importance); int cursor = 0; while ( cursor < LD.size() ) if ( LD[cursor].importance == bound ) LD[cursor] = LD.back(), LD.pop_back(); else cursor++; } if ( bound <= IMPORTANCE_BOUND ) cout << bound << endl; else cout << "IMPOSSIBLE" << endl; return 0; }