Decorative Dominoes

Marie likes dominoes. She is too young to fully understand the game, so she just makes arrangements based on this simple rule: each of the two ends of a domino must be adjacent to an end of another domino with the same number on it.

Figure D.1: Visualization of the first sample test case.

Today Marie found a large box of blank dominoes. This excites her because she can now show her full creativity: first she makes an unrestricted arrangement, then in a second step she paints numbers on both ends of all dominoes so that her simple rule is fulfilled.

She has already decided that putting the same number on each end of every domino is not satisfying enough. She wants to use each number at most twice. She does not restrict herself to numbers between $0$ and $6$, and she also does not care if two dominoes have the same pair of numbers on them.

Marie places the dominoes along an integer grid so that each domino occupies exactly two neighbouring grid squares. Marie's arrangement does not have to be connected.

After Marie decides on an arrangement, she notices that choosing suitable numbers is harder than she first thought. Help her find a valid numbering for her arrangement or state that this is impossible.

The input consists of:

• One line with an integer $n$ ($2 \leq n \leq 5\,000$), the number of dominoes in Marie's arrangement.
• $n$ lines, each with four integers $x\_1$, $y\_1$, $x\_2$, $y\_2$ ($1 \le x\_1, y\_1, x\_2, y\_2 \le 10\,000$), where $(x\_1, y\_1)$ and $(x\_2, y\_2)$ are the grid positions of the two ends of one domino.

All dominoes occupy two neighbouring positions in the integer grid and no two dominoes overlap.

If a valid numbering exists, print $n$ lines, the $i$th of which contains two numbers, the integers Marie should write on the two ends of the $i$th domino. Output the numbers in the same order as the dominoes, including their two ends, appear in the input. All numbers in the output should be integers between $0$ and $10^6$ inclusive. If multiple valid numberings exist, you may output any one of them. If there does not exist a valid numbering, output impossible instead.