Головоломка з кубиками
Давайте розглянемо головоломку з кубиками. Правила цієї головоломки такі:
1. У головоломці використовуються кубики з шістьма гранями, як показано на Рисунку 1.
Рисунок 1. Грані кубика
2. З двадцяти семи таких кубиків будується 3×3×3 куб, як показано на Рисунку 2.
Рисунок 2. 3×3×3 куб
3. При побудові куба з кубиків сума чисел на гранях сусідніх кубиків, які розташовані один проти одного, повинна дорівнювати семи (див. Рисунок 3). Наприклад, якщо одна грань пари позначена "2", то інша грань повинна бути "5".
Рисунок 3. Пара граней, розташованих одна проти одної
4. Верхній та передній вигляди куба частково задані, тобто числа на гранях деяких кубиків зверху та спереду задані.
Рисунок 4. Верхній та передній вигляди куба
5. Мета головоломки - знайти всі можливі розташування кубиків, які відповідають заданій інформації про верхній та передній вигляди.
Ваше завдання - написати програму, яка розв'язує цю головоломку.
Вхідні дані
Вхід складається з декількох наборів даних у наступному форматі.
N
Набір_даних_1
Набір_даних_2
...
Набір_даних_N
N - це кількість наборів даних.
Формат кожного набору даних такий.
T_11 T_12 T_13
T_21 T_22 T_23
T_31 T_32 T_33
F_11 F_12 F_13
F_21 F_22 F_23
F_31 F_32 F_33
T_ij та F_ij (1 ≤ i ≤ 3, 1 ≤ j ≤ 3) - це грані кубиків, що з'являються на верхньому та передньому виглядах, як показано на Рисунку 7, або нуль. Нуль означає, що грань у відповідній позиції невідома.
Вихідні дані
Для кожного можливого розташування кубиків обчисліть суму чисел, позначених на дев'яти гранях, що з'являються на правій стороні куба, тобто, з використанням позначень, наведених на Рисунку 2,
Для кожного набору даних ви повинні вивести суми правого вигляду для всіх можливих розташувань у зростаючому порядку та без повторень. Числа повинні бути розділені одним пробілом.
Коли для набору даних немає можливих розташувань, виведіть нуль.
Наприклад, припустимо, що верхній та передній вигляди задані наступним чином.
Рисунок 5.
Існує чотири можливих правих вигляди, як показано на Рисунку 6. Суми правого вигляду дорівнюють 33, 36, 32 та 33 відповідно. Після впорядкування їх у зростаючому порядку та усунення дублікатів, відповідь повинна бути "32 33 36".
Вихід повинен містити один рядок для кожного набору даних. Вихід може мати пробіли на кінцях рядків.
Рисунок 6.