Сергей собирает многоступенчатые ракеты. Для большей точности измерений параметров полета на каждой ступени ракеты он написал её мощность.

Но он совершенно забыл, что мощности ступеней любой ракеты должны строго возрастать. К примеру, мощности ступеней ракеты могут принимать значения 1 4 7, а 3 2 4 — не могут.

Собирать новую ракету Серёжа не хочет, однако он может вытащить некоторые ступени, не меняя порядка оставшихся. К примеру, из ракеты с мощностями ступеней 1 8 3 4 можно получить ракету 1 3 4 (вытащив ступень с мощностью 8), а ракеты 1 4 3 (порядок ступеней с мощностями 4 и 3 был изменен) и 1 8 3 (мощности ступеней не возрастают) получить нельзя.

Помогите Сергею вытащить минимальное количество ступеней так, чтобы мощность остальных ступеней строго возрастала.

У Сергея есть четыре ракеты. В таблице ниже для каждой ракеты приведена последовательность мощностей её ступеней.

Номер ракеты

Последовательность мощностей

1

5 3 4 2 3

2

1 6 3 2 5 8

3

4 6 7 5 6 7 1 2 8

4

2 5 3 5 3 4 7 3 8 4 9 6 7

Ответом на данную задачу являются четыре последовательности целых чисел: каждая из них — это последовательность мощностей оставшихся ступеней соответствующей ракеты. Каждую последовательность записывайте в соответствующей ей строке. Числа в последовательности должны быть разделены пробелом. Каждая последовательность должна строго возрастать, а также иметь как можно большую длину. Если существует несколько вариантов ответа, можно вывести любой из них.

Если вы не можете дать ответ для какой-то из ракет, запишите в качестве ответа для данной ракеты число 0.

Примечание. Рассмотрим пример. Допустим, у какой-то ракеты последовательность ступеней равна 1 4 5 2 3.


Для этой ракеты возможно два варианта ответа. Последовательность чисел в ответе может быть такой: 1 2 3. Или последовательность чисел может быть такой: 1 4 5.


В ответе нужно указать одну, любую из этих последовательностей.