Background

This problem is translated from XXVIII Olimpiada Informatyczna – Stage I Tablica binarna.

Problem Description

Matrix $A$ has $n$ rows and $m$ columns. Rows are numbered from $1$ to $n$ from top to bottom, and columns are numbered from $1$ to $m$ from left to right. Therefore, $(i, j)$ denotes the element in row $i$ and column $j$ of the matrix. Each element of matrix $A$ is either $0$ or $1$.

Initially, all elements in the matrix are $0$. Then you can perform $q$ modification operations on this matrix. Each operation gives four parameters $i_1, j_1, i_2, j_2$, meaning that you flip the value of every element inside the rectangle with top-left corner $(i_1, j_1)$ and bottom-right corner $(i_2, j_2)$ (changing $0$ to $1$, or $1$ to $0$).

If in an operation, the top-left corner of the rectangle coincides with the top-left corner of the matrix (i.e., $i_1 = j_1 = 1$), then this modification operation is called simple.

Now you want to know, after each modification operation on the matrix, what is the minimum number of simple modification operations needed to make all elements in the matrix equal to $0$.

Input Format

The first line contains three integers $n, m, q$, representing the number of rows, the number of columns, and the number of operations.

The next $q$ lines each contain four integers $i_1, j_1, i_2, j_2$, describing one modification operation. It is guaranteed that $1 \leq i_1 \leq i_2 \leq n$ and $1 \leq j_1 \leq j_2 \leq m$.

Output Format

Output $q$ lines. The $i$-th line should contain one integer, indicating that after the $i$-th modification, what is the minimum number of simple modification operations needed to make all elements in the matrix equal to $0$.

2 3 3
1 2 2 2
1 1 2 1
1 2 1 3

2
1
3

4 4 16
1 1 1 1
1 2 1 2
1 3 1 3
1 4 1 4
2 1 2 1
2 2 2 2
2 3 2 3
2 4 2 4
3 1 3 1
3 2 3 2
3 3 3 3
3 4 3 4
4 1 4 1
4 2 4 2
4 3 4 3
4 4 4 4

1
1
1
1
3
3
3
1
3
3
3
1
3
3
3
1

Hint

[Sample Explanation 1]:

[Constraints]:

All testdata satisfy: $1 \leq n, m \leq 10^3$, $1 \leq q \leq 10^5$.

Translated by ChatGPT 5