Sculpture

Time limit1sMemory limit128 MB

Summary

Given a set of axis-aligned boxes in 3D, compute the total exposed surface area and total volume, including internal cavities not reachable by liquid, using 3D space decomposition.

Level: Hard8 of 10
Topics: Geometry, Matrix, Simulation
Solved: No attempts yet

Problem

Imagine a box made of copper plate. Imagine a second one intersecting the first, and several others intersecting one another (or not). That is how a sculptor builds his sculptures. In fact he does not build them himself; he only makes the design, and the actual construction is contracted out to a construction company.

To calculate the construction cost, the company needs the total area of copper plate involved. Parts of a box that are hidden inside another box are, of course, not made of copper (copper is expensive, and prices keep rising).

After construction, the whole piece is plunged into a bath of chemicals. To keep the bath from overflowing, the company also needs the total volume of the construction.

Given a construction that is a collection of boxes, compute its total copper-plate area and its total volume.

Some designs are connected and some are not; either way, we want the total area and the total volume. The boxes may completely enclose a region of space that belongs to none of them. Because the liquid cannot reach that region, its volume must be added to the total volume. Copper plate bordering such an enclosed region is superfluous, so it does not add to the area.

Input

The first line contains a single positive integer: the number of test cases, at most $100$ . Each test case is given as follows:

One line with an integer $n$ ( $1 \le n \le 50$ ): the number of boxes.
$n$ lines, each with six positive integers $x_0, y_0, z_0, x, y, z$ ( $1 \le x_0, y_0, z_0, x, y, z \le 500$ ). The point $(x_0, y_0, z_0)$ is the corner of the box with the smallest coordinates, and $x, y, z$ are its side lengths along the respective axes. All lengths are in centimeters, and every box has edges parallel to the coordinate axes.

Output

For each test case, print one line with two integers separated by a single space: the total amount of copper plate needed (in square centimeters) and the total volume (in cubic centimeters).

Examples7

Example 1

Input

2
2
1 2 3 3 4 5
6 2 3 3 4 5
7
1 1 1 5 5 1
1 1 10 5 5 1
1 1 2 1 4 8
2 1 2 4 1 8
5 2 2 1 4 8
1 5 2 4 1 8
3 3 4 1 1 1

Expected output

188 120
250 250

Example 2
Input
```
1
1
1 1 1 2 3 4
```
Expected output
```
52 24
```
Example 3
Input
```
1
2
1 1 1 4 4 4
3 3 3 4 4 4
```
Expected output
```
168 120
```

Example 4

Input

1
2
1 1 1 10 10 10
3 3 3 2 2 2

Expected output

600 1000

Example 5

Input

1
6
1 1 1 3 3 1
1 1 3 3 3 1
1 1 2 3 1 1
1 3 2 3 1 1
1 2 2 1 1 1
3 2 2 1 1 1

Expected output

54 27

Example 6
Input
```
1
2
1 1 1 2 2 2
3 1 1 2 2 2
```
Expected output
```
40 16
```

Example 7

Input

3
1
5 5 5 1 1 1
2
1 1 1 2 2 2
10 10 10 2 2 2
1
1 1 1 500 500 500

Expected output

6 1
48 16
1500000 125000000