СиАОД

8.3. Матрица (8)

В матрице A размера N´N числа от 1 до N². Каждое число записано ровно один раз. Даны две матрицы размера N´N:Top и Left. Значение Top_{i j} определяет количество чисел, больших A_{i j}и расположенных выше по столбцу, Left_{i j} - количество чисел, больших A_{i j} и расположенных левее по строке. Найти возможные значения матрицы A. Если решений несколько, вывести любое.

Ввод из файла INPUT.TXT. В первой строке N (1 ≤ N ≤100), затем N строк матрицы Top (числа через пробел), затем N строк матрицы Left. Числа в обеих матрицах от 0 до N.

Вывод в файл OUTPUT.TXT матрицы A – N строк, числа в строке через пробел. Если решений нет, вывести 0.

Пример

Ввод

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

Подсказка. Основной принцип – проставлять очередное число в цикле от 1 до N² в такую клетку (i, j), гдеi –номер строки, а  j – номер столбца, значение которой должно быть наименьшим среди незаполненных клеток строки i и столбца j. Это свойство нужно уметь проверять по  матрицам Top и Left. Тогда заполненная матрица не будет противоречить заданным условиям. Различных решений может быть много.