406833: GYM102566 J The Sacred Texts

Jimmy is not really the sharpest tool in the shed. For instance, he detests notebooks and enjoys writing on toilet paper rolls (for reasons we do not know and do not need to know). One day, while relaxing in his chair after eating an industrial amount of crispy strips, he came up with an idea for a game. So he pulled out his trusty toilet paper ("The Sacred Texts") and began writing what resembled a very long and not so wide matrix. But Jimmy needs a friend to play this game with and it would make him very happy if you would be the one.

Formally, you are given a matrix with $$$N$$$ rows ($$$1 \leq N \leq 10$$$) and $$$M$$$ columns ($$$1 \leq M \leq 100.000$$$) with integers ($$$-1.000.000.000 \leq v_{i,j} \leq 1.000.000.000$$$) and $$$Q$$$ queries ($$$1 \leq Q \leq 1.000$$$) of $$$2$$$ types :

• $$$1\ x\ y\ val$$$ ($$$1 \leq x \leq N$$$; $$$1 \leq y \leq M$$$; $$$-1.000.000.000 \leq val \leq 1.000.000.00$$$) - $$$v_{i,j}$$$ changes its value to $$$val$$$
• $$$2\ x1\ y1\ x2\ y2$$$ ($$$1 \leq x1 \leq x2 \leq N$$$; $$$1 \leq y1 \leq y2\leq M$$$) - find the maximum sum of a submatrix of the submatrix with the upper left corner equal to $$$(x1,\ y1)$$$ and the lower right corner equal to $$$(x2,\ y2)$$$.

The first line of the input contains two positive integers $$$N$$$ and $$$M$$$ that represent the number of rows and the number of columns of the matrix.

The next $$$N$$$ lines each contain $$$M$$$ integers describing rows of the matrix.

The next line contains one positive integer $$$Q$$$ that represents the number of queries.

The last $$$Q$$$ lines each contain a query of either type $$$1$$$ or $$$2$$$.

Print answers to queries of type $$$2$$$ in the order they appear in the input.

2 3
3 5 2
-1 -3 -1
3
2 1 1 2 3
1 2 2 3
2 1 1 2 2

10
10