Description

“Minute 1: X said, let there be a matrix, and so there was an $n\times m$ matrix filled with $0$.

Minute 2: L said, let it support modifications, and so there was an operation that adds a value to all numbers in a rectangular region whose top-left corner is $(a,b)$ and bottom-right corner is $(c,d)$.

Minute 3: k said, let it support queries, and so there was an operation that computes the sum of all numbers in a given rectangular region.

Minute 4: Rainbow Meow said, it should be based on a data structure related to binary trees, and so there were the Constraints.

Minute 5: Hexue said, be patient, and so there was a time limit.

Minute 6: The piano-eating guy said, save some trouble, and so there was a restriction that during the operations and in the final result, everything will not exceed the range of a 32-bit signed integer type.

Minute 7: This problem was finally completed. However, the godlike problem setters no longer wanted to write the program for it.”.

— “Seven Minutes of God Making a Naked Problem”.

So this sacred task is handed over to you.

Input Format

The first line of the input is X n m, indicating that the matrix size is $n\times m$.
From the second line to the end of the file, each line contains one of the following two operations:

• L a b c d delta — add $delta$ to all numbers in the rectangular region with vertices $(a,b)$ and $(c,d)$.
• k a b c d — compute the sum of all numbers in the rectangular region with vertices $(a,b)$ and $(c,d)$.

Note that $k$ is lowercase.

Output Format

For each k operation, output the answer on a separate line.

X 4 4
L 1 1 3 3 2
L 2 2 4 4 1
k 2 2 3 3

12

Hint

For $10\%$ of the testdata, $1 \le n \le 16$, $1 \le m \le 16$, and there are no more than $200$ operations.

For $60\%$ of the testdata, $1 \le n \le 512$, $1 \le m \le 512$.

For $100\%$ of the testdata, $1 \le n \le 2048$, $1 \le m \le 2048$, $-500 \le delta \le 500$, and there are no more than $2\times 10^5$ operations. It is guaranteed that the final results do not exceed the range of a 32-bit signed integer type, but it is not guaranteed that intermediate computations stay within this range.

Translated by ChatGPT 5