장식용 도미노

Marie는 도미노를 좋아한다. 게임을 온전히 이해하기에는 너무 어려서, 다음과 같은 단순한 규칙에 따라 배열만 만든다. 도미노의 양 끝은 각각 같은 수가 적힌 다른 도미노의 끝과 인접해야 한다.

그림 D.1: 첫 번째 예제의 시각화.

오늘 Marie는 빈 도미노가 가득 든 큰 상자를 발견했다. 먼저 아무 제약 없이 배열을 만든 다음, 두 번째 단계에서 모든 도미노의 양 끝에 수를 칠해 자신의 단순한 규칙을 만족시키면 되므로, 이는 Marie에게 매우 신나는 일이다.

그녀는 이미 모든 도미노의 양 끝에 같은 수를 적는 것은 만족스럽지 않다고 생각했다. 각 수는 최대 두 번까지만 사용하려고 한다. 하지만 수를 $0$에서 $6$ 사이로 제한하지는 않으며, 두 도미노가 같은 수 쌍을 가져도 상관하지 않는다.

Marie는 도미노를 정수 격자 위에 배치해서, 각 도미노가 정확히 이웃한 두 격자 칸을 차지하게 한다. Marie의 배열이 반드시 연결되어 있을 필요는 없다.

배열을 정한 뒤, Marie는 적절한 수를 고르는 것이 처음 생각보다 어렵다는 것을 깨닫는다. 주어진 배열에 대해 유효한 번호를 찾거나, 불가능하다고 알려 주자.

입력은 다음과 같다.

• Marie의 배열에 있는 도미노의 개수 $n$ ($2 \leq n \leq 5\,000$)을 담은 한 줄.
• $n$개의 줄. 각 줄에는 네 정수 $x\_1$, $y\_1$, $x\_2$, $y\_2$ ($1 \le x\_1, y\_1, x\_2, y\_2 \le 10\,000$)가 주어지며, $(x\_1, y\_1)$과 $(x\_2, y\_2)$는 한 도미노의 두 끝이 있는 격자 위치이다.

모든 도미노는 정수 격자에서 이웃한 두 위치를 차지하며, 두 도미노가 겹치지 않음이 보장된다.

유효한 번호가 존재하면 $n$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 도미노의 두 끝에 Marie가 각각 적어야 할 두 정수를 출력한다. 입력에 도미노가 등장하는 순서와 두 끝의 순서를 그대로 따라 출력한다. 출력의 모든 수는 $0$ 이상 $10^6$ 이하의 정수여야 한다. 유효한 번호가 여러 개면 아무거나 출력해도 된다. 유효한 번호가 존재하지 않으면 대신 impossible을 출력한다.