Трехмерный тетрис

Игра в трехмерный тетрис происходит на поле, имеющем вид прямоугольного параллелепипеда размером W  D  H единичных кубиков. Введем координатную систему так, чтобы один из углов параллелепипеда находится в точке (0, 0, 0), противоположный ему – в точке (W, D, H), а ребра параллелепипеда были параллельны осям координаты. Каждый единичный кубик поля можно задать максимальными координатами его углов, тогда кубики будут иметь координаты от (1, 1, 1) до (W, D, H).

В процессе игры на поле последовательно появляются фигуры. Каждая фигура представляет собой множество единичных кубиков и обладает следующим свойством: от любого кубика можно добраться до любого другого, переходя через общую грань. Один из кубиков в фигуре является базовым – при поворотах он остается на месте.

Игрок может сделать несколько действий с фигурой. Каждое действие является либо перемещением на один в направлении одной из осей, либо поворотом на 90 градусов вокруг одной из осей. При повороте фигура исчезает с игрового поля, и затем появляется снова, уже в новом положении. Направления поворотов показаны на рисунке, при повороте вокруг оси OX ось OY переходит в ось OZ, при повороте вокруг оси OY ось OZ переходит в ось OX, при повороте вокруг оси OZ ось OX переходит в ось OY. Базовый кубик при повороте остается на месте.

Ваша задача – написать модуль, ответственный за определение, какие кубики в результате игры окажутся заняты фигурами. Вам задана последовательность появления фигур на поле и действия с этими фигурами, которые произвел игрок. Гарантируется, что каждое из действий допустимо, то есть не происходит выхода фигуры за границу поля, либо появления у двух фигур общего кубика.

Требуется по описанию последовательности появления фигур и действий с ними определить, какие кубики на поле будут заняты фигурами после выполнения всех этих действий.

В первой строке входного файла содержатся размеры игрового поля – три целых числа  W, D и H (1 ≤ W, H, D ≤ 100). 

Во второй строке входного файла задано целое число n – количество фигур, которые были размещены на игровом поле. (0 ≤ n ≤ 100). Каждая фигура задается следующим образом: на первой строке задано натуральное число m - количество кубиков в фигуре. (1 ≤ m ≤ 100) Далее следуют m строк, в i-й из которых содержится тройка целых чисел xi, yi, zi – координаты i-го кубика в фигуре в ее начальном положении. Базовый кубик описывается первым. 

Следующая строка содержит целое число k – количество операций, которые были проведены игроком с данной фигурой (0 ≤ k ≤ 100). Далее следуют k строк. Каждая из них начинается либо со слова «shift» либо со слова «rotate».

В первом случае далее следует одна из букв «x», «y» или «z», обозначающая, вдоль какой из осей был выполнен сдвиг, после чего через пробел идет либо символ «+», если сдвиг был осуществлен в положительном направлении данной оси, либо «–», если сдвиг был осуществлен в отрицательном направлении.

Если же строка начинается со слова «rotate», то далее идет одна из букв «x», «y» или «z», обозначающая, вокруг какой из осей был выполнен поворот.

Выведите в выходной файл в произвольном порядке координаты всех кубиков, которые будут заняты фигурами. На каждой строке должно содержаться три числа, разделенных пробелом – координаты кубика в формате «x y z».