Paper Hole Count

The headquarters' assistant often needs to cut various shapes out of a large sheet of paper. With the new cutting machine, which is much more flexible than the previous one, they can now perform a series of complex rectangular cuts. After all the cutting, the assistants are particularly interested in finding out how many holes have been formed on the paper. A hole is defined as a connected region of removed parts (cells with value 0) that is completely surrounded by intact paper (cells with value 1), i.e. the region does not touch the border of the paper.

The paper is represented as a grid of R rows and C columns, initially filled with 1's (representing intact paper). Each cutting operation removes (sets to 0) all cells in a given rectangular region specified by its top‐left and bottom‐right coordinates. Two cells are considered connected if they share a side (up, down, left, or right).

Your task is to output the number of holes (i.e. connected 0-regions that do not touch the border) after all cutting operations have been performed.

The latex formula for the definition of a hole can be given as:

\( \text{Hole} = \{ (i,j) \mid grid[i][j] = 0 \text{ and the connected region does not intersect } \{i=1, i=R, j=1, j=C\} \} \)

inputFormat

The first line contains three integers R, C, and Q representing the number of rows, columns, and the number of cutting operations, respectively.

Each of the following Q lines contains four integers r1, c1, r2, and c2 (1-indexed) indicating that all cells in the rectangle from row r1 to r2 and column c1 to c2 (inclusive) are removed (set to 0).

outputFormat

Output a single integer representing the number of holes formed on the paper. A hole is a connected region of removed cells that does not touch the border of the grid.

sample

5 5 1
2 2 4 4

1