Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2411
Link Link Look

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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



Author: ZHENG, Jianqiang
Source: Zhejiang University Local Contest 2005
Submit    Status