### Problem

We would like to place n rooks, 1 ≤ n ≤ 5000, on a n × n board subject to the following restrictions
• The i-th rook can only be placed within the rectangle given by its left-upper corner (xli , yli) and its rightlower corner (xri , yri), where 1 ≤ i ≤ n, 1 ≤ xli ≤ xri ≤ n, 1 ≤ yli ≤ yri ≤ n.
• No two rooks can attack each other, that is no two rooks can occupy the same column or the same row.

### Mean

8皇后+贪心的变形，变成5000皇后了~

### Code

```#include <bits/stdc++.h>
using namespace std;

struct Node {
int st, ed, id;
bool operator < (const Node & rhs) const {
return ed > rhs.ed;
}
};
const int maxn = 5120;
int n, resx[maxn], resy[maxn];
Node vx[maxn], vy[maxn];

bool solve(Node *v, int *res) {
sort(v + 1, v + n + 1, [](const Node &a, const Node &b) { return a.st < b.st; });
priority_queue<Node> qu;
for(int i = 1, cnt = 1; i <= n; ++i) {
while(cnt <= n && v[cnt].st <= i)
qu.push(v[cnt++]);
if(qu.empty() || qu.top().ed < i)
return false;
Node node = qu.top(); qu.pop();
res[node.id] = i;
}
return true;
}

int main() {
while(~scanf("%d", &n), n) {
for(int i = 1; i <= n; ++i) {
scanf("%d%d", &vx[i].st, &vy[i].st);
scanf("%d%d", &vx[i].ed, &vy[i].ed);
vx[i].id = vy[i].id = i;
}
if(solve(vx, resx) && solve(vy, resy)) {
for(int i = 1; i <= n; ++i)
printf("%d %d\n", resx[i], resy[i]);
} else {
printf("IMPOSSIBLE\n");
}
}
return 0;
}
```