eolymp
bolt
Try our new interface for solving problems
Problems

Rectangle Cutting

Rectangle Cutting

In the small historical village of Basinia, there is a popular activity in wedding ceremonies called rectangle cutting. During this activity, each close relative of the bride comes and cuts a rectangle in the wedding cake (but does not take a piece). The cake has a rectangular shape. The problem is to count how many pieces are in the cake after rectangle-cutting. For example, in the following figure, the cake size is \textbf{3}×\textbf{5}, and three people have made rectangular cuts in it. As a result, the cake is cut into six pieces. \includegraphics{https://static.e-olymp.com/content/e3/e39f860ffbb6bc221bfcd71e7c6dcd187cc0f568.jpg} Each rectangular cut is specified by the (\textbf{x}, \textbf{y}) coordinates of its two opposite corners. The input for the above figure can be found in the first sample input. As there are large families in Basinia, the number of pieces may be large and we need a computer program to compute it. \InputFile The input contains several test cases. Each test has several lines. The first line has two integers \textbf{w} (\textbf{1} ≤ \textbf{w} ≤ \textbf{20}) and \textbf{h }(\textbf{1} ≤ \textbf{h} ≤ \textbf{20}) which are the width and height of the cake. The second line contains a single integer \textbf{n} (\textbf{0} ≤ \textbf{n} ≤ \textbf{50}) which is the number of people who cut rectangles in the cake. After this, there are \textbf{n} lines each containing the integers \textbf{x_1}, \textbf{y_1}, \textbf{x_2}, \textbf{y_2} which are the coordinates of two opposite corners of the cut. You may assume \textbf{0} ≤ \textbf{x_1}, \textbf{x_2} ≤ \textbf{w} and \textbf{0} ≤ \textbf{y_1}, \textbf{y_2} ≤ \textbf{h}. The last line of the input is a line containing two zeros. \OutputFile For each test case, write the number of pieces the cake is cut into.
Time limit 1 second
Memory limit 64 MiB
Input example #1
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
Output example #1
6
3