Binary Matrix
Binary Matrix
You are given a matrix a of size n × m of zeros and ones, initially all elements are zeros.
Also you are given q queries, in each query numbers x1, y1, x2, y2 are given, it is necessary to invert all elements of the submatrix ax1...x2,y1...y2, i.e change each unit on this submatrix to zero, and every zero per unit.
After each query it is necessary to find the minimum number of operations which it must be done so that all elements of the matrix a become zeros.
- In one operation,you can select two numbers i and j (1 <= i <= n ,1 <= j <= m) and invert all elements of the submatrix
a1...i,1...j.
Input:
The first line contains three integers n, m, q (1 <= n, m <= 109, 1 <= q <= 105) - the dimensions of the matrix and number of requests.
Each of the following q lines contains four integers x1, y1, x2, y2 (1 <= x1 <= x2 <= n, 1 <= y1 <= y2 <= m) - numbers from the query.
Output:
For each query, print in one line the minimum number of operations so that all elements of the matrix
3 4 3 1 1 1 1 2 1 2 2 1 3 3 4
1 3 5
3 3 3 2 1 2 1 2 1 2 1 2 2 2 2
2 0 4