| Во Флориде нет гор, и мужчина из Флориды не может осознать их существование. Ему действительно нужна ваша помощь в этом деле. |
Среди дикой природы находится горная местность, представленная в виде прямоугольной сетки с \(n\) строками и \(m\) столбцами. Каждая ячейка в сетке в соответствии с её положением обозначается \((i, j)\), где \(i\) — индекс строки, а \(j\) — индекс столбца. Высота ячейки \((i, j)\) обозначается \(a_{i,j}\).
Однако в этом регионе произошли некоторые изменения. Путь, состоящий из \(n + m - 1\) ячеек, начинающийся в левом верхнем углу \((1, 1)\) и заканчивающийся в правом нижнем углу \((n, m)\), был очищен. Иными словами, для каждой ячейки \((i, j)\) вдоль этого пути высота \(a_{i,j}\) была установлена равной \(0\). Каждая ячейка пути находится либо на одну ячейку ниже предыдущей (\(\mathtt{D}\)), либо на одну ячейку правее (\(\mathtt{R}\)).
Известно, что до того, как в регион были внесены изменения, он обладал магическим свойством: все строки и все столбцы имели одинаковую сумму высот. Более формально, существует целое число \(x\) такое, что \(\sum_{j=1}^m a_{i, j} = x\) для всех \(1\le i\le n\), и \(\sum_{i=1}^n a_{i, j} = x\) для всех \(1\le j\le m\).
Ваша задача состоит в том, чтобы назначить новые высоты ячейкам на пути таким образом, чтобы вышеупомянутое магическое свойство было восстановлено. Можно доказать, что решение всегда существует. Если существует несколько решений, удовлетворяющих данному свойству, выведите любое из них.
Выходные данные
Для каждого набора входных данных выведите \(n\) строк по \(m\) целых чисел, представляющих восстановленную сетку высот \(b_{i, j}\). Высоты должны удовлетворять \(-10^{15} \leq b_{i,j} \leq 10^{15}\), и дополнительно \(a_{i,j} = b_{i,j}\), если \((i, j)\) не находится на пути. Если существует несколько решений, выведите любое из них.
Примечание
В первом наборе входных данных сетка была заполнена таким образом, чтобы каждая строка и каждый столбец содержали числа \(1, 2, 3\) в некотором порядке, что приводит к общей сумме \(6\).
Во втором наборе входных данных сетка была заполнена таким образом, что сумма в каждой строке и в каждом столбце равнялась \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 3
DRRD
0 2 3
0 0 0
3 1 0
4 5
DRRRRDD
0 1 0 2 3
0 0 0 0 0
-1 0 -3 -3 0
0 0 0 -1 0
2 3
RRD
0 0 0
0 1 0
5 5
DDDDRRRR
0 25 2 9 11
0 6 13 20 22
0 17 24 1 8
0 3 10 12 19
0 0 0 0 0
|
1 2 3
2 3 1
3 1 2
-6 1 0 2 3
7 -1 3 2 -11
-1 0 -3 -3 7
0 0 0 -1 1
0 -1 1
0 1 -1
18 25 2 9 11
4 6 13 20 22
15 17 24 1 8
21 3 10 12 19
7 14 16 23 5
|