Задача №1859. Волшебный лес
Василиса Премудрая с Иваном-царевичем сбежали от морского царя. Царь немедленно выслал погоню. Уже совсем близко стук копыт, а верный конь Василисы устал нести двоих седоков... Единственное, что спасёт беглецов — чудо!
Сохраняя хладнокровие, Василиса решает в уме сложную задачу. Она хочет сотворить между собой и преследователями волшебный лес. Этот лес будет представлять собой \(n\) рядов деревьев, идущих строго с запада на восток. В каждом ряду будет также \(n\) деревьев, образующих вместе \(n\) рядов, идущих строго с севера на юг. Более того, суммарная высота деревьев в \(i\)-м ряду с запада на восток должна составлять ровно \(a_i\) метров, а суммарная высота деревьев в \(j\)-м ряду с севера на юг — ровно \(b_j\) метров. Наконец, высота каждого дерева должна выражаться целым числом метров. Сотвори такой лес — и преследователи будут без толку плутать по нему, пока волшебство не ослабнет и лес не исчезнет.
Вдобавок ко всему, Василиса потратит на волшебство столько сил, какова будет высота самого высокого дерева в этом лесу. Конечно же, Василиса хочет сохранить силы для дальнейшего бегства. Поэтому она хочет, чтобы высота самого высокого дерева оказалась как можно меньше.
Помогите Василисе Премудрой и Ивану-царевичу — найдите такие высоты деревьев, что лес будет обладать описанными волшебными свойствами, и при этом максимальная из высот деревьев была бы как можно меньше.
В первой строке входного файла задано целое число \(n\) (\(2 \le n \le 1000\)). Во второй строке заданы \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) через пробел — сумма высот деревьев в рядах, идущих с запада на восток (\(0 \le a_i \le 10^6\)). В третьей строке заданы \(n\) целых чисел \(b_1, b_2, \ldots, b_n\) через пробел — сумма высот деревьев в рядах, идущих с севера на юг (\(0 \le b_j \le 10^6\)).
Если сотворить волшебный лес с данными параметрами невозможно, выведите «NO» в первой строке выходного файла. Иначе в первой строке выведите «YES», а в следующих \(n\) строках по \(n\) целых неотрицательных чисел через пробел в каждой — высоты деревьев. Сумма чисел в \(i\)-й из последних \(n\) строк должна равняться \(a_i\), а сумма чисел в \(j\)-м столбце должна равняться \(b_j\). Максимальное число в ответе должно быть минимально возможным. Если правильных ответов несколько, можно выводить любой из них.
2 1 3 2 2
YES 1 0 1 2
2 1 3 2 4
NO