| BSUIR Open XII: Student Final |
|---|
| Finished |
How great it is to take a walk in the fresh air at night and gaze at the constellations in the sky! This time, you have decided to prepare and study the map of the starry sky. The map consists of $$$n$$$ points on the plane, where the $$$i$$$-th point is located at coordinates $$$(x_i, y_i)$$$. Also, the map includes $$$m$$$ segments connecting certain pairs of points. A connected set of points forms a constellation, and it is guaranteed that each constellation does not contain cycles.
You want to take exactly one rectangular photograph and count how many connected sets of points will be in this photograph. Let's call such sets of points imaginary constellations, as they may not coincide with the original constellations on the map, since constellations may be partially visible, and some may be divided into several imaginary constellations.
Unfortunately, your camera is broken, so each time it randomly takes a rectangular area. For this, the camera independently selects two coordinates (not necessarily integers) $$$x_a$$$ and $$$x_b$$$ uniformly at random on the interval $$$[x_{\min}, x_{\max}]$$$. Similarly, it selects two coordinates $$$y_a$$$ and $$$y_b$$$ on the interval $$$[y_{\min}, y_{\max}]$$$. As a result, the photograph includes all points $$$(x_i, y_i)$$$ for which the conditions $$$\min \{ x_a, x_b \} \le x_i \le \max \{ x_a, x_b \}$$$ and $$$\min \{ y_a, y_b \} \le y_i \le \max \{ y_a, y_b \}$$$ are satisfied.
A segment connecting a pair of points appears in the photograph only if both of its ends are also on the photograph.
You are interested in the mathematical expectation of the number of imaginary constellations in the snapshot.
The first line contains six integers $$$n$$$, $$$m$$$, $$$x_{\min}$$$, $$$x_{\max}$$$, $$$y_{\min}$$$, $$$y_{\max}$$$ — the number of points on the star map and the number of straight segments connecting points.
The second line contains $$$n$$$ integers $$$x_i$$$ — the $$$x$$$-coordinate of the $$$i$$$-th star.
The third line contains $$$n$$$ integers $$$y_i$$$ — the $$$y$$$-coordinate of the $$$i$$$-th star.
The fourth line contains $$$m$$$ integers $$$a_i$$$ — the number of the star connected at one end of the $$$i$$$-th segment.
The fifth line contains $$$m$$$ integers $$$b_i$$$ — the number of the star connected at the other end of the $$$i$$$-th segment.
$$$$$$1 \le m \lt n \le 10^5$$$$$$ $$$$$$0 \le x_{\min} \lt x_{\max} \le 10^9, 0 \le y_{\min} \lt y_{\max} \le 10^9$$$$$$ $$$$$$0 \le x_i, y_i \le 10^9$$$$$$ $$$$$$1 \le a_i, b_i \le n$$$$$$ $$$$$$a_i \ne b_i$$$$$$
It is guaranteed that all points have distinct coordinates.
Let $$$p$$$ be the mathematical expectation of the number of imaginary constellations in the photograph. It can be shown that the answer can be represented as $$$\frac{a}{b}$$$, where $$$a$$$ and $$$b$$$ are coprime integers ($$$b \not\equiv 0 \pmod{10^9+7}$$$). Here, $$$b^{-1}$$$ denotes an integer for which $$$b \cdot b^{-1} \equiv 1 \pmod{10^9+7}$$$. Output the value $$$a \cdot b^{-1}$$$ modulo $$$10^9+7$$$.
2 1 0 3 0 31 21 212
456790127
2 1 0 2 0 21 31 312
250000002
12 8 0 16 0 81 5 1 5 6 8 10 6 11 11 15 151 7 7 1 7 4 7 1 1 7 7 11 3 5 6 6 9 9 112 4 6 7 8 10 11 12
286376956
| Name |
|---|


