Floors

Time limit1sMemory limit128 MB

Summary

Guillotine-cut a rectangle tiled by disjoint rectangles into the smallest possible pieces and output the largest piece's area.

Level: Medium7 of 10
Topics: Divide and conquer, Geometry, Recursion, Implementation
Solved: No attempts yet

Problem

The new highway promised a better and faster connection between A and B and a considerable reduction of congestion. Unfortunately there was an obstacle: the old mansion. This conflict was soon resolved in favor of the highway.

Shortly before the demolition of the mansion was about to start, a lover of old mansions found out that the colorfully tiled floors in the mansion were designed by the famous painter Mondriaan, and therefore had great cultural value. They had to be saved and removed from the mansion before it was demolished.

A floor moving expert was hired for the job. To make it more tractable, he decided to cut each floor into smaller pieces. His fine cutting tool could cut a rectangular piece of floor, parallel to one of its sides, into two smaller rectangular pieces. Of course the cut had to run between tiles; cutting through a tile was not allowed. In this way the floor in Figure 1 could easily be cut into 9 tiles. The floor in Figure 2, however, cannot be cut into smaller pieces. The floor in Figure 3 can be cut into six pieces, but one of them consists of several tiles.

The expert wanted to know how heavy the remaining pieces could be. Because the floors have a fixed thickness and a fixed density, the weight of a piece depends only on its area.

Given a rectangular floor covered with rectangular tiles, keep cutting the floor into the smallest possible pieces, then report the area of the largest piece. Here "smallest" and "largest" refer to the area of the pieces. Cutting through a tile is not allowed, and a cut is always parallel to one of the sides and runs through the full length (or width) of the rectangle.

Input

The input contains several floors. The first line gives the number of floors.

Each floor is described on several lines. The first line contains two positive integers: the length and the width of the floor, in millimeters. A floor is at most $40000$ mm long or wide. The next line contains a single integer $t$ ( $1 \le t \le 100$ ), the number of tiles. Each of the following $t$ lines describes one tile as four integers:

xl yl xh yh

where $(x_l, y_l)$ is the lower-left corner of the tile and $(x_h, y_h)$ is the upper-right corner. Every tile has a positive area, and the axis directions of the tiles match those of the floor. The tiles are mutually disjoint and together cover the whole floor, and nothing but the floor.

Output

For each floor (each test case), print on a single line the area of the largest piece (in square millimeters) after cutting the floor into the smallest possible pieces under the given restrictions.

Examples3

Example 1

Input

2
300 400
3
0 0 300 200
0 200 200 400
200 200 300 400
300 300
5
0 0 200 100
200 0 300 200
0 100 100 300
100 200 300 300
100 100 200 200

Expected output

60000
90000

Example 2
Input
```
1
100 100
1
0 0 100 100
```
Expected output
```
10000
```

Example 3

Input

1
200 200
4
0 0 100 100
100 0 200 100
0 100 100 200
100 100 200 200

Expected output