# Practice on Toph

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

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

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.

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

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.

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

63% Solution Ratio

nazmulashaEarliest,

rezaulhsagarFastest, 184714.7s

nazmulashaLightest, 6.7 MB

trojan_kingShortest, 3366B

Login to submit