Given a matrix of n rows and m columns you have to perform two types of queries on the matrix.
1) Calculate the SMSMS of the matrix.
2) Change the value of an element of the matrix.
Let us define SMSMS of a matrix. Given a matrix of n rows and m columns you have to store the elements of the matrix within a linear array in spiral order. The maximum contiguous sub-array summation of the linear array is the SMSMS of the given matrix.
For this problem an empty set is also a valid sub-array.
Input
The first line of the input contains an integer T (1<=T<=5) denoting the number of test cases.
The first line of a case contains three integers n,m,Q (1 ≤ n,m ≤ 300), Q (1 ≤ Q ≤ 100000). Each of the next n lines will contain m space separated integers forming the matrix. All the integers will be between -100000 and 100000.
Each of the next Q lines contains a task in one of the following form:
1 Calculate the the SMSMS of the matrix.
2 i j x Change the jth element of the ith row to x.Output
For each test case, print the case number first. If the query type is 1, then print the SMSMS of the matrix on a single line.
Sample
| Input | Output |
|---|---|
2 2 2 3 1 10 30 -20 1 2 2 2 -5 1 1 1 1 -4 1 | Case 1: 30 36 Case 2: 0 |
Given a Matrix
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
The spiral form of the matrix is
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 
