Rooks

On an $n \times n$ chessboard ($1 \le n \le 3000$) we place $n$ rooks, one per rook index. The placement must satisfy the following rules.

• For each $i = 1, \dots, n$, rook $i$ must be placed inside a rectangle given by two corners $(a_i, b_i)$ and $(c_i, d_i)$, where $(a_i, b_i)$ is the top-left square (row, column) and $(c_i, d_i)$ is the bottom-right square, with $1 \le a_i \le c_i \le n$ and $1 \le b_i \le d_i \le n$. The top-left square of the board is $(1, 1)$ and the bottom-right square is $(n, n)$. In other words, the row of rook $i$ must lie in $[a_i, c_i]$ and its column must lie in $[b_i, d_i]$.
• No two rooks may attack each other, meaning no two rooks share the same row or the same column.

Decide whether all rooks can be placed inside their rectangles without any two attacking each other, and if so, output one such placement.

The first line contains a single integer $n$ ($1 \le n \le 3000$). Each of the next $n$ lines contains four integers $a_i$, $b_i$, $c_i$, $d_i$ separated by single spaces, describing the rectangle for rook $i$ ($1 \le a_i \le c_i \le n$, $1 \le b_i \le d_i \le n$, every value between $1$ and $n$).

If no valid placement exists, print the single word NIE (Polish for "no").

Otherwise print $n$ lines. Line $i$ contains the row and column of rook $i$ separated by a single space, where the row lies in $[a_i, c_i]$ and the column lies in $[b_i, d_i]$; the rooks are listed in the same order as their rectangles were given.

Because several placements can be valid, print the lexicographically smallest one. Compare two placements by the sequence formed by reading the values in order: row of rook $1$, column of rook $1$, row of rook $2$, column of rook $2$, and so on. Equivalently, make the row of rook $1$ as small as possible, then its column as small as possible, then the row of rook $2$, then its column, and so on.