学步园

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
#include <cctype>
#include <utility>
#include <map>
#include <string>
#include <climits> 
#include <set>
#include <string> 
#include <sstream>
#include <utility>
#include <ctime>
//#pragma comment(linker, "/STACK:1024000000,1024000000") 

using std::priority_queue;
using std::vector;
using std::swap;
using std::stack;
using std::sort;
using std::max;
using std::min;
using std::pair;
using std::map;
using std::string;
using std::cin;
using std::cout;
using std::set;
using std::queue;
using std::string;
using std::istringstream;
using std::getline;
using std::make_pair;
using std::greater;

const int MAXN(5010);

struct NODE
{
	int l, r, ind;
	friend bool operator < (const NODE &op1, const NODE &op2)
	{
		return op1.r < op2.r;
	}
};

int dic[MAXN][2];

struct LINK
{
	int first[MAXN];
	NODE data[MAXN];
	int next[MAXN], rear;

	void init()
	{
		memset(first, -1, sizeof(first));
		rear = 0;
	}
	void insert(int tl, int tr, int tind)
	{
		data[rear].l = tl;
		data[rear].r = tr;
		data[rear].ind = tind;
		next[rear] = first[tl];
		first[tl] = rear++;
	}                                                                 
};

LINK link1, link2;

template<typename T>
struct HEAP
{
	T arr[MAXN];
	T *p[MAXN];
	int ind, size;
	void init()
	{
		size = ind = 0;
	}
	
	bool empty()
	{
		return size == 0;
	}

	void sink(int sour)
	{
		int ch = sour << 1;
		T *temp = p[sour];
		while(ch <= size)
		{
			if(ch < size && *p[ch+1] < *p[ch])
				++ch;
			if(!(*p[ch] < *temp))
				break;
			p[sour] = p[ch];
			sour = ch;
			ch <<= 1;
		}
		p[sour] = temp;
	}

	void swim(int sour)
	{
		int fa = sour >> 1;
		T *temp = p[sour];
		while(fa >= 1 && *temp < *p[fa])
		{
			p[sour] = p[fa];
			sour = fa;
			fa >>= 1;
		}
		p[sour] = temp;
	}

	void push(const T &value)
	{
		arr[ind] = value;
		p[++size] = arr+ind++;
		swim(size);
	}

	NODE &top()
	{
		return *p[1];
	}

	void pop()
	{
		p[1] = p[size--];
		sink(1);
	}
};

HEAP<NODE> heap;

bool solve(int n)
{
	heap.init();
	NODE cur;
	for(int i = 1; i <= n; ++i)
	{
		for(int j = link1.first[i]; j != -1; j = link1.next[j])
			heap.push(link1.data[j]);
		if(heap.empty())
			return false;
		cur = heap.top();
		heap.pop();
		if(cur.r < i)
			return false;
		dic[cur.ind][0] = i;
	}
	heap.init();
	for(int i = 1; i <= n; ++i)
	{
		for(int j = link2.first[i]; j != -1; j = link2.next[j])
			heap.push(link2.data[j]);
		if(heap.empty())
			return false;
		cur = heap.top();
		heap.pop();
		if(cur.r < i)
			return false;
		dic[cur.ind][1] = i;
	}
	return true;
}

int main()
{
	int n;
	while(scanf("%d", &n), n)
	{
		link1.init();
		link2.init();
		int xl, yl, xr, yr;
		for(int i = 1; i <= n; ++i)
		{
			scanf("%d%d%d%d", &xl, &yl, &xr, &yr);
			link1.insert(xl, xr, i);
			link2.insert(yl, yr, i);
		}
		if(solve(n))
		{
			for(int i = 1; i <= n; ++i)
				printf("%d %d\n", dic[i][0], dic[i][1]);
		}
		else
			printf("IMPOSSIBLE\n");
	}
	return 0;
}