# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Problem - SMSMS

By ShockProof · Limits 2s, 512 MB

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

InputOutput
```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
``````

### Statistics

63% Solution Ratio

nazmulashaEarliest, Dec '17

rezaulhsagarFastest, 184714.7s

nazmulashaLightest, 6.7 MB

trojan_kingShortest, 3366B