3D Geometry

An axis-aligned tetrahedron (also known as triangular pyramid) $DABC$ is a convex polyhedron in three dimension with vertices

• $D: (x\_1, y\_1, z\_1)$,
• $A: (x\_2, y\_1, z\_1)$,
• $B: (x\_1, y\_2, z\_1)$,
• $C: (x\_1, y\_1, z\_2)$.

Also, an axis-aligned cube $PQRSDEFG$ is a convex polyhedron with vertices

• $P: (x\_3, y\_3, z\_3)$,
• $Q: (x\_3, y\_3, z\_4)$,
• $R: (x\_3, y\_4, z\_3)$,
• $S: (x\_3, y\_4, z\_4)$,
• $D: (x\_4, y\_3, z\_3)$,
• $E: (x\_4, y\_3, z\_4)$,
• $F: (x\_4, y\_4, z\_3)$,
• $G: (x\_4, y\_4, z\_4)$.

Given an axis-aligned tetrahedron $DABC$ and an axis-aligned cube $PQRSDEFG$, find the volume of their intersection.

The input consists of several test cases terminated by end-of-file. For each test case,

There are $4$ lines, and the $i$-th line contains three integers $x\_i$, $y\_i$, and $z\_i$.

For each test case, output a float which denotes the volume.

Your answer is considered correct if its absolute or relative error doesn't exceed $10^{-6}$.

• $-500 \leq x\_i, y\_i, z\_i \leq 500$ for each $1 \leq i \leq 4$
• $x\_1 \neq x\_2$, $y\_1 \neq y\_2$, $z\_1 \neq z\_2$
• $x\_3 \neq x\_4$, $y\_3 \neq y\_4$, $z\_3 \neq z\_4$
• In each input, the number of test cases does not exceed $10^5$.