A. Absolute Difference
time limit per test
1 s
memory limit per test
512 megabytes
input
standard input
output
standard output

Both Alice and Bob have a set of real numbers, and both sets are the union of some disjoint closed intervals. They will independently pick a real number uniformly at random from their own set, and you need to calculate the expected absolute difference between the two real numbers.

More formally, given a set of real numbers $$$S = \bigcup\ [l,r]$$$, picking a real number $$$x$$$ from the set $$$S$$$ uniformly at random means that $$$P(x \in [l_1, r_1]) = P(x \in [l_2, r_2])$$$ holds for any two intervals $$$[l_1, r_1], [l_2, r_2] \subseteq S$$$ with the same length, i.e., $$$r_1 - l_1 = r_2 - l_2$$$.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^5$$$), the number of intervals that form Alice's set and Bob's set respectively.

Each of the following $$$n+m$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$-10^9 \le l \le r \le 10^9$$$), describing a closed interval $$$[l,r]$$$. The first $$$n$$$ intervals form Alice's set and the next $$$m$$$ intervals form Bob's set. Note that an interval $$$[l,r]$$$ with $$$l=r$$$ is a degenerate interval that contains a single real number.

It is guaranteed that the intervals that form someone's set are pairwise disjoint.

Output

Output a single real number, indicating the expected absolute difference of the two real numbers picked by Alice and Bob separately.

Your answer is acceptable if its absolute or relative error does not exceed $$$10^{-9}$$$. Formally speaking, suppose that your output is $$$a$$$ and the jury's answer is $$$b$$$, your output is accepted if and only if $$$\frac{|a - b|}{\max(1, |b|)} \leq 10^{-9}$$$.

Examples
Input
1 1
0 1
0 1
Output
0.333333333333333
Input
1 1
0 1
1 1
Output
0.5
Note

In the first sample case, both Alice and Bob can pick any real number from $$$[0,1]$$$, and the expected absolute difference is $$$\int_{0}^{1} \int_{0}^{1} |x-y| \,\mathrm{d}x \,\mathrm{d}y = \frac{1}{3}$$$.

In the second sample case, Alice can pick any real number from $$$[0,1]$$$ while Bob can only pick $$$1$$$, and therefore the expected absolute difference is $$$\int_{0}^{1} |x-1| \,\mathrm{d}x = \frac{1}{2}$$$.