354. Just Matrix
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard
This task is not about Berland or Beerland troubles, roads or flights. There will be no boring coins. This task is about simple square matrix.
Numbers from 1 to
n2 were written down in
nx
n square matrix
A. Each number was written exactly once. After that for each number the pair
topi,j and
lefti,j was written.
topi,j is the number of elements in column
j bigger than
Ai,j and positioned to the top from
Ai,j.
lefti,j is the number of elements in the row
i bigger than
Ai,j and positioned to the left from
Ai,j.
You are given matrices
top and
left. Your task is to find any possible matrix
A fulfilling the requirements of the problem.
Input
The first line of the input contains integer number
n (1 ≤
n ≤ 600). Further matrices
top and
left are written, each in the form of
n lines of
n non-negative integer numbers. The matrices are separated by the empty line. Numbers in both matrices are not bigger than
n.
Output
Write to the output matrix
A in the format similar to the input data. If there are several solutions, you can choose any of them. If there is no solution, write to the output just one number 0.
Example(s)
sample input | sample output |
3
0 0 0
0 0 0
0 0 2
0 0 0
0 1 0
0 1 2
|
1 2 6
5 3 7
9 8 4
|