###### 编程介的小学生
2017-03-21 14:39

A single player game is played on a grid chessboard with some colored beads on. In each round, the player can click on two grids of the chessboard. If the two grids both have beads of the same color, and a line with no more than two turns could be drawn to connect the two beads, the two beads will both disappear from the chessboard. Note that the line must not pass through any other beads.

Figure 1: Valid clicks that will erase the two beads
Given the information of a chessboard and the player's clicks in each round, you are required to calculate how many beads will disappear.

Input
The input consists of several test cases. The first line of each case contains two numbers N and M (1 <= N, M <= 100), indicating the dimensions of the chessboard. Then N lines follow, each represents a row of the chessboard. The positive numbers represent different colors of beads, and zero represents an empty grid. Then there is a positive number T followed by T lines of input which describe the clicks of all T rounds. Each line contains four numbers x1, y1, x2, y2 which are the positions (x1, y1) and (x2, y2) of the two clicks on the chessboard (the north-west corner is at (1, 1)).

Output

For each case, print in one line the number of beads disappeared.

Sample Input

3 4
1 1 2 2
3 3 4 4
2 2 1 1
6
1 1 1 2
1 3 1 4
2 1 2 2
2 3 2 4
3 1 3 2
3 3 3 4

3 4
1 2 1 2
3 4 3 4
2 1 2 1
6
1 1 1 2
1 3 1 4
2 1 2 2
2 3 2 4
3 1 3 2
3 3 3 4

3 4
1 2 1 2
1 1 2 2
2 2 1 1
3
2 3 2 4
2 2 3 3
3 2 1 4

2 3
0 0 0
0 0 0
2
1 1 1 1
1 1 1 2

0 0

Sample Output

12
0
6
0

• 写回答
• 好问题 提建议
• 追加酬金
• 关注问题
• 邀请回答