28876번 - Тренировки Тора 다국어

После того, как Тор открыл в себе новые способности, позволяющие ему еще лучше повелевать молниями и громом, он решил тренировать эти навыки. Для тренировки он выбрал прямоугольное поле и мысленно разбил его на $n$ равных строк и $m$ равных столбцов, тем самым получив клетчатое поле $n \times m$. Разряд молний он решил направлять в виде контуров прямоугольников --- для любых $1 \le x_1 \le x_2 \le n$ и $1 \le y_1 \le y_2 \le m$, он может поразить разрядом молнии клетки $(x_1, y_1), (x_1, y_1 + 1), \ldots, (x_1, y_2), (x_1 + 1, y_2), \ldots, (x_2, y_2), (x_2, y_2 - 1), \ldots, (x_2, y_1), (x_2 - 1, y_1), \ldots, (x_1 + 1, y_1)$.

Чтобы лучше понимать, куда направить молнию, Тору после каждого разряда нужно знать, сколько связных областей образуют непораженные молнией клетки поля. Тор называет область связной, если любые ее две клетки достижимы друг из друга переходами по вертикали и горизонтали, а также если область максимальна по включению.

Например, события могут развиваться следующим образом:

Сначала у Тора есть полностью непораженное поле $6 \times 6$.

Затем Тор поражает разрядом молнии контур прямоугольника $(1, 1), (5, 4)$ и связанных областей становится $2$.

Затем он поражает молнией контур прямоугольника $(3, 2), (6, 5)$ и связанных областей становится $4$.

Финальным разрядом Тор поражает вырожденный прямоугольник $(2, 6), (4, 6)$ и количество связанных областей становится равным $5$.

На вычисления руками у Тора нет времени, поэтому он попросил вас помочь ему с этой задачей.

В первой строке содержатся три числа $n$, $m$ и $q$ --- размеры клетчатого поля и количество разрядов молний, выпущенных Тором ($1 \le n, m, q \le 10^3$).

В следующих $q$ строках содержатся описания разрядов молний, выпущенных Тором. Описание состоит из $4$ чисел $x_1, y_1, x_2, y_2$ --- левого верхнего и правого нижнего углов прямоугольника ($1 \le x_1 \le x_2 \le n, 1 \le y_1 \le y_2 \le m$).

В $q$ строках выведите ответы на запросы --- $i$-е число соответствует количеству связных областей, которые образуют непораженные молнией клетки, после $i$-го разряда молнии.