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 x[1]
, y[1]
, x[2]
, y[2]
are given, it is necessary to invert all elements of the submatrix a[x1 ... 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
a[1. . . i,1. . . j]
.
####Input:The first line contains three integers n, m, q (1 <= n, m <= 10^9
, 1 <= q <= 10^5
) - the dimensions of the matrix and number of requests.Each of the following q lines contains four integers x[1]
, y[1]
, x[2]
, y[2]
(1 <= x[1]
<= x[2]
<= n, 1 <= y[1]
<= y[2]
<= 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