In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].

If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.

On the chessboard of size () we put rooks. The arrangement of the rooks should satisfy the following rules:

- For each , the -th rook can be put on the rectangle specified by two pairs of coordinates: , , where ) are coordinates of the square in the left upper corner of the rectangle (row, column), ) are coordinates of the square in the right lower corner of the rectangle, and . A field in the left upper square has coordinates , a square in the right lower corner has coordinates .
- No two rooks can attack each other, i.e. they cannot stay in the same row or the same column.

Write a program which:

- reads from the standard input the size of the rectangle and for each the coordinates of the rectangle, in which the -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 standard output one arrangement of the rooks satisfying given conditions
or single word
`NIE`(which means “no” in Polish) if such an arrangement doesn't exists.

In the first line of the standard input there is written one positive integer , . In each of the following lines there are written four positive integers not grater than separated by single spaces. The numbers in the -th line are the coordinates of the rectangle, in which the -th rook may be put (, , and respectively).

In the standard output there should be written one word `NIE`,
or in each of lines of the output file there should be written two integers separated by a single space.
The numbers in the -th line should denote the position of -th rook (row, column).
This position should be within the rectangle specified by coordinates in the -th line of the input.
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 input.

For the input data:

4 1 1 1 1 1 3 2 4 3 1 4 2 2 2 4 4

the correct result is:

1 1 2 3 3 2 4 4

*Task author: Krzysztof Diks.*