Connected Black Cells

Given an \(N \times M\) grid with rows and columns numbered from \(0\), a cell \((i,j)\) is black if and only if \(i \& j = 0\). Two black cells are connected if and only if they are both black and there exists a path between them moving through adjacent (up, down, left, or right) black cells.

You are given \(Q\) queries. Each query specifies a rectangle by its top-left corner \((x_1,y_1)\) and bottom-right corner \((x_2,y_2)\). For each query, you need to determine the number of connected components formed by the black cells within that rectangle.

Note: All coordinates are 0-indexed. All formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains three integers \(N\), \(M\), and \(Q\) representing the number of rows, the number of columns, and the number of queries respectively.

Each of the following \(Q\) lines contains four integers \(x_1\), \(y_1\), \(x_2\), and \(y_2\) representing the top-left and bottom-right corners of the query rectangle.

outputFormat

For each query, output a single integer on a new line representing the number of connected components of black cells in the specified rectangle.

sample

3 3 2
0 0 2 2
1 1 2 2

1
2