God Save the i-th Queen

Interview

Time limit1sMemory limit128 MB

Summary

Given a board and placed queens, count empty squares not sharing a row, column, or diagonal with any queen.

Level: Medium5 of 10
Topics: Array, Hash map, Math, Implementation
Solved: No attempts yet

Problem

Every year at the ACM-ICPC World Finals a large chessboard is set up so the contestants can play against one another. In this problem we check your basic chess intuition.

Recall that a queen attacks along its row, its column, and both diagonals.

A chessboard already holds $i - 1$ queens. Your task is to count the squares on which the $i$ -th queen could be placed so that it is not attacked by any of the queens already on the board. A candidate square must be empty and must not share a row, a column, or a diagonal with any existing queen.

Input

The input consists of several tasks.

Each task begins with a line of three integers $X$ , $Y$ , $N$ separated by spaces. $X$ and $Y$ give the board size, with $1 \le X, Y \le 20\,000$ . $N = i - 1$ is the number of queens already placed, with $0 \le N \le X \cdot Y$ .

The next $N$ lines each contain two integers $x_k$ and $y_k$ ( $1 \le x_k \le X$ , $1 \le y_k \le Y$ ), the position of the $k$ -th queen. All positions are distinct, i.e. no two queens share the same square.

The last task is followed by a line containing three zeros, which is not processed.

Output

For each task, print one line with a single integer: the number of empty squares that do not share a row, a column, or a diagonal with any queen already on the board.

Examples5

Example 1
Input
```
8 8 2
4 5
5 5
0 0 0
```
Expected output
```
20
```
Example 2
Input
```
5 5 0
0 0 0
```
Expected output
```
25
```
Example 3
Input
```
3 3 1
2 2
0 0 0
```
Expected output
```
0
```
Example 4
Input
```
4 4 1
1 1
0 0 0
```
Expected output
```
6
```

Example 5

Input

Expected output

20
0
6