JYY has $N$ rectangles in a 2D coordinate system. The bottom edge of each rectangle is parallel to the X-axis, and the side edge is parallel to the Y-axis. The bottom-left corner of the $i$-th rectangle is $(x_i, y_i)$, its base length is $a_i$, and its side length is $b_i$.

JYY plans to randomly select two different rectangles from these $N$ rectangles and calculate the size of their intersection. JYY wants to know the expected value of the intersection size.

In other words, JYY wants to know the average area of the intersection of two rectangles among all possible selections.

Input

The input contains a positive integer $N$. The next $N$ lines each contain 4 integers, representing $x_i, y_i, a_i, b_i$ respectively.

Output

Output a single real number representing the expected value of the intersection size of the two rectangles.

Note

The output file can contain a real number with arbitrary precision. If the absolute difference between the user's output and the standard answer does not exceed $10^{-2}$, it will be judged as correct.

Examples

Input 1

4
0 0 3 5
2 1 3 5
3 3 3 5
0 5 3 5

Output 1

1.833333333

Note 1

The positions of the 4 input rectangles are shown in the figure below.

The exact solution is: $\frac{4+0+0+1+6+0}{4 \times 3 / 2} = \frac{11}{6}$.

Constraints

• For 10% of the data, $N = 10$;
• For 20% of the data, $N \le 1000$;
• For 60% of the data, for any $i \neq j$, $a_i = a_j, b_i = b_j$ and $(x_i, y_i) \neq (x_j, y_j)$;
• For 100% of the data, $2 \le N \le 2 \cdot 10^5$, $0 \le x_i, y_i, a_i, b_i \le 10^6$.