룩 배치

$n \times n$ 크기의 체스판($1 \le n \le 3000$)에 룩 $n$개를 놓으려고 합니다. 배치는 다음 규칙을 만족해야 합니다.

• 각 $i = 1, \dots, n$에 대해 $i$번 룩은 두 꼭짓점 $(a_i, b_i)$와 $(c_i, d_i)$로 주어지는 직사각형 안에 놓여야 합니다. 여기서 $(a_i, b_i)$는 직사각형의 왼쪽 위 칸(행, 열)이고 $(c_i, d_i)$는 오른쪽 아래 칸이며, $1 \le a_i \le c_i \le n$, $1 \le b_i \le d_i \le n$입니다. 체스판의 왼쪽 위 칸은 $(1, 1)$, 오른쪽 아래 칸은 $(n, n)$입니다. 즉 $i$번 룩이 놓이는 칸의 행은 $[a_i, c_i]$, 열은 $[b_i, d_i]$ 범위 안에 있어야 합니다.
• 어떤 두 룩도 서로 공격할 수 없습니다. 즉 두 룩이 같은 행이나 같은 열에 놓일 수 없습니다.

모든 룩을 각자의 직사각형 안에, 서로 공격하지 않도록 놓을 수 있는지 판단하고, 가능하다면 그러한 배치 하나를 출력하세요.

첫 번째 줄에 정수 $n$($1 \le n \le 3000$)이 주어집니다. 이어지는 $n$개의 줄에는 각각 네 정수 $a_i$, $b_i$, $c_i$, $d_i$가 공백 하나로 구분되어 주어지며, $i$번 룩의 직사각형을 나타냅니다($1 \le a_i \le c_i \le n$, $1 \le b_i \le d_i \le n$, 모든 값은 $1$ 이상 $n$ 이하).

유효한 배치가 존재하지 않으면 NIE(폴란드어로 "아니오") 한 단어만 출력합니다.

그렇지 않으면 $n$개의 줄을 출력합니다. $i$번째 줄에는 $i$번 룩의 행과 열을 공백 하나로 구분해 출력하며, 행은 $[a_i, c_i]$, 열은 $[b_i, d_i]$ 범위 안에 있어야 합니다. 룩은 입력에서 직사각형이 주어진 순서와 같은 순서로 출력합니다.

유효한 배치가 여러 개일 수 있으므로 사전순으로 가장 작은 배치를 출력합니다. 두 배치는 값을 순서대로 나열한 수열, 즉 1번 룩의 행, 1번 룩의 열, 2번 룩의 행, 2번 룩의 열, 이런 순서로 비교합니다. 다시 말해 1번 룩의 행을 가능한 한 작게, 그다음 그 열을 가능한 한 작게, 그다음 2번 룩의 행, 그다음 그 열을 작게 하는 식으로 최소화합니다.