Inlay Cutters

Time Limit: 2 Seconds
Memory Limit: 65536 KB

The factory cuts rectangular M x N granite plates into pieces using a special
machine that is able to perform cuts in 4 different directions: vertically,
horizontally, and diagonally at the angle of 45 degrees to the sides of the
plate. Every cut is a straight line that starts and ends on the side of the
plate.

The factory has been ordered to produce tiles for the inlay, each tile of which
is a 45 degrees right triangle. To reduce the time to deliver the tiles it was
decided to take all triangles from the already cut plates. Information about
all performed cuts is available and your task is to compute the number of triangles
of any size that were produced.

**Input**

The input file describes the cuts that were performed on a single rectangular
plate. The first line of the input file contains three integer numbers M, N,
and K, separated by spaces. M and N (1 <= M, N <= 50) are the dimensions
of the plate, and K (0 <= K <= 296) is the number of cuts. Next K lines
describe the cuts. ith cut is described by four integer numbers Xi,1, Yi,1,
Xi,2, and Yi,2, separated by spaces, that represent the starting and ending
point of the cut. Both starting (Xi1, Yi1) and ending (Xi2, Yi2) points of the
cut are situated on the plate's border. Both points of the cut are different
and the cut goes through the plate. Here, the coordinates by the X axis run
from 0 to M, and the coordinates by the Y axis run from 0 to N. All cuts are
different.

**Output**

Write to the output file a single integer number - the number of triangles that
were produced by the cuts.

**Sample Input**

4 4 4

1 4 1 0

0 4 4 0

0 0 4 4

0 2 4 2

7 4 6

6 0 7 1

1 4 1 0

0 4 4 0

0 0 4 4

0 2 7 2

7 0 3 4

**Sample Output**

6

8

Source:

**Northeastern Europe 2002**
Submit
Status