테트리스 시뮬레이션

테트리스는 많은 사람이 해 본 비디오 게임이다. 여기서는 규칙을 단순하게 바꾼 테트리스를 시뮬레이션한다.

게임판은 가로 $W$칸, 세로 $H$칸이고 처음에는 비어 있다. 열 번호는 왼쪽부터 $0$번에서 $W-1$번까지, 행 번호는 위쪽부터 $0$번에서 $H-1$번까지 붙인다. 테트로미노는 한 번에 하나씩, 게임판 위쪽 바깥에서 아래로 떨어진다. 떨어지는 조각은 한 행씩 내려가다가, 한 행 더 내려가면 게임판 바닥 아래로 나가거나 먼저 놓인 조각과 겹치는 순간 그 자리에 멈춘다. 떨어지는 동안 조각은 좌우로 움직이지도 않고 회전하지도 않는다.

조각이 멈춘 직후, 빈틈없이 채워진 행은 모두 지워진다. 여러 행이 한꺼번에 지워지기도 한다. 지워진 행은 사라지고, 그 위에 있던 행은 지워진 행의 수만큼 아래로 내려오며, 같은 수만큼 빈 행이 맨 위에 생긴다. 다음은 그 예다. 그림에서 o는 방금 멈춘 조각이다.

  |..............|      |..............|      |..............|
  |.............o|      |..............|      |..............|
  |.............o|      |..............|      |..............|
  |.............o|      |..............|      |..............|
  |.............o|      |..............|      |..............|
  |..xx..........| -->  |..xx..........| -->  |..............|
  |xxxxxxxxxxxxx.|      |xxxxxxxxxxxxxo|      |..............|
  |xxxxxxxxxxxxx.|      |xxxxxxxxxxxxxo|      |..xx..........|
  |xx..xxxxxxxxx.|      |xx..xxxxxxxxxo|      |xx..xxxxxxxxxo|
  |xxxxxxxxxxx...|      |xxxxxxxxxxx..o|      |xxxxxxxxxxx..o|
  ----------------      ----------------      ----------------

  낙하 중               멈춤                  두 행 지움

단순하게 바꾼 이 게임에서는 행이 지워진 뒤 공중에 뜬 칸이 더 떨어지지 않는다. 위쪽의 두 칸은 열을 그대로 둔 채 지워진 두 행만큼만 내려온다. 그래서 원래 테트리스와 달리 행이 연쇄로 지워지는 일은 없다.

$N$개의 조각을 모두 놓으면 게임이 끝난다. 조각이 멈춘 자리에서 칸 하나라도 $0$번 행보다 위에 남아 있으면 게임판 높이가 모자라 그 조각을 놓을 수 없으므로, 이때도 게임이 끝난다.

각 조각의 종류와 회전, 떨어지는 가로 위치는 입력으로 주어진다. 게임을 시뮬레이션해서 마지막 게임판을 구하라.

테트로미노는 7가지다.

1   2   3   4   5   6   7

x    x  x    x  xx  x    x
xx  xx  x    x  xx  x   xxx
 x  x   xx  xx      x
                    x

조각의 회전은 $0 \le r < 4$인 정수 $r$로 나타낸다. 위 그림은 $r = 0$일 때의 모양이고, $r$이 1 커질 때마다 모양을 반시계 방향으로 90도 돌린다. 돌린 뒤에는 경계 상자를 다시 잡으므로, 각 $r$의 모양은 언제나 자기 경계 상자에 딱 맞는다. 7번 조각과 1번 조각의 네 가지 회전은 다음과 같다.

r=0   r=1  r=2   r=3

  x     x   xxx   x
 xxx   xx    x    xx
        x         x

 x     xx   x     xx
 xx   xx    xx   xx
  x          x

가로 위치는 정수 $x$로 나타낸다. $x$는 조각 경계 상자의 왼쪽 끝 열이다. 경계 상자의 너비가 $w$이면 조각은 $x$번 열부터 $x + w - 1$번 열까지 차지한다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 정수 $W$, $H$, $N$이 주어진다. 차례대로 게임판의 너비, 높이, 떨어지는 조각의 수다. 이어서 $N$개의 줄이 주어지고, 그중 $i$번째 줄에는 정수 $t_i$, $r_i$, $x_i$가 주어진다. 차례대로 $i$번째 조각의 종류, 회전, 가로 위치다. $x_i$는 조각이 게임판을 가로로 벗어나지 않도록 주어진다. 마지막 조각을 놓기 전에 게임이 끝나더라도 $N$개의 줄은 모두 주어진다.

각 테스트 케이스마다 먼저 "Case #i:"를 한 줄에 출력한다. $i$는 1부터 세는 테스트 케이스 번호다. 그다음, $N$개의 조각을 모두 놓기 전에 게임이 끝났으면 따옴표 없이 "Game Over!"를 출력한다. 그렇지 않으면 마지막 게임판을 $H$개의 줄에, 한 줄에 $W$개의 문자로 출력한다. 채워진 칸은 x로, 빈 칸은 .으로 나타낸다.

• $1 \le T \le 100$
• $4 \le W \le 20$
• $1 \le H \le 20$
• $0 \le N \le 100$
• $1 \le t_i \le 7$
• $0 \le r_i < 4$