| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 105 | 55 | 52 | 57.143% |
Bessie has an $N\times N$ (1ドル\le N\le 1000$) addition table where the integer in the cell at row $r$ and column $c$ is $r+c,ドル for all 1ドル\le r,c\le N$. For example, for $N=3,ドル the table would look like this:
2 3 4 3 4 5 4 5 6
Unfortunately, Elsie got ahold of the table and permuted it by performing the following three types of operations as many times as she wanted.
Elsie will always perform operations in increasing order of type; that is, she performs as many operations as she likes (possibly none) first of type 1ドル,ドル then of type 2ドル,ドル and finally of type 3ドル$.
Help Bessie recover a possible state of the table after Elsie finished applying all of her operations of types 1ドル$ and 2ドル,ドル but before applying any operations of type 3ドル$. There may be multiple possible answers, in which case you should output the lexicographically smallest one.
To compare two tables lexicographically, compare the first entries at which they differ, when reading both tables in the natural order (rows from top to bottom, left to right within a row).
The first line contains $N$.
The next $N$ lines each contain $N$ integers, representing Bessie's addition table after Elsie has permuted it.
The lexicographically minimum possible state of the table after all operations of types 1 and 2, but before any operations of type 3. It is guaranteed that the answer exists.
1 2
2
Regardless of what operations Elsie performs, the table won't change.
3 3 4 2 5 2 3 6 3 5
4 2 3 5 3 4 6 4 5
Here is a possible sequence of operations Elsie might have performed.
2 3 4 3 4 5 4 5 6 -> (op 1: swap columns 2 and 3) 2 4 3 3 5 4 4 6 5 -> (op 1: swap columns 1 and 2) 4 2 3 5 3 4 6 4 5 -> (op 3: swap values 2 and 3) 4 3 2 5 2 4 6 4 5 -> (op 3: swap values 3 and 4) 3 4 2 5 2 3 6 3 5
Note: the following is also a possible state of the table after operations of types 1 and 2, but it is not the lexicographically smallest because the second entry of the first row is larger than in the correct answer.
4 6 5 3 5 4 2 4 3
6 8 10 5 6 7 4 12 11 10 4 8 2 5 4 6 7 9 8 10 2 4 8 5 12 6 8 7 9 3 5 4 12 8 5 6 10
7 5 8 9 10 6 4 2 5 6 7 3 8 6 9 10 11 7 5 3 6 7 8 4 9 7 10 11 12 8 6 4 7 8 9 5