| The 2026 ICPC Belarus Qualification |
|---|
| Закончено |
В местной картинной галерее появилась новая художественная композиция, все картины которой написаны Светозаром. Композиция состоит из $$$n \cdot m$$$ картин, упорядоченных в виде решётки из $$$n$$$ строк и $$$m$$$ столбцов с картинами. Картина в строке $$$i$$$ и столбце $$$j$$$ имеет высоту $$$h_{i,j}$$$ и ширину $$$w_{i,j}$$$ сантиметров.
Злой маг Arglwyddytywyllwch уже строит планы на эти картины. Каждый день он приходит в галерею и мечтает о том, как композиция окажется в его замке. Замысел таков: он хочет обрезать некоторые картины (то есть уменьшить их высоту и/или ширину, оставляя их прямоугольными) так, чтобы:
Это делается для того, чтобы все картины можно было склеить в одно большое полотно без пробелов. Впрочем, какова художественная ценность такого полотна, план умалчивает.
Разрешается не обрезать картины вообще, если условия уже выполнены. Поворачивать картины и менять их местами нельзя. При этом Arglwyddytywyllwch хочет минимизировать сумму площадей обрезков и интересуется, насколько мало обрезков может быть в принципе.
Каждый день Arglwyddytywyllwch приходит в галерею, и каждый день, по прихоти музы Светозара, одна из картин меняется на другую, самую новую. Найдите минимальную сумму площадей обрезков после каждой замены картины.
Отметим, что картины обрезаются лишь гипотетически, а вот замены картин вполне реальны и применяются последовательно друг за другом.
Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \leqslant n, m, k \leqslant 2 \cdot 10^5$$$, $$$n \cdot m \leqslant 2 \cdot 10^5$$$) — размеры композиции в картинах и количество дней.
Следующие $$$n$$$ строк содержат по $$$2m$$$ целых чисел. $$$i$$$-я из них содержит числа $$$h_{i,1}$$$, $$$w_{i,1}$$$, $$$h_{i,2}$$$, $$$w_{i,2}$$$, $$$\ldots$$$, $$$h_{i,m}$$$, $$$w_{i,m}$$$.
Далее следуют $$$k$$$ строк, описывающие замены картин. Каждая замена задаётся четырьмя целыми числами $$$x$$$, $$$y$$$, $$$h$$$, $$$w$$$ ($$$1 \leqslant x \leqslant n$$$, $$$1 \leqslant y \leqslant m$$$) и заменяет картину $$$(x, y)$$$ новой картиной размера $$$h \times w$$$.
Для всех размеров выполняется $$$1 \leqslant h, w \leqslant 10^6$$$.
Для каждой замены картины выведите одно целое число — минимальную суммарную площадь обрезков после этой замены.
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
| Название |
|---|


