33562번 - shapex

문제

shapex는 각 사분면에 원형, 사각형, 풍차, 별 모양이 배치된 도형들을 자르고, 합치고, 색칠하여 복잡하고 다채로운 도형들을 만들어내는 것이 목표인 게임이다.

도형들과 그 도형들에 대한 조작이 주어졌을 때 만들어지는 도형을 구하는 프로그램을 작성해 보자.

shapex에서는 도형을 쉽게 나타내기 위해 도형 코드를 사용한다. 다음은 도형 코드에 대한 설명이다.

• 기본 도형
  • 기본 도형은 총 네 가지로 종류와 코드는 다음과 같다.
    • 원형(, Circle): C
    • 사각형(, Rectangle): R
    • 풍차(, Windmill): W
    • 별(, Star): S
• 색상
  • 색상은 총 여덟 가지로 종류와 코드는 다음과 같다.
    • 빨강(, Red): r
    • 초록(, Green): g
    • 파랑(, Blue): b
    • 노랑(, Yellow): y
    • 보라(, Purple): p
    • 시안(, Cyan): c
    • 색칠되지 않음(, Uncolored): u
    • 하양(, White): w
• 도형
  • 기본 도형과 색상을 조합하여 하나의 완전한 도형을 만들 수 있다.
  • 도형 한 층은 북동쪽, 남동쪽, 남서쪽, 북서쪽 사분면으로 나뉜다.
  • 한 사분면에는 하나의 기본 도형이 존재하거나 비어 있을 수 있다.
  • 하나의 기본 도형은 하나의 색상을 가진다.
  • 이런 층들을 최소 1층부터 최대 4층까지 쌓아 한 도형을 만들 수 있다.
  • 최고층 이하에 모든 사분면이 비어 있는 층이 있는 도형은 올바르지 않은 도형이다.
  • 그림에서 높은 층의 도형은 아래층보다 작게 보인다. 도형의 크기는 그림에만 나타나며 문제 풀이와 관련이 없다.
• 도형 코드
  • 기본 도형과 색상의 코드를 조합하여 도형을 코드로 나타낼 수 있다.
  • 도형 한 층의 코드는 '(기본 도형)(색상)(기본 도형)(색상)(기본 도형)(색상)(기본 도형)(색상)'의 형식으로 나타낼 수 있다. 이때 (기본 도형)(색상) 쌍은 순서대로 북동쪽, 남동쪽, 남서쪽, 북서쪽 사분면의 정보를 나타낸다.
  • 비어 있는 사분면의 코드는 '--'으로 나타낸다.
  • 1층부터 가장 높은 층까지 각 층의 코드를 ':'로 구분하여 나타낸다.
  • 다음은 문제 상단에 있는 도형들의 코드 예시이다.

도형을 조작하는 여러 가지 기계로 더욱 복잡한 도형을 만들 수 있다. 다음은 도형 조작을 위한 기계들에 대한 설명이다.

• 절단기
  • 한 도형을 서쪽 절반과 동쪽 절반으로 나눈다.
  • 절단 후 어떤 층이 완전히 빈 경우, 즉 '--------'이 되는 경우에는 그 층이 사라지고 그 층보다 높은 층들을 한 층씩 내린다.
  • 절단 후 모든 층이 완전히 빈 경우, 아무런 도형도 생성되지 않는다.
• 회전기
  • 한 도형을 정해진 각도(90도, 180도, 270도)만큼 시계방향으로 회전시킨다.
• 결합기
  • 두 도형을 하나의 도형으로 결합한다.
  • 즉, 두 번째로 입력된 도형을 첫 번째로 입력된 도형의 위에서부터, 두 도형에 포함된 기본 도형이 서로 겹쳐 더이상 내리지 못하거나 가장 낮은 층이 1층에 도달할 때까지 내린 후 한 도형으로 합친다.
  • 결합 후 도형이 4층을 초과할 경우, 초과한 층은 사라진다.
• 색칠기
  • 한 도형의 비어 있지 않은 모든 층, 모든 사분면에 색을 칠한다.
  • 기존에 있던 색은 모두 새로운 색으로 덮어씌워진다.
  • '색칠되지 않음'으로는 색칠할 수 없다.

다음은 기계의 작동 예시이다.

도형 조작을 위해 레지스터를 사용한다. 다음은 레지스터에 대한 설명이다.

• 도형 조작을 위해 100ドル$개의 레지스터를 사용할 수 있다.
• 레지스터에는 순서대로 $R_1,ドル $R_2,ドル $\cdots,ドル $R_{100}$으로 이름이 매겨져 있다.
• 처음 주어지는 $N$개의 도형은 $R_1,ドル $R_2,ドル $\cdots,ドル $R_N$에 저장되어 있다.
• 나머지 100ドル−N$개의 레지스터에는 None이 저장되어 있다.
• 레지스터에 저장된 값은 다른 값이 저장되지 않는 이상 유지된다.

입력

첫 번째 줄에 처음 주어지는 도형의 개수 $N$(1ドル \le N \le 10$)과 조작의 개수 $M$(1ドル \le M \le 10,000円$)이 공백으로 구분되어 주어진다.

다음 $N$개의 줄에 처음 주어지는 도형의 코드가 순서대로 주어진다. 주어지는 도형들은 모두 1층만 있다. 올바른 도형 코드만 입력으로 주어진다.

다음 $M$개의 줄에 조작이 다음과 같은 형식으로 순서대로 주어진다. 주어지는 모든 레지스터 번호는 1ドル$ 이상 100ドル$ 이하의 정수이다.

• 1ドル$ $i$ $j$ $k$ $(j \neq k)$
  • $R_i$에 저장된 도형을 절단기에 넣어 서쪽 절반을 $R_j$에, 동쪽 절반을 $R_k$에 저장한다.
  • $R_i$에 저장된 값이 None일 경우 $R_j,ドル $R_k$에 저장되는 값도 None이다.
  • 어느 쪽 절반에서 도형이 생성되지 않을 경우 그 절반에 해당하는 레지스터에 저장되는 값도 None이다.
• 2ドル$ $i$ $j$ $k$ ($k \in$ {1ドル,ドル 2ドル,ドル 3ドル$})
  • $R_i$에 저장된 도형을 $k \times 90$도 회전기에 넣어 생성되는 도형을 $R_j$에 저장한다.
  • $R_i$에 저장된 값이 None일 경우 $R_j$에 저장되는 값도 None이다.
• 3ドル$ $i$ $j$ $k$
  • $R_i,ドル $R_j$에 저장된 도형을 순서대로 결합기에 넣어 생성되는 도형을 $R_k$에 저장한다.
  • $R_i,ドル $R_j$에 저장된 값 중에 None이 있을 경우 $R_k$에 저장되는 값도 None이다.
• 4ドル$ $i$ $j$ $k$ ($k \in$ {'r', 'g', 'b', 'y', 'p', 'c', 'w'})
  • $R_i$에 저장된 도형을 색칠기에 넣어 색상 $k$로 칠해서 $R_j$에 저장한다.
  • $R_i$에 저장된 값이 None일 경우 $R_j$에 저장되는 값도 None이다.

출력

모든 조작을 완료한 후 $R_{100}$에 저장된 값을 출력한다. 도형일 경우 도형 코드를 출력하고, None일 경우 None을 출력한다.

제한

힌트