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

문제

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

Лестница состоит из $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$ раз. Теперь ей интересно, сколько раз и в каком порядке нужно переставить уровни, чтобы сила взрыва была максимальна.

Иными словами, Джинкс хочет за не более, чем $n$ действий получить лексикографически минимально возможный нижний ряд лестницы. Помогите ей это сделать.

입력

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

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

출력

В первой строке выведите целое число $k,ドル не превосходящее $n$ --- количество действий, которое нужно совершить Джинкс.

В следующих $k$ строках дайте описание действий. Строка номер $i$ должна содержать перестановку $p_i$ из $n$ целых чисел от 1ドル$ до $n,ドル задающую порядок расположения рядов в $i$-м действии. Число номер $p_{i,j}$ должно быть равно длине ряда, который надо расположить $j$-м сверху во время $i$-го действия.

Если возможных ответов несколько, выведите любой. Обратите внимание, что минимизировать $k$ не требуется, необходимо только, чтобы выполнялось неравенство 0ドル \leqslant k \leqslant n$.

제한

힌트

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

3
7 0
1 2 5
2 4 1 1

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

1 2 5
3
2 4 1 1
7 0

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

1
3 2
2 4 5
7 0 1 1