테트리스 시뮬레이션

테트리스를 간단하게 바꾼 게임을 시뮬레이션한다.

게임판은 너비가 $W$, 높이가 $H$이고 아래쪽으로 중력이 작용한다. 처음에 게임판은 비어 있다. 테트로미노는 게임판 위쪽에서 하나씩 떨어지고, 다른 테트로미노나 게임판 바닥에 닿는 순간 그 자리에 멈춘다. 떨어지는 동안 테트로미노는 회전하지 않고 좌우로도 움직이지 않는다.

한 줄이 테트로미노로 가득 차면 그 줄은 곧바로 사라진다. 한 번에 여러 줄이 사라지기도 한다. 예를 들면 다음과 같다.

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

  Falling               Stopped               Cleared 2 lines

이 게임에서는 줄이 사라진 뒤에 공중에 뜬 칸이 더 내려오지 않는다. 그래서 위쪽의 두 칸이 그대로 남는다. 원래 테트리스와 달리 연쇄 삭제도 일어나지 않는다.

주어진 테트로미노를 모두 놓으면 게임이 끝난다. 게임판 높이가 모자라서 이번 차례의 테트로미노를 놓지 못해도 게임이 끝난다.

각 테트로미노의 종류, 회전, 떨어지는 가로 위치는 입력으로 주어진다. 테트로미노는 모두 게임판 위쪽에서 떨어지기 시작한다. 각 게임의 최종 상태를 구하라.

테트로미노는 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

테트로미노의 회전은 수 $r$로 나타내고, $r$는 0, 1, 2, 3 중 하나다. 회전 방향은 반시계 방향이다. 예를 들면 다음과 같다.

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$는 테트로미노를 감싸는 가장 작은 직사각형의 왼쪽 아래 칸의 좌표이고, 0부터 시작한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 정수 $W$, $H$, $N$이 주어진다. $W$는 게임판의 너비, $H$는 게임판의 높이, $N$은 떨어지는 블록의 개수다.

이어지는 $N$개 줄에는 정수 $t_i$, $r_i$, $x_i$가 주어진다. $t_i$는 테트로미노의 종류, $r_i$는 이 테트로미노의 회전, $x_i$는 이 테트로미노가 떨어지는 가로 위치다. $x_i$는 테트로미노가 가로 방향으로 게임판 안에 들어가도록 주어진다.

각 테스트 케이스마다 먼저 Case #i:를 한 줄에 출력한다. $i$는 테스트 케이스 번호이고 1부터 시작한다.

그 다음, $N$개를 모두 놓기 전에 게임이 끝났으면 따옴표 없이 Game Over!를 출력한다. 그렇지 않으면 게임판의 최종 상태를 $H$개 줄에 출력한다. 각 줄은 $W$개의 문자로 이루어지고, 각 문자는 . 또는 x다.

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