On the chessboard of size n*n (1<=n<=3000) we put n rooks. The arrangement of the rooks should satisfy the following rules:

For each i = 1,...,n, the i-th rook can be put on the rectangle specified by two pairs of coordinates: (a_i, b_i), (c_i, d_i), where (a_i, b_i) are coordinates of the square in the left upper corner of the rectangle (row, column), (c_i, d_i) are coordinates of the square in the right lower corner of the rectangle, 1 <= a_i <= c_i <= n and 1 <= b_i <= d_i <= n. A field in the left upper square has coordinates (1, 1), a square in the right lower corner has coordinates (n, n).

No two rooks can attack each other, i.e. they cannot stay in the same row or the same column.

Task

• reads from the text file WIE.IN the size of the rectangle n and for each i = 1, ..., n the coordinates of the rectangle, in which the i-th rook can be put.
• verifies, whether the rooks may be put in appropriate rectangles so that no two of them attack each other, and if so, finds one of such arrangements.
• writes into the text file WIE.OUT one arrangement of the rooks satisfying given conditions or single word "NIE" ("no" in Polish) if such an arrangement doesn't exists.

Input

In the first line of the input file WIE.IN there is written one positive integer n<=3000. In each of the following n lines there are written 4 positive integers not grater than n separated by single spaces. The numbers in the i-th line are the coordinates of the rectangle, in which  the i-th rook may be put (a_i, b_i, c_i and d_i respectively).

Output

In the output file WIE.OUT there should be written one word NIE ("no" in Polish), or in each of n lines of the output file there should be written two integers separated by a single space. The numbers in the i-th line should denote the position of i-th rook (row, column). This position should be within the rectangle specified by coordinates in the (i+1)-th line of the input file WIE.IN. Pay attention to the fact that the positions of the rooks should be written in the same order as the coordinates of the rectangles were read from the file WIE.IN.

Example

For the file WIE.IN:
4
1 1 1 1
1 3 2 4
3 1 4 2
2 2 4 4

one of the correct solutions is the file WIE.OUT:
1 1
2 3
3 2
4 4

Your program should look for the file WIE.IN in the current directory and produce the output file WIE.OUT in the current directory too. The file containing the source code of your program should have a name WIE.???, whereas you should put three-letter abbreviation the of used programming language name instead of ???. The same program in executable form should be written in file WIE.EXE