005 - ペンキの色

問題

情報オリンピックの宣伝のために,長方形のベニヤ板にペンキを塗り看板を制作 したい.ベニヤ板には色を塗りたくないところにあらかじめ何枚かの長方形のマス キングテープが貼られている.そこでマスキングテープで区切られた領域ごとに別々 の色を使いペンキを塗ることにした.例えば,図 5-1 の場合は 5 色のペンキを使う.

入力としてマスキングテープを貼る位置が与えられた時,使うペンキの色の数を 求めるプログラムを作成せよ.ただし,ベニヤ板全体がマスキングテープで覆われる ことはなく,全てのマスキングテープの辺はベニヤ板のいずれかの辺に平行である.

入力

入力ファイルのファイル名は input.txt である.

1 行目にはベニヤ板の幅 w (1 ≤ w ≤ 1000000 となる整数) と高さ h (1 ≤ h ≤ 1000000 となる整数) がこの順に空白区切りで書かれている.

2 行目にはマスキングテープの数 n (1 ≤ n ≤ 1000 となる整数) が書かれている. 続く 3 行目以降の 2 + i 行目 (1 ≤ i ≤ n) には,i 番目に貼るマスキングテープの左 下の座標 (x₁ , y₁ ) と,右上の座標 (x₂ , y₂ ) が x₁ , y₁ , x₂ , y₂ (0 ≤ x₁ < x₂ ≤ w, 0 ≤ y₁ < y₂ ≤ h となる整数) の順に空白区切りで書かれている.

ただし,ベニヤ板の左下の角の座標は (0, 0) で右上の角の座標は (w, h) である. 採点用データのうち, 配点の 30% 分は w ≤ 100, h ≤ 100, n ≤ 100 を満たす.

出力

出力ファイルのファイル名は output.txt である. output.txt は 1 行だけからなり,その 1 行は使うペンキの色数だけを含む.

次の例は図 5-1 の場合である.

入出力の例

input.txt

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.txt

5