Binary Matrix#10201
Given a matrix of size n \times m consisting of zeros and ones. Initially, all elements of the matrix are zero. There are also queries. In each query, four numbers (x_1, y_1, x_2, y_2) are given. You need to invert all elements of the submatrix a_{x_1 \ldots x_2,\, y_1 \ldots y_2}, that is, change each one to zero and each zero to one. After each query, you must determine the minimum number of operations required to make all elements of the matrix equal to zero.
Note. In one operation, you can choose two numbers and (1 \leq i \leq n,\ 1 \leq j \leq m) and invert all elements of the submatrix a_{1 \ldots i,\, 1 \ldots j}.
The first line contains three integers , , (1 \leq n, m \leq 10^9,\ 1 \leq q \leq 10^5) — the size of the matrix and the number of queries.
Each of the next lines contains four integers x_1, y_1, x_2, y_2 (1 \leq x_1 \leq x_2 \leq n,\ 1 \leq y_1 \leq y_2 \leq m) — describing the submatrix to invert.
For each query, output a single line with the minimum number of operations required to make all elements of the matrix equal to zero.
Example 1
Example 2