Migrated from Lutece 2684 Dongxue Daisuki Benzhu

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Dongxue daisuki Benzhu, but Benzhu thinks Dongxue is getting too close. So Benzhu figures out a way to keep some distance from Dongxue.

The positions of Dongxue and Benzhu can be regarded as two points in a two-dimensional coordinate system. In the beginning, Dongxue and Benzhu are both at $(0,0)$.

Benzhu gives Dongxue $n$ pairs of integers in order, the $i$-th of which is $l_i$ and $r_i$. Each time Benzhu gives a pair, Dongxue will choose a real number in the range of $[l_i,r_i]$ uniformly and randomly, represented as $d_i$. Then Dongxue will go to a random point at a distance of $d_i$ from the current position. In detail, if he locates at $(x,y)$, he will choose a point uniformly and randomly on the circumference of the circle whose center is $(x,y)$ and radius is $d_i$.

Both Dongxue and Benzhu want to know how close they will be in the end. Let's denote the final Euclidean distance between them by $X$. Please calculate the expectation of $X^2$, i.e. $E(X^2)$. The Euclidean distance of two points $(x_1,y_1)$ and $(x_2,y_2)$ is $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$.

Input

The first line of the input contains only one integer $n$ ($1\le n\le 10^3$) indicating the number of pairs Benzhu gives Dongxue.

For the next $n$ lines, the $i$-th line contains two integers $l_i,r_i$ ($0\le l_i\le r_i\le 10^3$) indicating the $i$-th pair Benzhu gives Dongxue.

Output

Print $E(X^2)$, rounded to three decimal places.

Samples

1
1 2

2.333

2
1 2
1 3

6.667

Resources

电子科技大学第十二届 ACM 趣味程序设计竞赛