Giải bài trực tuyến

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 x₁， y₁， x₂， y₂ (0 ≤ x₁ < x₂ ≤ w，0 ≤ y₁ < y₂ ≤ h) separated by single spaces. (x₁, y₁) and (x₂, y₂) represent the coordinates of the bottom left corner and the top right corner, respectively, of the i^th 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 ≤ 10⁶.
30% of the mark is given for test cases with w ≤ 100, h ≤ 100, n ≤ 100.