401609: GYM100499 H CCTV

Closed-circuit television (CCTV), also known as video surveillance, is the use of video cameras to transmit a signal to a specific place, on a limited set of monitors. They are widely used for security purposes.

Next week, there will be an exhibition of famous Renaissance artwork. The exhibition room has a rectangular form with the lower left corner at (0, 0) and the upper right corner at (X, Y). In 4 corners of the room, CCTVs are used to surveillance every moves of every visitors. Inside this room, N impressive artworks are placed in glass cases. These glass cases are all rectangular shape with edges parallel to the walls; the lower left corner is at (X_1i, Y_1i) and the upper right corner is at (X_2i, Y_2i). A CCTV can track any point if the direct line from the point to the CCTV is not blocked by some case.

Given the shape of the exhibition room, the position and shape of all the cases, your task is to calculate the track-able area of 4 CCTV.

The input starts with T (T ≤ 20) - the number of tests. Then T tests follow. Each test is formatted as:

• The first line consists of X, Y - the upper right corner of the exhibition room. (0 < X, Y ≤ 1000).
• The second line consist of N - the number of glass cases. (1 ≤ N ≤ 20).
• In the next N lines, the ith line describes the position of the ith cabinet. It consists of 4 integers X_1i, Y_1i, X_2i, Y_2i.
• No cabinet share a point with another cabinet or with any CCTV.

For each test, you should print 2 lines:

• On the first line, print the track-able area of the CCTV at the upper left corner and upper right corner.
• On the second line, print the track-able area of the CCTV at the lower left corner and lower right corner.
• The result should be printed with the precision of less than 1e-4.

1
4 4
2
1 1 2 2
1 3 3 4

4.666667 6.833333
8.250000 9.666667

The layout of the exhibition room in the example:

The track-able area of CCTVs: