Codeforces 390 E. Inna and Large Sweet Matrix-布布扣-bubuko.com

Inna loves sweets very much. That‘s why she wants to play the "Sweet Matrix" game with Dima and Sereja. But Sereja is a large person, so the game proved small for him. Sereja suggested playing the "Large Sweet Matrix" game.

The "Large Sweet Matrix" playing field is an n?×?m matrix. Let‘s number the rows of the matrix from 1 to n, and the columns — from 1 tom. Let‘s denote the cell in the i-th row and j-th column as (i,?j). Each cell of the matrix can contain multiple candies, initially all cells are empty. The game goes in w moves, during each move one of the two following events occurs:

Sereja chooses five integers x1,?y1,?x2,?y2,?v (x1?≤?x2,?y1?≤?y2) and adds v candies to each matrix cell (i,?j) (x1?≤?i?≤?x2; y1?≤?j?≤?y2).
Sereja chooses four integers x1,?y1,?x2,?y2 (x1?≤?x2,?y1?≤?y2). Then he asks Dima to calculate the total number of candies in cells(i,?j) (x1?≤?i?≤?x2; y1?≤?j?≤?y2) and he asks Inna to calculate the total number of candies in the cells of matrix (p,?q), which meet the following logical criteria: (p?<?x1 OR p?>?x2) AND (q?<?y1 OR q?>?y2). Finally, Sereja asks to write down the difference between the number Dima has calculated and the number Inna has calculated (D - I).

Unfortunately, Sereja‘s matrix is really huge. That‘s why Inna and Dima aren‘t coping with the calculating. Help them!

Input

The first line of the input contains three integers n, m and w (3?≤?n,?m?≤?4·106; 1?≤?w?≤?105).

The next w lines describe the moves that were made in the game.

A line that describes an event of the first type contains 6 integers: 0, x1, y1, x2, y2 and v (1?≤?x1?≤?x2?≤?n; 1?≤?y1?≤?y2?≤?m; 1?≤?v?≤?109).
A line that describes an event of the second type contains 5 integers: 1, x1, y1, x2, y2 (2?≤?x1?≤?x2?≤?n?-?1; 2?≤?y1?≤?y2?≤?m?-?1).

It is guaranteed that the second type move occurs at least once. It is guaranteed that a single operation will not add more than 109candies.

Be careful, the constraints are very large, so please use optimal data structures. Max-tests will be in pretests.

Output

For each second type move print a single integer on a single line — the difference between Dima and Inna‘s numbers.

Sample test(s)

input
4 5 5
0 1 1 2 3 2
0 2 2 3 3 3
0 1 5 4 5 1
1 2 3 3 4
1 3 4 3 4

output
2
-21

Note

Note to the sample. After the first query the matrix looks as:

After the second one it is:

After the third one it is:

For the fourth query, Dima‘s sum equals 5 + 0 + 3 + 0 = 8 and Inna‘s sum equals 4 + 1 + 0 + 1 = 6. The answer to the query equals 8 - 6 = 2. For the fifth query, Dima‘s sum equals 0 and Inna‘s sum equals 18 + 2 + 0 + 1 = 21. The answer to the query is 0 - 21 = -21.

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long int LL; const int maxn=4000400; int n,m,w,nm; LL B[2][maxn],C[2][maxn]; int lowbit(int x) { return x&(-x); } void add_b(int id,int p,LL v) { for(int i=p;i;i-=lowbit(i)) B[id][i]+=v; } void add_c(int id,int p,LL v) { for(int i=p;i<=nm;i+=lowbit(i)) C[id][i]+=v*p; } LL sum_b(int id,int p) { LL sum=0; for(int i=p;i<=nm;i+=lowbit(i)) sum+=B[id][i]; return sum; } LL sum_c(int id,int p) { LL sum=0; for(int i=p;i;i-=lowbit(i)) sum+=C[id][i]; return sum; } void ADD(int id,int l,int r,LL v) { add_b(id,r,v); add_c(id,r,v); if(l-1) { add_b(id,l-1,-v); add_c(id,l-1,-v); } } LL sUm(int id,int p) { if(p) return sum_b(id,p)*p+sum_c(id,p-1); else return 0; } LL SUM(int id,int l,int r) { return sUm(id,r)-sUm(id,l-1); } int main() { scanf("%d%d%d",&n,&m,&w); nm=max(n,m)+10; while(w--) { int c,x1,x2,y1,y2,v,dx,dy; scanf("%d%d%d%d%d",&c,&x1,&y1,&x2,&y2); dx=x2-x1+1;dy=y2-y1+1; if(c==0) { scanf("%d",&v); ADD(0,x1,x2,v*dy); ADD(1,y1,y2,v*dx); } else { printf("%I64d\n",SUM(1,y1,y2)-SUM(0,1,x1-1)-SUM(0,x2+1,nm)); } } return 0; }