Problem G: Fabled Rooks

We would like to place n rooks, 1 ≤ n ≤ 5000, on a n×n board subject to the following restrictions

The first line of input contains one integer number, n, the side of the board. n lines follow giving the rectangles where the rooks can be placed as described above. The i-th line among them gives xli, yli, xri, and yri.

Your task is to find such a placing of rooks that the above conditions are satisfied and then output n lines each giving the position of a rook in order in which their rectangles appeared in the input. If there are multiple solutions, any one will do. Output IMPOSSIBLE if there is no such placing of the rooks.

Sample input

8
1 1 2 2
5 7 8 8
2 2 5 5
2 2 5 5
6 3 8 6
6 3 8 5
6 3 8 8
3 6 7 8

Output for sample input

1 1
5 8
2 4
4 2
7 3
8 5
6 6
3 7


K. Diks, adapted by P. Rudnicki
ACPC 2006