Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2762
New Diamond

Time Limit: 10 Seconds      Memory Limit: 32768 KB

The game Diamond is a very famous game. I know many girls like to play this game in their spare time. In this problem, you will meet with a new Diamond game.

On the table, there are m rows by n columns colorful diamonds. Each step you can exchange two diamonds next to each other if and only if they have different colors. The score of this exchange is equal to the area of the rectangle with the maximum area formed by the exchange. (Please see the Sample Input and output.) Different from the old game, no diamond disappear after the exchange. You task is to calculate the score for each exchange.

Input

The first line have two integers m and n. (1 <= m, n <= 500). Then it is the diamonds matrix. Every element of the matrix has a integer(1��5) stands for the color of the diamond.

Then there is an integer p (1<=p<=1000), the number of exchanges. Then p lines followed. Each line has four integers x1 y1 x2 y2 indicate the coordinate of the two diamonds. The top left corner is (1, 1); the bottom right corner is (n, m).

You can safely assume that all the exchanges are legitimate.

Output

For each case, the first line output ��Case X:�� (X starts from 1).

Then p lines followed. Each line output the score of that exchange.

Please use scanf() and printf() for this problem.

Sample Input

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

Sample Output

Case 1:
9
1
Case 2:
10

Hint

In case 1, the first exchange forms two rectangles: the rectangle of color 1 has area 9; the rectangle of color 2 has area 4, so the score is the greater one. The second exchange two area 1 rectangles. Although there are other rectangles of color 3 and 4 on the table, they are not formed by this exchange. In case 2, the exchange formed many rectangles; the score is the maximum area one.


Author: XUE, Zaiyue
Source: ZOJ Monthly, September 2006
Submit    Status