시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 95 | 51 | 43 | 51.807% |
On the chessboard of size n × n (1 ≤ n ≤ 3,000) we put n rooks. The arrangement of the rooks should satisfy the following rules:
Write a program which:
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 n, 1 ≤ n ≤ 3,000. In each of the following n lines there are written four positive integers not greater 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 (ai, bi, ci and di respectively).
In the standard output there should be written one word NIE
, 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. 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.
4 1 1 1 1 1 3 2 4 3 1 4 2 2 2 4 4
1 1 2 3 3 2 4 4