Bobo has a triangle and a rectangle, and he wants to find the area of their intersection.

Specifically, the triangle and the rectangle are described by $8$ integers $x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4$. The vertices of the triangle are $(x_1, y_1), (x_1, y_2), (x_2, y_1)$. The vertices of the rectangle are $(x_3, y_3), (x_3, y_4), (x_4, y_4), (x_4, y_3)$.

Input

The input contains no more than $30000$ test cases.

Each test case consists of two lines. The first line contains $4$ integers $x_1, y_1, x_2, y_2$ ($x_1 \neq x_2, y_1 \neq y_2$).

The second line contains $4$ integers $x_3, y_3, x_4, y_4$ ($x_3 < x_4, y_3 < y_4$).

($0 \leq x_i, y_i \leq 10^4$)

Output

For each test case, output a real number representing the area of the intersection. An absolute or relative error of less than $10^{-6}$ is considered correct.

Examples

Input 1

1 1 3 3
0 0 2 2
0 3 3 1
0 0 2 2
4462 1420 2060 2969
4159 257 8787 2970

Output 1

1.00000000
0.75000000
439744.13967527