A new artistic composition has appeared in the local art gallery; all of its paintings were painted by Svetozar. The composition consists of $$$n \cdot m$$$ paintings arranged in a grid of $$$n$$$ rows and $$$m$$$ columns of paintings. The painting in row $$$i$$$ and column $$$j$$$ has height $$$h_{i,j}$$$ and width $$$w_{i,j}$$$ centimeters.
The evil mage Arglwyddytywyllwch is already making plans for these paintings. Every day he comes to the gallery and dreams of the composition ending up in his castle. The idea is as follows: he wants to crop some of the paintings (that is, decrease their height and/or width, keeping them rectangular) so that:
This is done so that all paintings can be glued into one large canvas with no gaps. The plan is silent on the artistic value of such a canvas.
It is allowed not to crop the paintings at all if the conditions are already satisfied. Rotating the paintings and swapping them is forbidden. At the same time, Arglwyddytywyllwch wants to minimize the total area of the scraps and is interested in how small the scraps can be in principle.
Every day Arglwyddytywyllwch comes to the gallery, and every day, at the whim of Svetozar's muse, one of the paintings is replaced with another, the newest one. Find the minimum total area of scraps after each painting replacement.
Note that the paintings are cropped only hypothetically, whereas the replacements are quite real and are applied sequentially one after another.
The first line contains integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \leq n, m, k \leq 2 \cdot 10^5$$$, $$$n \cdot m \leq 2 \cdot 10^5$$$): the dimensions of the composition in paintings and the number of days.
The next $$$n$$$ lines contain $$$2m$$$ integers each. The $$$i$$$-th of them contains the integers $$$h_{i,1}$$$, $$$w_{i,1}$$$, $$$h_{i,2}$$$, $$$w_{i,2}$$$, $$$\ldots$$$, $$$h_{i,m}$$$, $$$w_{i,m}$$$.
Then, $$$k$$$ lines describing the painting replacements follow. Each replacement is given by integers $$$x$$$, $$$y$$$, $$$h$$$, $$$w$$$ ($$$1 \leq x \leq n$$$, $$$1 \leq y \leq m$$$) and replaces the painting $$$(x, y)$$$ with a new painting of size $$$h \times w$$$.
All sizes satisfy $$$1 \leq h, w \leq 10^6$$$.
For each painting replacement, print an integer: the minimum total area of scraps after this replacement.
2 3 44 5 3 8 3 106 4 5 7 5 101 2 7 62 1 2 101 1 1 12 3 8 20
41 92 127 237