Safe Squares on a Chessboard

Interview

Time limit2sMemory limit128 MB

Summary

Given a chessboard with queens, knights, and pawns, count squares that no queen or knight attacks, treating all pieces as movement blockers.

Level: Medium5 of 10
Topics: Simulation, Implementation, Matrix
Solved: No attempts yet

Problem

An n x m chessboard contains the opponent's Queen, Knight, and Pawn pieces. A square is safe if you could place one of your pieces there and it would not be captured by any opponent piece. Count the number of safe squares.

A Queen attacks horizontally, vertically, and diagonally in all 8 directions until just before the first occupied square in that direction. If another piece is in the way, squares behind it are not attacked by that Queen.

A Knight attacks the 8 squares reached by moving to the opposite corner of a 2 x 3 rectangle. A Knight's attack is not blocked by pieces between the start and target squares.

A Pawn does not attack any square in this problem. It only acts as an obstacle that can block a Queen's movement.

Input

The first line contains the number of rows n and columns m of the chessboard. (1 <= n, m <= 1000)

The second line contains the number k of Queens, followed by k positions r_i c_i. The third line gives the Knights in the same format, and the fourth line gives the Pawns in the same format.

For each position, r_i is the row and c_i is the column. No two pieces are placed on the same square. The number of Queens, Knights, and Pawns is each a nonnegative integer not greater than 100.

Output

Print the number of safe squares on the n x m chessboard.

Examples2

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