Matrix Simple Flip Operations

We are given a binary matrix \(A\) with \(n\) rows and \(m\) columns. The rows are numbered from \(1\) to \(n\) (from top to bottom) and the columns from \(1\) to \(m\) (from left to right), so the element in the \(i\)th row and \(j\)th column is denoted by \((i,j)\). Initially, every element of \(A\) is \(0\).

You will perform \(q\) modification operations on the matrix. In each operation, you are given four integers \(i_1, j_1, i_2, j_2\) which describe a rectangular region with the top-left corner at \((i_1,j_1)\) and the bottom-right corner at \((i_2,j_2)\). The operation flips every element in that rectangle (that is, \(0\) becomes \(1\) and \(1\) becomes \(0\)).

An operation is called simple if the rectangle starts at the top-left corner of the matrix (i.e. if \(i_1 = j_1 = 1\)). A simple operation flips all elements in a prefix submatrix (from \((1,1)\) to \((i,j)\) for some valid \(i\) and \(j\)).

After each modification operation, your task is to determine the minimum number of simple operations required to turn the matrix back to all zeros. A standard greedy strategy is to scan the matrix from the bottom-right corner to the top-left. Whenever a \(1\) is encountered, perform a simple operation that flips the corresponding prefix submatrix; this process yields the minimum required number.

inputFormat

The first line contains three integers \(n\), \(m\), and \(q\) representing the number of rows, columns, and operations respectively.

Each of the following \(q\) lines contains four integers \(i_1\), \(j_1\), \(i_2\), \(j_2\) describing an operation: flip all elements in the rectangle with top-left \((i_1,j_1)\) and bottom-right \((i_2,j_2)\).

outputFormat

After each operation, output a single line containing the minimum number of simple operations needed to turn the matrix back to all zeros.

sample

2 2 2
1 1 1 1
1 2 2 2

1
3