Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3055
WW's game

Time Limit: 1 Second      Memory Limit: 32768 KB

WW is fascinated by a new game lately: Magical puzzle.

This game is a kind of normal puzzlee with some new rules. The normal rules of puzzle game are like this:

First of all, the player are given a map with a lot of shells on it. They can choose to exchange two shells which are adjacent to each other. As soon as three or more shells have the same shape are located together, in a row or in a line, they are destroyed and will leave spaces on the map. Influenced by the gravity, the shells hanging in the air will fall to the spaces underneath them to occupy the spaces. Put the shells saved aside into the first column in order, then the second one, and so on. The player can get some points after destroying the shells. When the points accumulate to a certain score, the player will win.

The Magic Puzzle has new rules:

Different from the normal puzzle, the player can turn the whole column up or the whole row to the left to some degree when deal with the puzzle. For example, turn the fourth column up to four locations as the picture shows:

In the third picture, there are three purple and three green ones, so these six can be destroyed and the grids are marked. When every grid on the map is marked, the player wins.

Because this game is challenging, WW decided to study the key to win. Now you are given the original information and WW wants you to make a program to tell how many gridss of the map can be marked after taking the steps.

Notice that if some move cannot destroy any shell, the row/column of shells remain at the positions moved.


The first line is an integer T (T <= 10), which means there are T cases. For every case, the first line contains two integers n and m (1 <= n, m <= 10), which mean that the size of the map is n rows * m columns. The following n lines each contains m positive-integers, which describe the shells. You can make sure that initially there won't be three same shells in a row or in a column in the map. Then there will be a integer k (1 <= k <= 100) which stands for the steps you take. The following k lines each with 3 integers a b and c. If a equals to 1, it means to turn around the row; if a equals to 2, it means to turn around the column. b stands for the index for the row or the column to turn around. c stands for how many locations you are to turn. You can make sure all the moves are valid. There will be some more positive-integers which describe the shells added after destroying the original shells. You can make sure that they are enough during the game (and some of them may not be used). This part ends with a zero.


For each case, output a line which contains only one number, the number of marked grids.

Sample Input

4 5
1 2 4 3 1
1 3 2 1 3
2 1 3 2 3
3 3 2 1 1
1 3 1
1 2 3 2 1 4 3 3 3 1 2 4 3 2 1 0

Sample Output



The moves can only be operated when there're no three same shells in a row or in a column, else, all the shells match the rule will be destroyed, the grids will be marked, and new shells will be put into the spaces. Before filling out all the spaces, no shell-destroying will be done.

Shells can be used by different row or column, when the following condition occurs, all the five shells will be destroyed:


Author: WAN, Wei
Source: ZOJ Monthly, October 2008
Submit    Status