28605번 - Взрывоопасная лестница (Once) 스페셜 저지다국어

Джинкс совершила очередное ограбление, и теперь пытается убежать от преследователей. На ее пути отступления находится лестница, состоящая из строительных блоков Хекстека. После прохода по ней, она собирается эту лестницу взорвать.

Лестница состоит из $n$ уровней, каждый из уровней состоит из какого-то количества блоков. А именно, $i$-й сверху уровень состоит из $i$ строительных блоков. Каждый блок Хекстека обладает какой-то магической силой. Так как сила любой лестницы в ее фундаменте, то магическая сила взрыва лестницы зависит только от самого нижнего ее уровня. А именно, чем лексикографически меньше последовательность магических блоков последнего уровня в лестнице, тем сильнее будет взрыв.

Напомним, что последовательность $a$ лексикографически меньше последовательности $b$, если существует такой индекс $i$, что $a_1 = b_1, a_2 = b_2, \ldots, a_{i - 1} = b_{i - 1}$, а $a_i < b_i$. Иными словами, что в первой различающейся позиции, в $a$ стоит меньшее значение.

У Джинкс есть в запасе немного времени, поэтому она может переставить уровни в любом порядке, после чего блоки, под которыми появилось пустое место, падают вниз под действием гравитации. Времени не так много, как хотелось бы, поэтому такую операцию она сможет осуществить лишь один раз. Теперь ей интересно, в каком порядке нужно переставить уровни, чтобы сила взрыва была максимальна.

В первой строке находится единственное число $n$ --- количество уровней лестницы ($1 \leqslant n \leqslant 1000$).

В $i$-й из следующих $n$ строк через пробел перечислены $i$ чисел $a_{i,1}, \ldots, a_{i,i}$ --- магические силы блоков в $i$-м ряду ($0 \leqslant a_{i,j} \leqslant 10^9$).

Выведите перестановку из $n$ чисел от $1$ до $n$ --- порядок, в котором Джинкс должна расположить уровни сверху вниз, чтобы сила взрыва была максимальна.

В приведенном примере, изначально лестница выглядит так:

1
2 2
1 3 3

После смены порядка уровней:

1 3 3
2 2
1

После действия гравитации:

1
2 3
1 2 3