In a field, there are $$$N$$$ rectangular fences, with the sides of the rectangles aligned to the coordinate axes. Two distinct fences never intersect each other, not even at a point, and in particular, not even at a vertex. However, it is possible that some fences are "surrounded" or "enclosed" by other fences.
There are $$$M$$$ possible points in the field where a parachutist can land. A given parachutist always has the same probability of landing at each of the $$$M$$$ points. More specifically, two parachutists will land in this field, and the position where each lands is independent of the other. In other words, all $$$M \times M$$$ combinations of landing locations for the first and second parachutist, respectively, are equally probable. None of the $$$M$$$ locations is on an electrified fence, not even at a vertex.
The fences are made of electrified wire, which covers the entire perimeter of the rectangle, making it difficult to cross them without receiving an electric shock. Crossing a fence means passing through the perimeter of its corresponding rectangle, that is, passing through a point that belongs to one of the $$$4$$$ sides of the rectangle. To fulfill their mission, after landing, the parachutists can walk through the field until they meet at the same point in the field. Since crossing a fence is very complicated and dangerous, they will walk in such a way as to cross the minimum possible number of fences until they meet.
Your task is to calculate the expected number of fences they must cross in total to be able to meet.
A line with two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N,M \leq 2\cdot 10^5$$$), the number of fences and the number of landing points.
Then $$$N$$$ lines, each describing one of the $$$N$$$ fences. Each line contains $$$4$$$ integers $$$X_1$$$, $$$Y_1$$$, $$$X_2$$$, $$$Y_2$$$ ($$$0 \leq X_1 \lt X_2 \leq 10^9$$$, $$$0 \leq Y_1 \lt Y_2 \leq 10^9$$$), such that the fence has corners at $$$(X_1, Y_1)$$$, $$$(X_1, Y_2)$$$, $$$(X_2, Y_1)$$$, and $$$(X_2, Y_2)$$$.
Then $$$M$$$ lines, each describing one of the $$$M$$$ landing points. Each line contains $$$2$$$ integers $$$X,Y$$$ ($$$0 \leq X,Y \leq 10^9$$$).
A single line with a single number indicating the expected number of fences that the parachutists must cross in total to be able to meet.
This answer will be accepted if it has a relative or absolute error less than or equal to $$$10^{-9}$$$.
Formally, let $$$a$$$ be your answer and $$$b$$$ be the jury's answer. Then, your answer will be accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-9}$$$.
1 2 0 0 10 30 1 1 0 31
0.5000000000
3 3 0 0 10 30 5 5 8 8 20 20 30 30 3 3 7 7 25 25
1.3333333333
1 4 10 15 100 200 1000 2000 3000 4000 5000 6000 7000 8000
0.0000000000
The following figure illustrates the second example:
