3차원 테트리스

3차원 테트리스 게임은 $W \times D \times 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 \le W, H, D \le 100$)

입력 파일의 둘째 줄에는 필드 위에 놓인 도형의 개수 $n$이 주어진다. ($0 \le n \le 100$) 각 도형은 다음과 같이 주어진다. 첫째 줄에는 도형에 들어 있는 정육면체의 개수 $m$이 주어진다. ($1 \le m \le 100$) 이어서 $m$개의 줄이 주어지며, $i$번째 줄에는 도형의 초기 위치에서 $i$번째 정육면체의 좌표 $x_i$, $y_i$, $z_i$가 주어진다. 기준 정육면체가 첫 번째로 주어진다.

다음 줄에는 이 도형에 플레이어가 한 연산의 개수 $k$가 주어진다. ($0 \le k \le 100$) 이어서 $k$개의 줄이 주어진다. 각 줄은 단어 shift 또는 rotate로 시작한다.

shift인 경우, 이어서 어느 축을 따라 이동했는지를 나타내는 문자 x, y, z 중 하나가 주어지고, 그 뒤에 공백을 두고 해당 축의 양의 방향으로 이동했으면 +, 음의 방향으로 이동했으면 -가 주어진다.

rotate인 경우, 이어서 어느 축을 중심으로 회전했는지를 나타내는 문자 x, y, z 중 하나가 주어진다.

도형으로 채워진 모든 정육면체의 좌표를 아무 순서로 출력한다. 각 줄에는 정육면체의 좌표를 x y z 형식으로 공백을 두고 출력한다.