This page is still under construction.

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

Rectangle Cutting

Time limit1sMemory limit128 MB

Summary
Given a small cake and several rectangular outlines cut into it, count the number of connected pieces the cake is divided into.
Level

Medium6 of 10

Topics
BFS, Implementation, Geometry, Simulation
Solved
No attempts yet

Problem

In a small historic village, a popular wedding-ceremony activity is called rectangle cutting. Each close relative of the bride comes up and cuts a rectangle into the wedding cake (but does not take a piece). The cake has a rectangular shape, and the task is to count how many pieces the cake is divided into after all the cuts.

For example, in the figure below the cake is 3×5 (height × width) and three people have each made a rectangular cut. As a result, the cake is split into six pieces.

Each rectangular cut is described by the (x,y)(x, y) coordinates of two opposite corners. Only the outline (the four edges) of each rectangle is cut; no cake is removed. The cuts in the figure correspond to the first sample test case. Because families here can be large, the number of pieces can also be large, so a program is needed to compute it.

Input

The input contains several test cases. Each test case spans several lines. The first line contains two integers hh and ww (1≤h,w≤201 \le h, w \le 20) — the height and the width of the cake. The second line contains a single integer nn (0≤n≤500 \le n \le 50) — the number of people who cut a rectangle. Each of the following nn lines contains four integers x1x_1, y1y_1, x2x_2, y2y_2, the coordinates of two opposite corners of one cut, where 0≤x1,x2≤w0 \le x_1, x_2 \le w and 0≤y1,y2≤h0 \le y_1, y_2 \le h (the xx-axis runs along the width, the yy-axis along the height). The input ends with a line containing two zeros, which is not processed.

Output

For each test case, output a single line containing the number of pieces the cake is cut into.

Examples1

  1. Example 1

    Input
    3 5
    3
    1 1 3 2
    4 0 2 3
    4 0 5 1
    6 6
    2
    2 0 5 3
    3 1 4 2
    0 0
    
    Expected output
    6
    3