Tetris Simulation

Tetris is a video game that many people have played. Here you simulate a version of it with simpler rules.

The field is $W$ columns wide and $H$ rows tall, and it starts empty. Columns are numbered $0$ to $W-1$ from left to right, and rows are numbered $0$ to $H-1$ from top to bottom. Tetrominoes fall one at a time, each starting entirely above the top of the field. A falling piece moves down one row at a time and stops as soon as one more row of movement would push part of it below the bottom row or onto a square that an earlier piece occupies. A piece never moves sideways and never rotates while it falls.

Right after a piece stops, every row that is completely filled is cleared. Several rows can be cleared at once. The cleared rows disappear, every row above them moves down by the number of cleared rows, and the same number of empty rows appears at the top. Here is an example, where o marks the piece that just stopped.

  |..............|      |..............|      |..............|
  |.............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 rows

In this simpler version, squares left hanging in the air after a clear do not fall any further. The two squares near the top keep their columns and only move down by the two cleared rows. Chain clears therefore never happen, even though the original game has them.

The game ends once all $N$ pieces are placed. It also ends early if a piece stops at a position where at least one of its squares is still above row $0$: the field is not tall enough for that piece, so the piece cannot be placed.

The type, the rotation and the horizontal position of every piece are given in the input. Simulate the play and report the final field.

There are 7 types of tetromino.

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

The rotation of a piece is an integer $r$ with $0 \le r < 4$. The shapes above are the shapes for $r = 0$, and each increase of $r$ by one turns the shape 90 degrees counterclockwise. The bounding box is taken again after every turn, so the shape for a given $r$ always sits tight against its own bounding box. The four rotations of type 7 and of type 1 look like this.

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

The horizontal position is an integer $x$. It is the column of the left edge of the piece's bounding box, so a piece whose bounding box is $w$ columns wide covers columns $x$ to $x + w - 1$.

The first line has the number of test cases $T$. Each test case starts with a line holding three integers $W$, $H$, $N$: the width of the field, its height, and the number of falling pieces. Then follow $N$ lines. The $i$-th of them holds three integers $t_i$, $r_i$, $x_i$: the type, the rotation and the horizontal position of the $i$-th piece. Every $x_i$ keeps its piece inside the field horizontally. All $N$ lines are given even when the game ends before the last piece.

For each test case, print one line holding "Case #i:", where $i$ is the number of the test case counting from 1. Then, if the game ended before all $N$ pieces were placed, print "Game Over!" without the quotes. Otherwise print the final field as $H$ lines of $W$ characters each, using x for an occupied square and . for an empty one.

• $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$