Electromagnetic Attacks

In Barareh, a Point-to-Point (P2P) wireless network is used to connect base stations for private data services. In a P2P wireless network, each base station uses some directional antennas to connect with the other base stations. If base stations are modeled as points and communication links are modeled as line segments, the P2P network in Barareh surprisingly has some geometric properties. Specifically, the network is a planar graph whose outer boundary is a convex polygon and all interior faces are triangles.

In the recent world conflicts, an important question has occupied the mind of Khorzukhan, the Minister of Information and Communications Technology (ICT) of Barareh. He wants to know how resilient the network is to electromagnetic attacks. In an electromagnetic attack, noise is created in a certain region (so-called attack region), disrupting all communications passing through that region. The remaining network consists of every base station and every communication link that were strictly outside of the attack region. Specifically, Khorzukhan wants to know if the remaining network remains connected. To achieve this, he has instructed his ministry to simulate multiple electromagnetic attacks separately, testing the network’s tolerance to interference and reporting whether the remaining network stays connected after each simulation.

The first line of input contains $n$, $m$, and $k$ ($3 \le n \le 10^5$, $3 \le m \le 3 \cdot 10^5$, $1 \le k \le 10^5$), which are the number of base stations, the number of communication links, and the number of attack simulations, respectively.

In the next $n$ lines, the $i$th line contains the $x$ and $y$ coordinates of the $i$th base station, both of which are non-negative integers ($0 \le x, y \le 10^9$). It is guaranteed that not all base stations are collinear.

Each of the next $m$ lines represents a communication link. Each line contains two integers $i$ and $j$ ($1 \le i, j \le n$), representing a communication link as a straight line segment between $i$th and $j$th base station. The $m$ communication links form a planar graph. The outer boundary is a convex polygon and interior faces are all triangles.

At the end, the attack regions come in $k$ lines. Each attack region is a non-empty rectangle, represented by the coordinates $x\_1$, $y\_1$, $x\_2$, $y\_2$ of its lower-left and upper-right corners ($0 \le x\_1 < x\_2 \le 10^9$, $0 \le y\_1 < y\_2 \le 10^9$). The sides of all rectangles are parallel to the coordinate axes. Note that if a base station or some part (even one point) of a link lies inside the attack region (including the boundary), it is not usable during the attack.

In $k$ lines, for each attack simulation, print Yes if the remaining network resulting from the attack is connected; otherwise print No. If all base stations are within the attack region, the remaining network becomes empty and is still considered connected.