#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

Rafiki Island (RI) is actually made out of ice blocks that form a parallelogram that slants towards the right, as shown below. As such, RI's shape is always a nice, perfect parallelogram.

However, due to global warming, the ice thickness on RI has fluctuated quite a lot. For example, if the sun shines on just one spot of the parallelogram, then that spot will decrease in thickness. If the cloud blocks the sun so that it doesn't shine on that spot, then that spot will increase in thickness.

Based on the thickness, the penguins have come up with a danger rating of each block (how likely it is to fall apart). Now, the penguins want to hold one-day events on specific areas of the parallelogram.

When they hold events, they will look at certain co-ordinates and want to find out what is the sum of the danger ratings. The space that they are looking for must either be a rectangle or a parallelogram in the same direction (i.e. pointing to the right, sides must have gradient of -1). If not, they will not be able to conduct the all important Great Guin rituals, required at any major penguin event.

Your task is to create a program that will help the penguins determine the total danger rating of the area in their operations on Rafiki Island at each time. This is so that the penguins can complete their tiresome paperwork, filling in the Risk Assessment Management System forms with much greater ease.

In your program, there are two actions that can be carried out:

Update: update an element within the parallelogram to another value (This happens when Global Warming changes one of the cell of the parallelogram to a different thickness, and hence a different danger rating).

Query: find the sum of the danger ratings in the area bounded by either a rectangle or a parallelogram in the same direction (facing leftward, sides must have gradient of -1).

An example is shown below:

RI has height of 6 and width of 4 and the different danger ratings are shown below:

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
---|---|---|---|---|---|---|---|---|---|

0 | 1 | 2 | 3 | 4 | |||||

1 | 2 | 3 | 4 -> 6 | 5 | |||||

2 | 3 | 4 | 5 | 6 | |||||

3 | 4 | 5 | 6 | 7 | |||||

4 | 5 | 6 | 7 | 8 | |||||

5 | 1 -> 6 | 7 | 8 | 9 |

A rectangle query of (5,4) (5,5) (7,4) (7,5) initially gives the answer of 1 + 7 + 8 + 6 + 7 + 8 = 37.

A parallelogram query of (4,1) (5,2) (3,2) (2,1) would give the answer of 3 + 4 + 5 + 4 + 5 + 6 = 27.

Then I can update the value of (5,5) to be 6. (The sun shines on it and it gets thinner, making it more dangerous.)

After the update, a rectangle query of (5,4) (5,5) (7,4) (7,5) would then give the answer of 6 + 7 + 8 + 6 + 7 + 8 = 42.

For a query that does not fit in the two categories above such as (2,1) (2,2) (4,4) (4,3), output "Cannot query.".

I can further update the value of (3,1) to be 6 instead. (The sun shines on it and it gets thinner, making it more dangerous.)

A parallelogram query of (4,1) (5,2) (3,2) (2,1) would now give the answer of 3 + 4 + 5 + 6 + 5 + 6 = 29.

## Input

The first line contains the height and ** h** width

**of the parallelogram.**

*w*The next ** h** lines contains the diamond in the input order shown above.

The next line contains the number of actions to be taken, ** a**.

The next ** a** lines first contain a character 'U' or 'Q'.

On the same line, if the character is 'U', there will be two integers representing the co-ordinates of the cell to be updated (x, y), followed by an integer which is the new integer to fill the place of the cell.

On the same line, if the character is 'Q', there will be four pairs of integers (a total of eight integers) representing the sides of the parallelogram/rectangle that one wants to query the sum.

## Output

For a 'U' query, one need not output anything. You are given that all co-ordinates given will be valid.

For a 'Q' query, if one cannot find the query because the shape is not there, output "Cannot query.", else output the sum of the required query. You are given that all co-ordinates given will be valid.

## Limits

For 10% of the test cases, 1 ≤ ** h** ≤ 10, 1 ≤

**≤ 10, 1 ≤**

*w***≤ 10, and all queries will be rectangle queries, and there will be no "update" action.**

*a*For 30% of the test cases, 1 ≤ ** h** ≤ 10, 1 ≤

**≤ 10, 1 ≤**

*w***≤ 1000, all queries are rectangles, but there will be at most 5 "update" actions.**

*a*For 50% of the test cases, 1 ≤ ** h** ≤ 20, 1 ≤

**≤ 20, 1 ≤**

*w***≤ 10000, queries can be rectangles and parallelograms and there are at most 10 "update" actions.**

*a*For 100% of the test cases, 1 ≤ ** h** ≤ 70, 1 ≤

**≤ 70, 1 ≤**

*w***≤ 100000, you are given that there will be only at most 15 'U' actions. The rest will be 'Q' actions.**

*a*## Sample Input

6 4 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 5 6 7 8 1 7 8 9 7 Q 5 4 5 5 7 4 7 5 Q 4 1 5 2 3 2 2 1 U 5 5 6 Q 5 4 5 5 7 4 7 5 Q 2 1 2 2 4 4 4 3 U 3 1 6 Q 4 1 5 2 3 2 2 1

## Sample Output

37 27 42 Cannot query. 29

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 10 | 1s | 32MB | Average |

2 | 0 | 1 | 1s | 32MB | Average |

### Judge Compile Command

g++-7 ans.cpp -o ice -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512