## USUBQSUB - Update Sub-Matrix & Query Sub-Matrix

Updating and querying 1 dimensional arrays is a popular question. How about updating and quering sub-matrices of a matrix?

A sub-matrix will be depicted as (a, b), (c, d). This implies that it will include all the cells (x, y) such that a<=x<=c and b<=y<=d.

The matrix is indexed from [1..N][1..N], where N is the size.

You are given a matrix of size NxN, with each element initially set to 0. There are M queries and each query can be of one of the two types:

1 x1 y1 x2 y2: This query asks you to return the sum of all the elements in the sub-matrix (x1, y1), (x2, y2).

2 x1 y1 x2 y2 K: This query asks you to add K to each element in the sub-matrix (x1, y1), (x2, y2).

### Input

The first line of input contains N, M.

The next M lines contain queries in the same forms as stated above.

You may assume that x1<=x2 and y1<=y2 for all queries.

Also N<=1000 and M<=10^{5}. K<=10^{9}

### Output

The answer to all the queries wherein you need to return the sum of elements in the sub-matrix, i.e., all the queries of type 1.

### Sample Test Case

Input:5 5

2 2 2 4 4 4

1 1 1 3 3

2 5 5 5 5 3

1 1 1 1 2

1 2 2 5 3Output:16

0

24Note:Please be careful with certain languages as the output may exceed the range of the data type used to store it.

Please use 64-bit integers to store the results. For example, long long in C/C++.

Added by: | Pushkar Mishra |

Date: | 2013-09-11 |

Time limit: | 1s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM64 |

Resource: | Own |