## Singularity Cup P4 - Staircase Sum

View as PDF

Points: 17 (partial)
Time limit: 3.5s
Memory limit: 256M

Author:
Problem type

Given an grid of integers , you will be asked to perform operations on it. Each operation is one of the following:

1. Update the integer at some to .
2. Query the "staircase sum" at some with height .

A "staircase sum" is defined as follows: starting at , get the sum of every column from to with the first column going from to and then descending by unit of height for each subsequent column.

More formally, the "staircase sum" at some is equivalent to .

You will be asked to answer of the operations described above. For each operation of type , output the desired result.

Operation 1

Operation 2

#### Input Specification

The first line of input contains integers , , and .

The next lines of input each contain space-separated integers representing .

The next lines of input each contain space-separated integers in the format 1 r c v or 2 r c h.

#### Output Specification

For each type operation, output the "staircase sum" of the grid after applying any previous type operations.

#### Sample Input

4 4 3
6 1 0 2
1 1 1 1
2 2 2 2
3 0 3 -3
1 4 2 7
2 1 1 1
2 4 2 3

#### Sample Output

6
12

#### Explanation for Sample

The result of the final operation is obtained by adding the numbers highlighted below: