EduBrick

Побочные диагонали

5000 мс · 256 МБ · всё или ничего

Дано поле из nn строк по mm чисел. Клетки, у которых сумма номеров строки и столбца одинакова, лежат на одной побочной диагонали.

Выведите суммы всех таких диагоналей в порядке возрастания этой суммы.

Формат ввода

В первой строке числа nn и mm от 11 до 500500. В следующих nn строках по mm чисел от 109-10^9 до 10910^9.

Формат вывода

n+m1n + m - 1 чисел через пробел.

Примеры

ввод
2 2
1 2
3 4
вывод
1 5 4

Примечание

Номер диагонали — это просто сумма номеров строки и столбца. Заведите список сумм нужной длины и складывайте в ячейку с этим номером.

Войдите, чтобы отправлять решения.