Сергей собирает многоступенчатые ракеты. Для большей точности измерений параметров полета на каждой ступени ракеты он написал её мощность.
Но он совершенно забыл, что мощности ступеней любой ракеты должны строго возрастать. К примеру, мощности ступеней ракеты могут принимать значения 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.
В ответе нужно указать одну, любую из этих последовательностей.