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 

    Discussion

    Statistics


    63% Solution Ratio

    nazmulashaEarliest, Dec '17

    rezaulhsagarFastest, 184714.7s

    nazmulashaLightest, 6.7 MB

    trojan_kingShortest, 3366B

    Submit

    Login to submit

    Related Contests

    Replay of Comilla University CSE Fiesta 2017 Ended at 2017-12-15 18:00:00 +0000 UTC