Cake Cutting

Time limit1sMemory limit1024 MB

Summary

Count the distinct rectangular pieces that can be left after repeatedly halving a cake into two equal halves with equal candle counts.

Level: Medium7 of 10
Topics: Divide and conquer, Recursion, Hash map
Solved: No attempts yet

Statement

For Artūras's birthday, his friends baked a rectangular cake. On it they placed $K$ candles, one for each year of his age. Because the cake is decorated with a checkered pattern, we can treat it as an $M \times N$ rectangle. Some cells hold exactly one candle, while the others hold none.

The friends set Artūras a task: cut off a piece of the cake following these rules.

With a single horizontal or vertical cut that runs along the cell edges, the cake is split into two rectangular pieces. The two pieces must have the same size and the same number of candles.
Artūras sets one of the two pieces aside and keeps cutting the remaining piece by the same rules.
When a piece can no longer be cut, Artūras keeps it if it contains exactly one candle. Otherwise he gets no cake.

For example, the $4 \times 8$ cake below can be split by one vertical cut into two $4 \times 4$ pieces, each holding two candles. The first cut cannot be horizontal: cutting through the middle would leave three candles in the top piece and only one in the bottom.

The right piece cannot be cut any further and holds two candles, so keeping it would leave Artūras with no cake. The left piece can be cut either horizontally or vertically.

In both cases each resulting piece holds one candle, so any of them may go to Artūras.

Thus in this example Artūras can end up with one of four different pieces.

Count how many different pieces Artūras can end up with. Two pieces are considered different if they occupy different positions in the cake.

Input

The first line contains three integers: the cake height $M$ , the width $N$ , and the number of candles $K$ .

Each of the next $K$ lines gives the coordinates of a cell that holds a candle. The first value is the vertical coordinate, numbered from $0$ to $M-1$ top to bottom, and the second is the horizontal coordinate, numbered from $0$ to $N-1$ left to right.

No cell is listed more than once.

Output

Print a single integer: the number of different pieces Artūras can end up with.

Constraints

$1 \le M, N \le 10^9$
$1 \le K \le 10^5$
The number of candles does not exceed the number of cells, i.e. $K \le M \cdot N$ .

Examples4

Example 1
Input
```
4 8 4
0 0
2 2
0 6
0 7
```
Expected output
```
4
```

Example 2

Input

Expected output

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