Grid Update and Query

You are given an ( n \times m ) grid initially filled with zeros. Your task is to perform two types of operations on the grid:

1. Update operation (denoted by U) which increases the value of every element in the sub-grid specified by the top-left corner ( (x_1, y_1) ) and the bottom-right corner ( (x_2, y_2) ) by a given integer ( val ).

2. Query operation (denoted by Q) which calculates the sum of all elements in the sub-grid specified by the top-left corner ( (x_1, y_1) ) and the bottom-right corner ( (x_2, y_2) ).

For a query operation, the sum is defined as: [ S = \sum_{i=x_1}^{x_2} \sum_{j=y_1}^{y_2} grid[i][j] ]

The input will be provided from the standard input (stdin) and the output should be printed to the standard output (stdout). Make sure your solution is correct and efficient for all provided test cases.

inputFormat

The input begins with a line containing two space-separated integers ( n ) and ( m ) (the number of rows and columns of the grid). The next line contains an integer ( k ) representing the number of operations. Each of the following ( k ) lines describes an operation:

• For an update operation: a line in the format U x1 y1 x2 y2 val, where ( (x1, y1) ) is the top-left coordinate, ( (x2, y2) ) is the bottom-right coordinate, and ( val ) is the value to add.
• For a query operation: a line in the format Q x1 y1 x2 y2, where ( (x1, y1) ) and ( (x2, y2) ) specify the sub-grid over which the sum is computed.

outputFormat

For each query operation in the order they appear, output the computed sum on a new line.## sample

4 5
5
U 1 1 3 3 2
Q 1 1 2 2
U 2 2 4 4 3
Q 2 2 3 3
Q 1 1 4 5

8
20
45