Единичным кубом назовём куб 1×1×1, вершины которого имеют целочисленные координаты x, y, z. Два единичных куба могут образовывать новый объект путём соединения их по граням. Кубоидом назовём непустое соединение единичных кубов (см. рисунок 1). Объём кубоида равен количеству единичных кубов, из которых он составлен. Блоком назовём кубоид с объёмом не больше четырёх. Скажем, что два блока имеют одинаковый тип, если один из них может быть получен из другого с помощью вращений и сдвигов блока (заметьте, что отражение делать запрещено). Всrего существует 12 типов блоков (см. рисунок 2). Цвета объектов на рисунке изображены лишь для иллюстрации структуры объектов, и они не несут никакой смысловой нагрузки.
Набор кубоидов D назовём декомпозицией кубоида S, если объединение всех кубоидов из D равно S, и никакой единичный куб из кубоида S не принадлежит одновременно двум разным кубоидам из D.
Напишите программу, которая по заданному описанию типов блоков и кубоида S определяет наименьший по количеству элементов набор блоков, являющийся декомпозиций кубоида S. Вам нужно выдать только типы блоков. Каждый тип должен быть выведен столько раз, сколько блоков этого типа встречается в декомпозиции.
Рисунок 1.
Рисунок 2.
Первая строка содержит объём V кубоида (1 ≤ V ≤ 50). Следующие V строк описывают положение единичных кубов, из которых состоит кубоид. Каждая из этих V строк состоит из трёх целых чисел x, y, z (1 ≤ x, y, z ≤ 7).
Первая строка содержит одно целое число M, которое равно количеству блоков в минимальном наборе, являющееся декомпозицией заданного кубоида.
Файл с описанием типов блоков приведено ниже.