2D Array Multi-Update Single Sum

You are given an integer 2D array $A$ of size $n \times n$. The elements of $A$ are $A[0][0], A[0][1], \ldots, A[n-1][n-1]$. The initial value of every element of $A$ is given in the input. You are also given an array $B$ that stores $m$ queries on $A$. Each query in $B$ is one of two types. Type 1 is written first, and type 2 is written second.

• 1 $i_1$ $j_1$ $i_2$ $j_2$ $k$: Add $k$ to every $A[i][j]$ where $i_1 \le i \le i_2$ and $j_1 \le j \le j_2$.
• 2 $i_1$ $j_1$ $i_2$ $j_2$: Print the sum of every $A[i][j]$ where $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 print the result of the type 2 query. Note that $B$ contains only one type 2 query, and it is the last one.

The first line contains $n$ and $m$, separated by a space.

Each of the next $n$ lines contains the elements of $A$. The $j$-th number on the $i$-th line is $A[i-1][j-1]$.

Each of the next $m$ lines contains one query. The numbers of a query are separated by spaces.

Print the result of the type 2 query on the first line.

• $1 \le n \le 1{,}000$, $1 \le m \le 300{,}000$
• $1 \le A[i][j] \le 1{,}000{,}000$ ($0 \le i, j \le n-1$)
• $B$ contains only queries of type 1 and type 2.
• $B$ contains exactly one type 2 query, and it is the last 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 10{,}000$