I. Pirates on a Boat
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Catch me on a boat with a whole bunch of pirates

It's a ****ing boat, and it's full of pirates

—Yuno Miles, Pirates on a Boat 2

Captain Oliver is plotting a new expedition for his pirate crew. His navigation skills aren't the strongest, so he decided to randomly choose a point on the shore and a direction. He is now curious about his probability of reaching the opposite shore across the sea. He has now asked for your help to determine this probability by modeling it as a geometry problem!

He has modeled each shore as a polyline in the Cartesian plane, each starting at $$$x = 0$$$ and ending at the same value of $$$x$$$. Since the shores are separated by a sea, it is guaranteed that the maximum y value of the starting shore is strictly less than the minimum y of the ending shore. In addition, there are no bays; therefore, it is guaranteed that for each polyline, the x values of the points are strictly increasing.

Captain Oliver will then pick a point $$$p$$$ uniformly randomly on the starting polyline. Let $$$\vec{n}$$$ be the normal vector to the segment that $$$p$$$ is on, pointing towards the sea (i.e., it has a positive y component). Relative to $$$\vec{n}$$$, he will then pick an angle, $$$\theta$$$ ($$$-\frac{\pi}{2} \leq \theta \leq \frac{\pi}{2}$$$), with a probability density function of $$$\frac{\cos(\theta)}{2}$$$. The boat's trajectory is then the ray starting at $$$p$$$ and traveling at angle $$$\theta$$$, in respect to $$$\vec{n}$$$. A trajectory reaches the opposite shore if it intersects the ending polyline and only intersects the starting polyline at $$$p$$$.

Input

The first line contains two integers, $$$n$$$ and $$$m$$$ ($$$2 \leq n, m \leq 10^6$$$) — the number of points on the starting shore's polyline, and the number of points on the ending shore's polyline.

The following $$$n$$$ lines will each contain two integers, $$$x_{s, i}$$$ and $$$y_{s, i}$$$ ($$$0 \leq x_{s, i}, y_{s, i} \leq 10^9$$$) — the $$$i$$$-th point on the starting shore's polyline. It is guaranteed that $$$x_{s, i} \lt x_{s, i+1}$$$ for all $$$i \in [1, n-1]$$$.

The following $$$m$$$ lines will each contain two integers, $$$x_{e, i}$$$ and $$$y_{e, i}$$$ ($$$0 \leq x_{e, i}, y_{e, i} \leq 10^9$$$) — the $$$i$$$-th point on the ending shore's polyline. It is guaranteed that $$$x_{e, i} \lt x_{e, i+1}$$$ for all $$$i \in [1, m-1]$$$.

It is guaranteed that the maximum value of $$$y_{s, i}$$$ is strictly less than the minimum value of $$$y_{e, i}$$$ and that $$$x_{s,1} = x_{e,1} = 0$$$ and $$$x_{s,n} = x_{e,m}$$$.

Output

Output a single real number — the probability that the trajectory successfully reaches the ending shore. Your answer will be accepted if it has an absolute or relative error of $$$10^{-6}$$$ with the judge's solution.

Examples
Input
3 3
0 0
1 3
2 0
0 4
1 5
2 4
Output
0.0911512657
Input
5 7
0 0
2 2
3 1
4 2
6 0
0 6
1 3
2 4
3 7
4 4
5 3
6 6
Output
0.3715825446