Box Art

The world-famous artist A.A. Blox, celebrated for his cubic sculptures, has invented a brand-new way to create striking artwork from a rectangular block of transparent acrylic glass. Using the patented laser device built by his friend T.D. Resal, he can change the colour of parts of the originally colourless block. Because the laser device is still a prototype, he can only colour a rectangular region whose faces are parallel to the faces of the large block ("axis aligned").

The value of the finished piece is the volume of coloured acrylic glass. Since A.A. Blox is not fond of mathematics, he has hired you to compute the price of his artwork.

Given an axis-aligned initial box $b$ and a set $S$ of axis-aligned boxes, compute the volume of the union of all parts of the boxes in $S$ that lie inside $b$. Volume covered by several boxes must be counted only once.

The first line contains the number of scenarios.

Each scenario begins with a line x1 y1 z1 x2 y2 z2 giving the two opposite corners $(x_1, y_1, z_1)$ and $(x_2, y_2, z_2)$ of the initial box $b$. The numbers are separated by single spaces.

The next line contains the number $m$ ($m \le 2000$) of boxes in $S$ that were coloured by the laser device, followed by $m$ lines, each containing x1 y1 z1 x2 y2 z2 for the two opposite corners of one box in $S$.

All coordinates are integers in the range $0$ to $1000$, and every line satisfies $x_1 \le x_2$, $y_1 \le y_2$, and $z_1 \le z_2$.

For every scenario, first print a line Scenario #i:, where $i$ is the scenario number starting at $1$. Then print a line with the total volume of coloured acrylic glass. Separate consecutive scenarios with a blank line.