Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
85 - ZOJ Monthly, December 2009 - G
Matrix Processing

Time Limit: 3 Seconds      Memory Limit: 32768 KB

Last time with your help, jay perfectly completed the troublesome task from moondy. Moondy was so surprised with jay's solution that she couldn't believe jay had made so great progress. She decided to give him another problem to verify her doubt and gave him one day to solve it.

This time she gave him a R*C matrix ( indexed from 1 ). There were two types of updates and one type of query:

  • type =0,r1,c1,r2,c2,k: add k to all integers from ( r1,c1 ) to ( r2,c2 ) in row order( see sample and hint. )
  • type =1,r1,c1,r2,c2,k: add k to all integers from ( r1,c1 ) to ( r2,c2 ) in column order.
  • type =2,r,c: query the current integer in ( r,c ) .

So easy? Naive jay began his endless trip in the matrix and soon fell asleep halfway. When he woke up, there were only four hours left! So now he has to ask you for help again.

Input

Input consists of multiple cases( <= 9 ) and terminates with end of file.

For each case, the first line contains two integer R and C ( 1 <= R,C <= 100 ). Then next R lines each with C integers show the R*C matrix ( all numbers in the matrix are between [1,100] ). Then an integer Q(1 <= Q <= 10^5 ) follows in a single line denoting the number of commands. Each command begins with an integer type ( 0 <= type <= 2 ), then follow five or two integers in the same line. It's garanteed all positions are legal and 1 <= k <= 100, and ( r2,c2 ) 's corresponding order is not less than ( r1,c1 ) 's.

There is a blank line between two consecutive cases.

Output

For each case, output "Case", one space, and case number ( based on 1 , see Samples ) in a line.

Then for each query, output the current integer in ( r,c ) in a line.

Sample Input

3 3
1 2 3
4 5 6
7 8 9
5
0 1 2 2 2 1
2 1 2
1 1 1 2 2 1
2 1 2
2 2 2

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

Sample Output

Case 1
3
4
7
Case 2
7

Hint ( of the first case )

At first, the matrix is:

1 2 3
4 5 6
7 8 9

The first command: add 1 from (1,2) to (2,2) in row order, that is, (1,2)->(1,3)->(2,1)->(2,2). The matrix becomes:

1 3 4
5 6 6
7 8 9

The second command: query (1,2), which is 3.

The third command: add 1 from (1,1) to (2,2) in column order ,that is, (1,1)->(2,1)->(3,1)->(1,2)->(2,2). The matrix becomes:

2 4 4
6 7 6
8 8 9

Then you can see (1,2) is 4 and (2,2) is 7.


Author: LI, Jie
Source: ZOJ Monthly, December 2009
Submit    Status