Submatrix Queries: Sum & Maximum

You are given an m × n matrix of integers and Q queries. Each query requires you to compute either the sum or the maximum value of a submatrix defined by its top-left and bottom-right coordinates (1-indexed).

Each query is in one of the following forms:

• S x₁ y₁ x₂ y₂: Compute the sum of all elements in the submatrix from (x₁, y₁) to (x₂, y₂).
• M x₁ y₁ x₂ y₂: Find the maximum value in the submatrix from (x₁, y₁) to (x₂, y₂).

The boundaries of the submatrix satisfy the following conditions:

$$1 \le x_1 \le x_2 \le m \quad \text{and} \quad 1 \le y_1 \le y_2 \le n.$$

Print the answer for each query on a new line.

Example:

Input:
3 3
1 2 3
4 5 6
7 8 9
5
S 1 1 2 2
M 1 1 3 3
S 2 2 3 3
M 1 2 2 3
S 1 1 3 3
Output:
12
9
28
6
45

</p>

inputFormat

The first line contains two integers m and n, representing the number of rows and columns of the matrix, respectively.

The following m lines each contain n space-separated integers representing the matrix rows.

The next line contains an integer Q, the number of queries.

Each of the next Q lines contains a query in the format:

[type] x1 y1 x2 y2

where type is either S for sum or M for maximum.

outputFormat

For each query, print a single line containing the result. For sum queries, print the submatrix sum; for maximum queries, print the maximum element in the submatrix.

## sample

3 3
1 2 3
4 5 6
7 8 9
5
S 1 1 2 2
M 1 1 3 3
S 2 2 3 3
M 1 2 2 3
S 1 1 3 3

12
9
28
6
45

</p>