/*
 *
 * Copyright (c) 2010 Krzysztof Wladyszewski, krzysiek@lodz.pl
 *
 * Permission to use, copy, modify, distribute and sell this source file
 * for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation. Krzysztof Wladyszewski makes no
 * representations about the suitability of this source file for any
 * purpose. It is provided "as is" without express or implied warranty.
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Range
{
public:
    Range() : a(0), b(1), valid(true) {}
    Range( int a , int b ) : valid(true) { set( a, b ); }
    Range( const Range & item ) : valid(true) { a = item.a; b = item.b; }
    
    void set( int a , int b )
    {
	this->a = min( a , b );
	this->b = max( a , b );
    }
    
    int left() const { return a; }
    int right() const { return b; }

    void combine( const Range & item )
    {
	a = min( a , item.a );
	b = max( b , item.b );
    }
    
    void adjustLeftSide( const Range & item )	{ a = max( a , item.a ); }
    void adjustRightSide( const Range & item )	{ b = min( b , item.b ); }
    
    void invalidate() { valid=false; }
    bool isValid() const { return valid; }
    
    bool overlaps( const Range & item ) const { return !(item.b < a || b < item.a); }
    bool isBelow( const Range & item ) const { return item.b < a; }
    bool isAbove( const Range & item ) const { return item.a > b; }

    Range & operator=( const Range & item ) { a = item.a; b = item.b; return *this; }

private:
    int a,b;
    bool valid;

    inline friend bool operator==( const Range & x , const Range & y )
    { return x.a == y.a && x.b == y.b; }

    inline friend bool operator!=( const Range & x , const Range & y )
    { return !(x==y); }

    inline friend bool operator<( const Range & x , const Range & y )
    { return x.a < y.a; }

    inline friend ostream & operator<<( ostream & o , const Range & item )
    { o << "(" << item.a << "," << item.b << ")" << endl; }
};

inline bool isRangeInvalid( const Range & item )
{
    return !item.isValid();
}

inline bool isRangeBelow( const Range & x , const Range & y )
{
    return y.isBelow( x );
}

inline void addRange( const Range & item , vector<Range> & v )
{
    vector<Range>::iterator pos;
    pos = upper_bound( v.begin() , v.end() , item );
    if( pos == v.end() )
	v.push_back( item );
    else
	v.insert( pos , item );
}

inline void makeSortedVectorNotOverlaping( vector<Range> & v )
{
    size_t i,j;
    for( i=0 ; i < v.size() ; )
    {
	for( j=i+1 ; j < v.size() && v[i].overlaps( v[j] ) ; v[j++].invalidate() )
	    v[i].combine( v[j] );
	i = j;
    }
    vector<Range>::iterator last = remove_if( v.begin() , v.end() , isRangeInvalid );
    v.resize( last - v.begin() );
}

inline void trimVector( const Range & the_range , vector<Range> & v )
{
    vector<Range>::iterator pos;

    /* cut back the left side */
    for( pos=v.begin() ; pos != v.end() && (*pos).isAbove( the_range ) ; (*pos).invalidate(), ++pos );
    v.erase( v.begin() , pos );
    if( !v.empty() )
	v[0].adjustLeftSide( the_range );

    /* cut back the right side */
    pos = upper_bound( v.begin() , v.end() , the_range , isRangeBelow );
    v.resize( pos - v.begin() );
    if( !v.empty() )
	v[v.size()-1].adjustRightSide( the_range );
}

inline void printFinalRanges( const Range & the_range , const vector<Range> & v )
{
    size_t i;

    if( v.size() < 1 )
    {
	cout << the_range;
	return;
    }
    if( v.size() == 1 && v[0] == the_range )
    {
	cout << "No range left" << endl;
	return;
    }

    if( the_range < v[0] )
	cout << "(" << the_range.left() << "," << v[0].left()-1 << ")" << endl;
    for( i=1 ; i < v.size() ; i++ )
	cout << "(" << v[i-1].right()+1 << "," << v[i].left()-1 << ")" << endl;
    if( the_range.right() > v[v.size()-1].right() )
	cout << "(" << v[v.size()-1].right()+1 << "," << the_range.right() << ")" << endl;
}

int main()
{
    vector<Range> ranges;
    Range the_range(7,27);

    /*
     * don't add ranges and sort them at the end (push_back(), push_back()..., sort());
     * this makes it faster
     */
    addRange( Range(6,9) , ranges );
    addRange( Range(14,20) , ranges );
    addRange( Range(21,24) , ranges );
    addRange( Range(12,22) , ranges );

    makeSortedVectorNotOverlaping( ranges );
    trimVector( the_range , ranges );
    printFinalRanges( the_range , ranges );

    return 0;
}