Farmer Juan is a barista

Interview

Time limit2sMemory limit512 MB

Summary

Maintain a grid under range-add rectangle updates and point queries, answering each point query using only earlier updates.

Level: Medium6 of 10
Topics: Prefix sum, Matrix, Implementation, Array
Solved: No attempts yet

Problem

Juan is a barista and he also runs a coffee farm. The farm is an $N \times M$ grid, the $x$ coordinate runs from $1$ to $N$ , and the $y$ coordinate runs from $1$ to $M$ . Juan performs $Q$ operations in the order they are given, and each operation is one of these two.

Plant seeds: plant one seed of nutrition $d$ on every cell whose $x$ coordinate lies in $[x_1, x_2]$ and whose $y$ coordinate lies in $[y_1, y_2]$ .
Check nutrition: report the sum of the nutrition of the seeds planted on cell $(x, y)$ .

A check reflects only the planting operations that come before it. A cell with no seed yet answers $0$ . Write the program that manages Juan's farm.

Input

The first line contains $N$ , $M$ , and $Q$ . ( $1 \le N, M \le 5000$ , $0 \le Q \le 2 \times 10^5$ )

Each of the next $Q$ lines contains one operation.

If the first number on the line is $1$ , the operation plants seeds and five numbers $x_1$ , $y_1$ , $x_2$ , $y_2$ , $d$ follow. ( $1 \le x_1 \le x_2 \le N$ , $1 \le y_1 \le y_2 \le M$ , $-10^9 \le d \le 10^9$ )

If the first number on the line is $2$ , the operation checks nutrition and two numbers $x$ and $y$ follow. ( $1 \le x \le N$ , $1 \le y \le M$ )

Output

For every check operation, print its result on its own line, in the order the operations are given.

Examples3

Example 1
Input
```
3 5 2
1 1 1 3 5 2
2 3 3
```
Expected output
```
2
```

Example 2

Input

4 4 9
2 2 2
1 1 1 2 2 5
2 2 2
2 3 3
1 2 2 4 4 -3
2 2 2
2 4 4
1 1 1 4 4 10
2 1 1

Expected output

Example 3

Input

1 1 5
1 1 1 1 1 1000000000
1 1 1 1 1 1000000000
2 1 1
1 1 1 1 1 -1000000000
2 1 1

Expected output

2000000000
1000000000