MASKTAPE - Masking Tape

no tags 

You are a publicity agent of the JCIOI. You are ordered to make a signboard to publicize the IOI. The signboard made by painting a rectangle plywood board. The plywood board is bound with some rectangle masking tapes is in advance. So, You decide that you paint each region which is bounded by the masking tapes with different colors.
For example, five colors are necessary and enough to paint the plywood of Fig 5-1.

Write a program which, given a situation of a plywood, determine the minimum number of colors to be able to paint the input plywood with. Here, it is impossible that the entire surface of the plywood is covered by masking tapes, and every side of masking tapes is parallel to one of a side of the plywood.

Input

- The first line contains two integers separated by a single space that represent the size of the given plywood, the width w and the height h.
- The second line contains the number n of the masking tape on the plywood.
- The (2 + i)th line (1 ≤ i ≤ n) contains four integers x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ w,0 ≤ y1 < y2 ≤ h) separated by single spaces. (x1, y1) and (x2, y2) represent the coordinates of the bottom left corner and the top right corner, respectively, of the ith masking tape on the plywood.
Note that the coordinates of the bottom left corner of the plywood is (0, 0) and the coordinates of the top right corner of it is (w, h).

Output

- The output file should contain a single integer, which is the minimum number of colors to be able to paint the input plywood with.

Sample

Input:
15 6
10
1 4 5 6
2 1 4 5
1 0 5 1
6 1 7 5
7 5 9 6
7 0 9 2
9 1 10 5
11 0 14 1
12 1 13 5
11 5 14 6

Output:
5

Limitations

- 1 ≤ n ≤ 1000.
- 1 ≤ w, h ≤ 106.
30% of the mark is given for test cases with w ≤ 100, h ≤ 100, n ≤ 100.



Added by:AnhDQ
Date:2009-05-10
Time limit:0.300s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:JOI08