2D Range Sum Query with Updates

You are given a 2D matrix and a series of queries. The queries are of two types:

• update r c val: Update the element at row r and column c to the new value val.
• sumRegion r1 c1 r2 c2: Return the sum of the rectangular submatrix defined by the top-left corner (r1, c1) and the bottom-right corner (r2, c2).

Your task is to implement a data structure that supports both operations efficiently. Under the hood, you might consider using a Binary Indexed Tree (Fenwick Tree) for 2D range queries. The update and sum operations should work in \(O(\log m \cdot \log n)\) time, where \(m\) and \(n\) refer to the number of rows and columns, respectively.

Input Format and Output Format details are provided below.

inputFormat

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

The next m lines each contain n integers representing the initial matrix.

The following line contains an integer q, the number of queries.

Each of the next q lines contains a query in one of the following formats:

• update r c val
• sumRegion r1 c1 r2 c2

Note: Rows and columns are zero-indexed.

outputFormat

For each sumRegion query, output the resulting sum on a new line.

## sample

5 5
3 0 1 4 2
5 6 3 2 1
1 2 0 1 5
4 1 0 1 7
1 0 3 0 5
5
sumRegion 2 1 4 3
update 3 2 2
sumRegion 2 1 4 3
update 0 0 2
sumRegion 0 0 1 1

8
10
13

</p>