2D Array Range Add and Range Sum

Interview

Time limit3sMemory limit512 MB

Summary

Given an n by n matrix, apply all rectangle add updates in order, then print the sum of each rectangle query.

Level: Medium4 of 10
Topics: Matrix, Prefix sum
Solved: No attempts yet

Problem

You are given an integer 2D array $A$ of size $n \times n$ . The elements are $A[0][0], A[0][1], \ldots, A[n-1][n-1]$ . The initial values of all elements are given as input. Array $B$ stores $m$ queries on $A$ , and each query is one of two types. Type 1 is the first kind, and type 2 is the second kind.

1 $i_1$ $j_1$ $i_2$ $j_2$ $k$ : Add $k$ to every $A[i][j]$ with $i_1 \le i \le i_2$ and $j_1 \le j \le j_2$ .
2 $i_1$ $j_1$ $i_2$ $j_2$ : Output the sum of every $A[i][j]$ with $i_1 \le i \le i_2$ and $j_1 \le j \le j_2$ .

Process the queries in $B$ from the first to the $m$ -th in order, and output the results of the type 2 queries. All type 1 queries are stored before all type 2 queries in $B$ .

Input

The first line contains $n$ and $m$ , separated by a space. The next $n$ lines contain the elements of $A$ . The $j$ -th number on the $i$ -th line is $A[i-1][j-1]$ . The next $m$ lines each contain one query, given in order. The numbers in each line are separated by spaces.

Output

Print the results of the type 2 queries in order, one per line.

Constraints

$1 \le n \le 1000$ , $1 \le m \le 300000$
$1 \le A[i][j] \le 1000000$ ( $0 \le i, j \le n-1$ )
$B$ contains only type 1 and type 2 queries.
All type 1 queries are stored before all type 2 queries in $B$ .
$B$ contains at least one type 2 query.
$0 \le i_1 \le i_2 \le n-1$
$0 \le j_1 \le j_2 \le n-1$
$1 \le k \le 10000$

Examples1

Example 1

Input

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

Expected output

16
31
15