ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1270. Уникуб

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Уникуб — это замечательный набор кубиков разработанных Б.П. Никитиным специально для развития детей. Вот и Васе в детстве папа смастерил такую игрушку. В общем-то ничего особенного — просто набор из 27 покрашенных кубиков — грани у кубиков красные, синие и жёлтые. Но раскраска подобрана таким образом, чтобы можно было собрать кубы 3×3×3 с внешней поверхностью любого из этих трёх цветов. Более того, можно (хотя это и не так просто) собрать куб 3×3×3 с шахматной ракраской не только всех внешних граней но и всех 6 (а с учетом двух сторон разреза и всех 12) сечений этого куба. Словом, это игрушка для развития детей до 10 лет, и Вася с папой активно в нее играли.
Когда же они построили все фигуры, предложенные в книжке (которые точно можно было собрать), Вася начал приставать к папе — а можно ли собрать вот такую фигуру, да ещё чтобы вот с таким расположением цветов? Поначалу папа честно пытался собирать предложенные Васей фигуры: некоторые получались, некоторые — нет. В конце концов папа обратился к студентам УрГУ с просьбой автоматизировать его тяжкий труд. Конечно же, студенты, да ещё и вооружённые компьютером, должны легко выполнить его просьбу.
Ваша задача будет заключаться в написании программы, которая по информации об имеющемся наборе кубиков и фигуре, которую надо построить, подсказала бы, как нужно действовать, чтобы сложить эту фигуру. Все фигуры в данной задаче — это размещённые в клетках трёхмерного пространства кубики, такие, что на некоторые грани некоторых кубиков наложено требование иметь определённый цвет.

Исходные данные

В первой строке стоит одно число 0 < N < 31 — количество кубиков, имеющихся в Васином распоряжении. Далее следует N строк с описанием имеющихся кубиков: для каждой грани в порядке «передняя, верхняя, правая, нижняя, левая, задняя» указан номер цвета грани — число от 1 до 30. Далее в новой строке следует целое число M — общее число кубиков в фигуре, которую надо поcтроить (0 < M < 31). Наконец, следуют M строк с описанием кубиков фигуры в формате <X> <Y> <Z> <F> <U> <R> <D> <L> <B>, где X,Y,Z — координаты клетки (все от 0 до 30), F, U, R, D, L, B — требования к цветам кубика в этой клетке, в том же порядке, что при описании цветов имеющихся кубиков (от 1 до 30, если стоит 0, то цвет может быть любым). Система координат — левая (OX смотрит вправо, OY — вперед, OZ — вверх) — это естественная система координат для Васи, который строит фигуру из кубиков на полу.

Результат

Если хотя бы одно решение поставленной задачи есть, то программа должна выводить какое-нибудь решение в виде последовательности из M строк. Строка с номером i должна содержать номер кубика (в порядке перечисления их во входных данных, начиная с 1 — ничего странного, именно так дети и считают) для клетки с номером i (также в порядке перечисления их во входных данных, начиная с 1). Если решения нет, то надо вывести единственное число 0.

Пример

исходные данныерезультат
1
6 1 3 4 5 2
1
0 0 0 1 2 3 6 5 4
1
Автор задачи: Александр Мироненко
Источник задачи: Чемпионат Уральского государственного университета, 25 октября 2003 года