This page is still under construction.

Parts of this page are still being built. What you see may change.

Rectangle update and rectangle sum

Time limit1sMemory limit256 MB

Summary
You add w to all cells in one rectangle per update and print the cell sum of one rectangle per query in order.
Level

Medium7 of 10

Topics
Segment tree, Prefix sum, Matrix
Solved
No attempts yet

Problem

You have an N×MN \times M grid. Rows are numbered 1 to NN from bottom to top, columns are numbered 1 to MM from left to right, and every cell starts at 0. Cell (i,j)(i, j) is the cell where row ii meets column jj.

Process QQ operations on the grid, in the order given.

1 a b x y w: add ww to every cell of the rectangle whose bottom left cell is (a,b)(a, b) and whose top right cell is (x,y)(x, y).

2 a b x y: print the sum of every cell of the rectangle whose bottom left cell is (a,b)(a, b) and whose top right cell is (x,y)(x, y).

Input

The first line holds NN, MM, and QQ, separated by spaces. Each of the next QQ lines holds one operation in the format above.

1≤N,M≤10001 \le N, M \le 1000 and 1≤Q≤1000001 \le Q \le 100000. Every operation satisfies 1≤a≤x≤N1 \le a \le x \le N and 1≤b≤y≤M1 \le b \le y \le M, and ww in an operation of type 1 is an integer with 1≤w≤10001 \le w \le 1000.

Output

For each operation of type 2, print the sum on its own line, in input order. A sum can exceed the range of a 32-bit integer.

Examples7

  1. Example 1

    Input
    2 3 8
1 1 1 1 1 5
1 1 1 1 2 5
2 1 2 1 3
1 1 1 2 1 4
2 2 1 2 2
2 1 2 1 3
1 2 1 2 2 5
2 1 1 1 1
    Expected output
    5
4
5
14

  2. Example 2

    Input
    1 1 5
2 1 1 1 1
1 1 1 1 1 7
2 1 1 1 1
1 1 1 1 1 1000
2 1 1 1 1
    Expected output
    0
7
1007

  3. Example 3

    Input
    4 5 6
2 1 1 4 5
1 2 2 3 4 3
2 1 1 4 5
2 2 2 3 4
2 1 1 1 1
2 3 4 4 5
    Expected output
    0
18
18
0
3

  4. Example 4

    Input
    3 3 9
1 1 1 3 3 1
1 2 2 3 3 2
1 3 3 3 3 4
2 1 1 3 3
2 2 2 3 3
2 3 3 3 3
1 1 1 1 3 10
2 1 1 1 3
2 1 1 3 3
    Expected output
    21
16
7
33
51

  5. Example 5

    Input
    1 10 8
1 1 1 1 10 2
2 1 1 1 10
1 1 3 1 7 5
2 1 3 1 7
2 1 1 1 2
1 1 5 1 5 100
2 1 5 1 5
2 1 1 1 10
    Expected output
    20
35
4
107
145

  6. Example 6

    Input
    10 1 8
1 1 1 10 1 2
2 1 1 10 1
1 3 1 7 1 5
2 3 1 7 1
2 1 1 2 1
1 5 1 5 1 100
2 5 1 5 1
2 1 1 10 1
    Expected output
    20
35
4
107
145

  7. Example 7

    Input
    5 5 7
1 1 1 5 5 4
1 2 3 4 4 6
2 1 1 5 5
2 1 1 2 5
2 3 1 5 5
2 1 1 5 2
2 1 3 5 5
    Expected output
    136
52
84
40
96