JAVA (Japan Aerospace Voyage Agency) launched a spacecraft in 2003 as part of its space development project. One of the purposes of launching this spacecraft is to approach the asteroid Ishikawa and collect samples of its surface material. Despite various accidents, the spacecraft reached Ishikawa and finally returned to Earth in 2010 to successfully recover the capsule containing Ishikawa's sample.

Masa Kita, who graduated from the University of Tokyo and got a job at JAVA, is in charge of research on this sample. I'd like to analyze the sample as soon as possible, but Mr. Kitamasa, who is very careful, thought that it would be difficult if there were ferocious aliens in the capsule. Therefore, before opening the capsule, I decided to use X-rays to examine the shape of the substance inside and confirm that it did not contain aliens. When the capsule is exposed to X-rays, a photograph is obtained in which the substance is white where it is present and black where it is not present. By irradiating X-rays from various angles and obtaining photographs, the shape of the substance inside can be identified.

However, there was another problem here. The X-ray device broke down when I got three pictures from the front, from the right side, and from the top. Furthermore, it is possible that the development of the three photographs also failed, and the part that should have been black has turned white. Since the shape of the substance cannot be accurately specified as it is, it cannot be confirmed that there are no aliens inside, and the capsule cannot be opened.

The only way to continue research is to replace the X-ray equipment, but JAVA does not have the money to replace the X-ray equipment immediately due to the budget cuts due to business sorting. So Kitamasa asked him to increase his budget next year and thought about buying a new X-ray device with that money. Of course, the budget will not increase easily, so it is necessary to maximize the results of the spacecraft. The larger the substance contained in the capsule, the stronger the appeal of the result, so we decided to calculate the maximum volume that the substance can take.

Find the shape of the substance inside that is consistent with the three X-ray photographs and have the largest volume, and output that volume.

Notes on Test Cases

Multiple datasets are given in the above input format. Create a program that outputs each data set in the above output format.

When nx, ny, nz are all 0, it indicates the end of input.

<!-

Input

The white and black border of each radiograph consists of a single polygon. Polygons are not always convex and do not self-intersect. The inside of the polygon is white and the outside is black.

The input format is as follows.

nx
y1 z1
y2 z2
...
ynx znx
ny
z1 x1
z2 x2
...
zny xny
nz
x1 y1
x2 y2
...
xnz ynz

nx, ny, and nz are the number of vertices of the polygon corresponding to the X-ray photograph from the front, right side, and top, respectively. The number of each vertex is 3 or more and 20 or less. The following n lines are given the coordinates of the vertices of the polygon counterclockwise. The coordinates of the vertices are integers between 0 and 300.

The coordinate axes are the x-axis in the front direction from the center of the capsule, the y-axis in the right side direction, and the z-axis in the top surface direction.

<image>

Output

Output the maximum volume of the substance in one line that is consistent with the three X-ray photographs. The output value may contain an error of 10-3 or less. The value may be displayed in any number of digits after the decimal point.

Examples

Input

4
0 0
100 0
100 100
0 100
4
0 0
100 0
100 100
0 100
4
0 0
100 0
100 100
0 100
3
0 0
100 0
0 100
3
0 0
100 0
0 100
3
0 0
100 0
0 100
5
0 0
200 0
200 200
100 100
0 200
5
0 0
200 0
100 100
200 200
0 200
4
0 0
200 0
200 200
0 200
0
0
0

Output

1000000.0000
250000.0000
5333333.3333

Input

4
0 0
100 0
100 100
0 100
4
0 0
100 0
100 100
0 100
4
0 0
100 0
100 100
0 100

Output

1000000.0000

Input

3
0 0
100 0
0 100
3
0 0
100 0
0 100
3
0 0
100 0
0 100

Output

250000.0000

Input

5
0 0
200 0
200 200
100 100
0 200
5
0 0
200 0
100 100
200 200
0 200
4
0 0
200 0
200 200
0 200

Output

5333333.3333

见题面

见题面