Маша очень любила строить башенки из кубиков в детстве, но теперь она уже взрослая, потому башенки из простых кубиков её не интересуют. Она купила детали для башенки, которые представляют собой блок 3*3*1, который очень легко описать матрицей 3 на 3, так как толщина блока всего 1 кубик.
Маше точно известно, что:
- при использовании всех блоков, можно гарантированно построить башенку, которая не будет иметь пустот, включая нижнюю и верхнюю границы;
- используя все блоки, можно построить башенку только одним и не более способами;
- при строительстве башенки блоки нельзя вращать;
- только два блока во всём наборе имеют сплошную верхнюю или же нижнюю границу;
- глубина пустот в блоке может состоять из 1 или 2 элементов;
- блоков, имеющих пустоты, которые нельзя покрыть при сборе башенки не существует.
Напишите программу, помогающую Маше определить, в каком порядке нужно строить башню, исходя из всех ограничений, написанных выше.
Входные данные
В первой строке подаётся число N (1 <= N <= 10) – количество блоков для башенки, далее на 3*N строках вводится по 3 цифры через пробел(0 – у блока отсутствует элемент в этой позиции, 1 – сам блок), представляющие из себя N блоков, доступных для строительства.
Нумерация блоков начинается с 1 и увеличивается при описании каждого последующего блока (то есть первый блок, второй и так далее).
Выходные данные
Вывести в ответе в одну строку через пробел каждый элемент – номера блоков в порядке сбора башни снизу-вверх.
Пояснение
Пример №2
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 0 0
1 1 0
0 1 1
1 1 1
0 1 1
0 0 1
1 0 0
1 1 1
1 1 1
|
3 1 2
|
|
2
|
4
1 1 0
1 0 1
0 0 1
1 1 1
1 1 1
0 1 1
1 0 0
1 1 1
0 0 1
0 1 0
1 1 0
1 1 1
|
4 1 3 2
|