테트리스

테트리스는 거의 모든 사람이 해 본 유명한 비디오 게임이다. 이 문제에서는 이를 단순화한 버전을 시뮬레이션해야 한다.

이 버전의 게임은 중력이 작용하는 너비 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

이 단순화된 버전에서는 줄이 지워진 후에도 "공중에 떠 있는" 테트로미노 블록이 계속 떨어지지 않는다는 점에 유의한다. 따라서 가장 위쪽의 두 칸은 해당 위치에 그대로 남는다. 그러므로 원래 버전의 테트리스에서는 연쇄적으로 줄이 지워질 상황이더라도 여기서는 연쇄적으로 지워지지 않는다.

주어진 모든 테트로미노가 배치되거나, 필드의 높이 제한에 도달하여 현재 테트로미노를 배치할 수 없게 되면 게임이 끝난다.

이 문제에서는 각 테트로미노의 종류, 회전, 낙하 위치가 입력으로 주어진다. 테트로미노는 필드 위쪽에서 떨어지기 시작한다. 각 게임을 시뮬레이션하여 최종 결과를 구하는 것이 목표이다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1 GB. 1 <= T <= 100 1 <= $t_{i}$ <= 7 0 <= $r_{i}$ < 4

작은 데이터 세트(테스트 세트 1 - 공개)

4 <= W <= 20 1 <= H <= 20 0 <= N <= 100

큰 데이터 세트(테스트 세트 2 - 비공개)

4 <= W <= 100 1 <= H <= 100 0 <= N <= 5000

테트로미노의 종류는 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가 주어진다. 각 테스트 케이스에서 입력의 첫 줄에는 정수 3개 W, H, N이 주어진다. W는 너비, H는 높이이며, N은 떨어질 블록의 수이다.

이후 N개의 줄이 주어지며, 각 줄에는 정수 3개 $t_{i}$, $r_{i}$, $x_{i}$가 주어진다. $t_{i}$는 테트로미노의 종류를 나타낸다. $r_{i}$은 이 테트로미노의 회전이다. $x_{i}$은 이 테트로미노의 수평 낙하 위치이다. $x_{i}$에 따라 테트로미노가 수평 방향으로 필드 내부에 놓임이 보장된다.

각 테스트 케이스마다 먼저 "Case #i:"을 포함하는 한 줄을 출력한다. 여기서 i는 테스트 케이스 번호이며 1부터 시작한다. 그다음 N개의 블록이 모두 배치되기 전에 게임이 끝나면 "Game Over!"(따옴표 제외)을 출력한다. 그렇지 않으면 게임 필드의 최종 상태를 출력한다. 이는 H개의 줄로 이루어져야 하며, 각 줄에는 W개의 문자가 있어야 한다. 각 문자는 '.' 또는 'x'일 수 있다.