K. Картинная галерея
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

В местной картинной галерее появилась новая художественная композиция, все картины которой написаны Светозаром. Композиция состоит из $$$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 4
4 5 3 8 3 10
6 4 5 7 5 10
1 2 7 6
2 1 2 10
1 1 1 1
2 3 8 20
Выходные данные
41
92
127
237