This page is still under construction.

Parts of this page are still being built. What you see may change.

Cutting Lines

Time limit3sMemory limit256 MB

Summary
Count the pieces of a W by H rectangle after cutting along N axis-parallel interior segments.
Level

Medium7 of 10

Topics
Geometry, Union-find, Sorting, Math
Solved
No attempts yet

Problem

A rectangle has corners (0,0)(0,0), (W,0)(W,0), (0,H)(0,H), and (W,H)(W,H). There are NN cut segments, each parallel to a side. Segment ii runs from (Ai,Bi)(A_i,B_i) to (Ci,Di)(C_i,D_i) with exactly one of Ai=CiA_i=C_i or Bi=DiB_i=D_i. Parallel segments never share a point, and no parallel segment touches the paper border. After cutting along every segment, how many pieces remain?

Input

The first line has WW, HH, and NN. The next NN lines give each segment's endpoints.

Output

Print the number of pieces on one line.

Limits

1≤W,H≤1091 \le W,H \le 10^9, 1≤N≤1051 \le N \le 10^5.

Examples2

  1. Example 1

    Input
    10 10 5
6 0 6 7
0 6 7 6
2 3 9 3
2 3 2 10
1 9 8 9
    Expected output
    4

  2. Example 2

    Input
    13 7 28
1 1 4 1
1 1 1 3
2 2 3 2
2 2 2 3
1 3 2 3
3 2 3 6
4 1 4 6
3 6 4 6
5 1 8 1
5 1 5 6
6 2 7 2
6 2 6 5
7 2 7 5
6 5 7 5
8 1 8 6
5 6 8 6
9 1 12 1
9 1 9 2
9 2 10 2
12 1 12 2
11 2 12 2
10 2 10 5
9 5 10 5
9 5 9 6
11 2 11 5
11 5 12 5
12 5 12 6
9 6 12 6
    Expected output
    5