Binary Table

Interview

Time limit6sMemory limit1024 MB

Summary

Given a binary table and rectangle flips, report after each flip the fewest top-left rectangle flips needed to reset the table to all zeros.

Level: Medium6 of 10
Topics: Matrix, Prefix sum
Solved: No attempts yet

Statement

You are given a table $A$ with $n$ rows and $m$ columns. Each cell holds a 0 or a 1. Rows are numbered $1, \ldots, n$ from top to bottom, and columns are numbered $1, \ldots, m$ from left to right. The cell in row $i$ and column $j$ has coordinates $(i, j)$ . The figure below also shows this.

The table supports a flip operation on a rectangle. Each operation is given by four numbers $i_1, j_1, i_2, j_2$ . The rectangle has opposite corners at $(i_1, j_1)$ and $(i_2, j_2)$ . Every cell inside it changes from 0 to 1 or from 1 to 0.

An operation is called simple if its top left corner is the top left corner of the table, that is, $i_1 = j_1 = 1$ .

Initially every number in the table is 0. Then $q$ operations are applied, each changing the table. After each operation, find how many more simple operations would be needed to turn every number in the table back to 0.

Input

The first line contains three integers $n$ , $m$ , and $q$ ( $1 \le n, m \le 1000$ , $1 \le q \le 100000$ ), the table size and the number of operations.

Each of the next $q$ lines describes one operation with four integers $i_1$ , $j_1$ , $i_2$ , $j_2$ ( $1 \le i_1 \le i_2 \le n$ , $1 \le j_1 \le j_2 \le m$ ).

Output

Print exactly $q$ lines. The $i$ -th line contains the minimum number of simple operations needed to turn every number in the table to 0, after the first $i$ operations from the input have been applied.

Hint

The top row of the figure shows the table $A$ after the three operations from the input, applied in order. Each column shows the table being reset to zeros with the minimum number of simple operations.

Examples1

Example 1
Input
```
2 3 3
1 2 2 2
1 1 2 1
1 2 1 3
```
Expected output
```
2
1
3
```