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.

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.

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.

sample input
sample output
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

Online Contester Team © 2002 - 2010. All rights reserved.